PROGRAM #2

Fall 2008

Due: October 17, 2008, 5pm on eLearning

---

General Guidelines:

• This submission should be accompanied by a cover sheet which is a single page document that contains all the information listed in this sample cover sheet: Word or PDF. Assignments without a cover sheet will NOT be graded.
• This is an individual programming assignment. No team work is allowed. You may consult with others (this is encouraged) or refer materials online, but you MUST reference your sources (people, books, webpages, etc.). These sources must be listed on the cover sheet mentioned below (no points will be deducted). However, the final material for submission should be entirely written by you. Directly reproducing source codes or verbiage from online resources or other's people's assignments will be considered plagiarism, and therefore will be awarded ZERO points and subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss textbook is an exception to this rule, and is encouraged wherever possible.)
• Grading will be based on correctness, coding style, implementation efficiency, exception handling, source code documentation, and the written report.
• Submission: All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last name as follows: "Program2<YourLastName>.zip"), and attached by email and sent to “All Instructors” and “All Teaching Assistants” through the eLearning website. Submissions are due by 5pm. A penalty of 10% will be assessed for late submissions within the next 24-hour.
  Note: Submissions will be accepted only through eLearning. Any submission outside the eLearning portal will be discarded. Also, we will not be able to send out acknowledgements for each submission. If there is something missing in your assignment/attachment we will contact you directly.

---

There are two problems in this project:

PROBLEM#1    Maximum subsequence sum problem:

(40 points)

For this assignment you will be implementing the four different solutions we discussed in class for the maximum subsequence sum problem, and comparing them for performance. Here are the details:

• Implement the four algorithms (maxSubSum1, maxSubSum2, maxSubSum3, maxSubSum4) from the Weiss textbook (pages 52-58) exactly as written. You will need to implement your own max3 function, which is needed to complete maxSubSum3.
• Write a test driver main() function that will allow you to (i) test each algorithm on an arbitrary input array, (ii) report program running time, and (iii) report the number of additions performed for a given run. For measuring time, use the same timing functionality that you implemented in your first programming project. (Refer to the example ElapsedTimeExample.cpp). The timing statistics should  be in seconds or milliseconds or microseconds (whichever gives the closest precision to the actual time of the event).
• You should test each of the four algorithms on three different sequence sizes: 8, 16, 32, 64, 128, 256, 512, 1024. Each sequence should be loaded with the repetitive subsequence <5,2,1,-4,5,3,-2,-3>. So, the sequence of size 8 will be exactly this. The sequences of sizes 16 or more are to be constructed by repeatedly concatenating the 8-length sequence blocks - e.g., the 16-sequence input will look like:  <5,2,1,-4,5,3,-2,-3, 5,2,1,-4,5,3,-2,-3>, and the 32-sequence input will look like: <5,2,1,-4,5,3,-2,-3, 5,2,1,-4,5,3,-2,-3, 5,2,1,-4,5,3,-2,-3, 5,2,1,-4,5,3,-2,-3>, and so on.
• For each call to each of the four algorithms with each of the three sequences, you should output:
• the name of the algorithm (maxSubSum1,maxSubSum2,etc.);
• the size of the input sequence (n);
• the result (maximum subsequence sum);
• the total number of additions performed; and
• the total time taken by the algorithm for this call.
• Using the above test results, make two plots as follows:
•     Plot I) Running times for all 4 algorithms (on Y axis) and for each of the input sizes from 8 to 1024 (on X axis).
•     Plot II) Number of additions performed for all 4 algorithms (on Y axis) and for each of the input sizes from 8 to 1024 (on X axis).

            Your curves in each plot should obviously say which curve stands for which algorithm (using legends). You must use some electronic tool (e.g., matlab, gnuplot, excel) to create the plot - handwritten plots will NOT be accepted.

Report for problem 1:

In a separate document (Word or PDF), compile the following sections:

· A: Problem statement. In a couple of sentences state the goal(s) of this exercise.

• B: Experimental setup. In this section, you should provide a description of your machine specification (CPU, its clock speed, RAM available) where all the testing was conducted.

· C: Experimental Results: In this section, include the following:

o The plots from the above test results

o Answer this question in not more than 5 lines: Are the observations made in the above plots as per your expectations? If so, why, and if not, why not?

What you need to submit:

In one zip file called "MaxSubSum<YourLastName>.zip", compress the following:

1. A separate folder containing all your source code (including the main function you used for testing)
2. The Report

---

PROBLEM #2    A simple board game:

(60 points)

For this assignment, you will be implementing a simple board game using an appropriate tree data structure of your choice. A "board" is defined as a m x m square matrix, with each cell identified using a unique (x,y) coordinate. An example 10 x 10 board is shown in the figure below. In a game, a board has n players, each illustrated in the figure as a queen piece (from a chessboard). Note that n should less than or equal or m x m. The figure shown below is for m=10 and n=8.

Your task is to implement the following functionalities:

• Implement a Board class that implements a board of size m x m with n players. At the start of the game, all the m x m empty cells of the board are empty (i.e., n=0). As the game progresses n is allowed to change. However, the dimensions of the board (m x m) have to remain fixed.
• Implement a Player class that implements each player. Each player object will have a unique, positive integer ID, and will have a unique (x,y) position that it occupies on the board. Care must be taken that the value of (x,y) position is always within bounds of the board at any given point of time. Also, no collisions are allowed - i.e., no two players are allowed to share a cell.
• Implement an Insert method in the Board class that will allow you to insert a player into the board in O(log n) time. The method should take as input the player ID to be inserted, along with a desired (x,y) position into which it is to be initially placed. If successful, the method should return an iterator to the player object just inserted. For a successful insertion, the ID should not be a duplicate of some other existing player and the position should be within bounds & currently unoccupied. Upon successful insertion, the value of n is updated. If the insertion fails, the code should display an error message and return a null iterator without modifying anything.
• Implement a Remove method in the Board class that will allow you to remove a player from the board in O(log n) time . The method should take as input the player ID to be removed, and should return the number of players removed (1 upon success and 0 if not found). The value of n should also be accordingly updated. 
• Implement a Find method in the Board class that is given a player ID and returns an iterator to the corresponding player object. The method should run in O(log n) time.
• Implement a MoveTo method in the Board class that takes as input a player ID and a destination (x,y) position. The method should run in O(log n) time. The method should move the player ID from its current position (say (x1,y1)) to the new position (x,y) only if the both following conditions are satisfied: i) (x,y) is within bounds and an unoccupied position, and i) the movement from (x1,y1) to (x,y) is always along the same row or same column or same diagonal in any direction (just as for the queen in a chess game). Upon a successful move, the method should return an iterator to the moved player object. If the move fails, the code should display an error message and return a null iterator without modifying anything. 
• Implement a PrintByCoordinate method in the Board class that prints all the player IDs along with their (x,y) positions, in the increasing order of their x-coordinates. If there are more than one player with the same x-coordinate then you may print them in any order. This method should run in O(n) time. In the example illustrated in the figure above, this method can print the player IDs from the positions (in this order):  (3,2)  (4,3) (4,6) (5,7) (6,3) (8,2) (9,3) (9,8). Another equally correct output (among other possibilities) is: (3,2)  (4,6) (4,3) (5,7) (6,3) (8,2) (9,8) (9,3).
• Implement a PrintByID method in the Board class that prints all the player IDs along with their (x,y) positions, in the increasing order of their IDs. This method should run in O(n) time.
• Write a main function in which you test all the above methods at least once. You can think of using the example in the figure above as an initial configuration to do testing. (We will have our own test code to test your source.)

You should make the best choice possible for the container data structure(s) that will store all the players of a board along with their positions. Your decision should be based on what can guarantee the desired performance for each of these methods. 

Hint: Note that PrintByCoordinate requires traversing the set of players in order of their x-coordinates. But other methods require traversing the set of players in the order of their IDs. So, think about maintaining the set of players in two separate data structures: once in a structure ordered by ID and once in a structure ordered by x-coordinates. Of course, this design would imply that you need to update both structures every time there is an update.

Report for problem 2:

In a separate document (Word or PDF), compile the following sections:

· A: Problem statement. In a couple of sentences state the goal(s) of this exercise.

• B: Experimental setup. In this section, you should provide a description of the testing you conducted in not more than half a page.

· C: Algorithm design. Within one page, provide a brief description of the main ideas behind your implementation. Add a high level description (in plain English) behind each method’s implementation (basically what data structure it uses and what run-time complexity that method will take). Add a figure to illustrate the design, if possible.

What you need to submit:

In one zip file called "BoardGame<YourLastName>.zip", compress the following:

1. A separate folder containing all your source code (including the main function you used for testing)
2. The Report

---

FINAL CHECKLIST FOR SUBMISSION:

    ___  Cover sheet

    ___ MaxSubSum<YourLastName>.zip

    ___ BoardGame<YourLastName>.zip

    ___  Both the above zipped into another folder archive called Program2<YourLastName>.zip