CS 0445 Summer 2023 Assignment 1 - University of Pittsburgh

CS 0445 Summer 2023 Assignment 1

Online: Wednesday, May 17, 2023 Due: All source files plus a completed Assignment Information Sheet zipped into a single .zip file and submitted properly to the submission site by 11:59PM on Saturday, May 27, 2023 (Note: see the submission information page for submission details) Late Due Date: 11:59PM on Tuesday, May 30, 2023

Purpose: To refresh your Java programming skills and to emphasize the object-oriented programming approach used in Java. Specifically, you will work with control structures, class-building, interfaces and generics to create and utilize a simple array-based data structure.

Goal 1: To design and implement a simple class MultiDS that will act as a simple data structure for accessing Java Objects. Your MultiDS class will primarily implement 2 interfaces ? MyQ and Shufflable. The details of these interfaces are explained in the files MyQ.java and Shufflable.java. Read these files over very carefully before implementing your MultiDS class.

Goal 2: To utilize your MultiDS class by implementing a simple version of the card game "War". In this case your program will be a client using MultiDS and the details of the MultiDS implementation will be abstracted out.

Details 1: For the details on the functionality of your MultiDS class, carefully read over the files MyQ.java, QueueInterface.java, Shufflable.java and Assig1A.java provided on the Web site. You must use these files as specified and cannot remove/alter any of the code that is already written in them.

In Lecture 3 we discussed the author's QueueInterface, which is an ADT that allows for adding at the logical back (enqueue) and removing from the logical front (dequeue) of the data structure. The methods in this interface are specified in file QueueInterface.java. See the Lecture 3 Powerpoint presentation for some background and ideas about the QueueInterface.

In Recitation Exercise 2 you implemented (or will implement) two simple classes called PrimQ1 and PrimQ2 that satisfy QueueInterface but in an inefficient way. Specifically, they use an array that maintains one logical end or the other of the queue at index 0 and thus requires shifting for one of the enqueue() or dequeue() operations. We will discuss specific run-time analysis of these implementations a bit later in the course, but it is intuitive that there is a lot of overhead in both of these implementations.

A queue can be implemented in a more efficient way with an array if we allow both logical sides of the queue to move along the array in a circular fashion. For example, consider the array below:

0

1

2

3

4

5

6

7

10

20

30

40

50

front

back

In this queue, both front and back will move forward within the array as we enqueue() or dequeue() in the queue. For example, if we enqueue(55) in this queue, it will look as follows:

0

1

2

3

4

5

6

7

10

20

30

40

50

55

front

back

If we then dequeue(), the queue will look as follows:

0

1

2

3

4

5

6

7

20

30

40

50

55

front

back

Note that for this approach to work effectively, both back and front will need to "wrap" around the end of the array when necessary. This enables the beginning indices in the array to be reused. For example, if we now enqueue(66), the array will appear as follows:

0

1

2

3

4

5

6

7

66

20

30

40

50

55

back

front

Your MultiDS class must implement the queue using this circular approach. Note that when the queue is implemented in this way, we do not have to shift data in the array and either of the enqueue() or dequeue() methods can be implemented with just a few statements. However, there are some special cases to consider (ex: detecting a full array, handing an empty queue) so think carefully about how you would implement your class.

The MyQ interface extends QueueInterface, adding 2 new, simple methods (size() and capacity()).

Your MultiDS must implement MyQ as well as the Shufflable interface. Shufflable has just one method, shuffle(), which will permute the data within the collection in a pseudo-random way. Thus, your class header should be:

public class MultiDS implements MyQ, Shufflable

Important Note: The primary data within your MultiDS class must be an array. You may not use any predefined Java collection class for your MultiDS data.

In addition to the interface methods, you will also need a constructor and a toString() method for your MultiDS class. See file Assig1A.java for details on these methods.

Your MultiDS class must also be able to dynamically resize when necessary. As we discussed (or will discuss) in Lecture 4, array-based data structures can be logically resized by allocating new, larger arrays and copying the data from the old array into the new array. This can be done in your MultiDS class but, due to its circular nature, you must be careful when doing this to preserve the queue order. Think about how you would resize for this class. Note that after resizing (but before doing anything else) the capacity() of your MultiDS should double but the size() should be unchanged.

After you have finished your coding of MultiDS, the Assig1A.java file provided for you should compile and run correctly, and should give output identical to the output shown in the sample executions (except for the segments where the data is shuffled, since it will be pseudo-random in that case).

Details 2: War is a card game played often by children that has many variations. You will implement the simple version as described below:

? Initially shuffle a 52-card standard deck of cards ? Deal the cards out completely to two players, alternating cards to each player ? Do the following until one player is out of cards or until a set number of rounds have completed:

? Each player plays the top card in their hand ? If one player's card beats the other (has a higher rank ? suits don't matter), that player

puts both cards into their discard pile ? If the players tie, it is a WAR, so do the following until the WAR is resolved:

? Each player plays a card without comparing (in the physical game this would be placing a card "face down" on the table).

? Each player plays one more card and compares in the same way as above ? The winner of the WAR takes all played cards (initially compared cards,

uncompared cards, second compared cards). For a single WAR this will be 6 total cards. ? If the WAR cards also yield a tie, repeat the process (one uncompared card, one compared card) until there is a winner. Thus a single round of the game could in fact have an arbitrary number of card comparisons and put an arbitrary number of cards at risk. The following rules also apply to the game: ? If at any point in the game a player's hand is empty, the player should move the cards in their discard pile into their hand and shuffle them. ? If at any point in the game (even in the middle of a round) a player has no cards remaining in both their hand and their discard pile, they have lost the game. ? If the both players have cards remaining after a set number of rounds (can vary), the player with the most cards (hand + discard pile) is the winner. In this case, it is possible for a tie to occur, with each player having 26 cards.

Implementation Requirements: ? Your initial card deck, the player's hands, the player's discard piles and the cards "in play" must all be stored in Card (single) or MultiDS (collection) objects. ? The Card class must be used as provided and cannot be changed. ? The maximum number of rounds for the game must be read in from the command line ? To allow better testing of your program, you must output when WARs occur and when discard piles are reshuffled. See the various sample output files for required output information.

You must submit in a single .zip file (minimally) the following 8 complete, working source files for full

credit:

MyQ.java

QueueInterface.java

EmptyQueueException.java

Shufflable.java

Assig1A.java

Card.java

the above six files are given to you and must not be altered in any way.

MultiDS.java

War.java

the above two files must be created so that they work as described. If you create any additional files, be

sure to include those as well.

The idea from your submission is that your TA can unzip your .zip file, then compile and run both of the main programs (Assig1A.java and War.java) from the command line WITHOUT ANY additional files or changes, so be sure to test it thoroughly before submitting it. If you cannot get the programs working as given, clearly indicate any changes you made and clearly indicate why on your Assignment Information Sheet. You will lose some credit for not getting it to work properly, but getting the main programs to work with modifications is better than not getting them to work at all. See the CS 0445 Web site for an Assignment Information Sheet template ? you do not have to use this template but your sheet should contain the same information. Note: If you use an IDE such as NetBeans to develop your

programs, make sure they will compile and run on the command line before submitting ? this may require some modifications to your program (such as removing some package information).

Hints / Notes: ? See program A1Help.java for some help with the Card class and using the MultiDS class with Card objects. ? See file A1Out.txt to see how your output for Assig1A should look. As noted, your output when running Assig1A.java should be identical to this with the exception of the order of the values after being shuffled. ? See files WarOut1.txt , WarOut2.txt , WarOut3.txt for example runs of my War.java program. Your War program output does not have to look exactly like this but the functionality should be the same.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download