Assignment 2 Coin Toss and Recursion Assignment Download Assignment 2.zip and import it into an Eclipse workspace using the standard instructions. Finish the Coin Toss project Finish the Recursion...

Assignment 2
Coin Toss and Recursion

Assignment

• Download
  Assignment 2.zip
  and import it into an Eclipse workspace using the standard instructions.
  
  
  


• Finish the Coin Toss project
  
  
  


• Finish the Recursion project.
  
  
  


• Submit the completed projects using the standard submission instructions
  
  o Export the projects to a zip archive named
  Assignment 2 YourName.zip
  where YourName must be your first initial and last name.
  
  
  

o You MUST use the submission instructions exactly or you will lose marks.

o You MUST name the archive correctly or you will lose marks. o For example, for

Coin Toss

• Create a list of coins, which are tossed and are either randomly heads or tails.
  
  
  


• Show the coin list, then move all of the coins which are heads to a new list, leaving the rest (tails) in the original list. Then display each list, and the summary statistics including number of coins in each list, and their total value (in cents).
  
  
  


• Coins are the basic Canadian coins.
  o Coin class is provided with complete implementation. Do not touch this.
  
  
  


• To finish the project
  o Implement the classes in the ListPackage and ListWithIteratorsPackage




• Alist, AListWithIterator
  
  
  


• Llist, LListWithIterator
  o Complete the methods in CoinToss
  
  
  


• The template code relies on ListInterface and ListWithIteratorInterface throughout.
  
  
  


• Test each implementation by commenting out appropriate lines
  
  o Test each implementation against Output.txt.
  
  
  


• The output of your programs should match the output
  
  
  


• Since the coin toss is random, the number of heads/tails will change, but the total value of ALL coins in the initial list will always be the same.
  
  
  

Implement ListInterface classes

• ListInterfacePackage and ListWithIteratorsPackage are provided for you. It is exactly the same as in the textbook and lectures.

oEvery class must implement all methods. • Classes are provided but incomplete

oClasses to be implemented • Alist, AListWithIterator
• Llist, LListWithIterator

oYou must implement all methods for each.
oYou may need to create private methods as needed.

ListInterface implementations

• Constructor and helper methods are already provided for all implementations

• AList

oMUST use an array, NOT use links and nodes

oMUST increase size of array used dynamically as list grows.

• LList

oMust use links, NOT an array

oMust use a single nextNode link for each node, and keep track of ONLY the head of the list (firstNode).

oYou must use the external Node class provided.

CoinToss program

• Complete the methods in CoinToss and test your code against Output.txt.
  
  oComment out the ListWithIteratorInterface classes not being used
  
  oOutput must match exactly.
  
  oYou must code initializeCoins(), moveCoins(), changeCoins(), and showCoins()
  
  
  


• moveCoins(), changeCoins() and showCoins() MUST use iterators.
  
  
  

oDo NOT use toArray().

Slide 6

Recursion

• You must implement versions of a factorial and Fibonacci sequence.

oImplement an iterative, recursive, and tail recursive version of each.

• The RecursionDemo program is already done

oFor each implementation, the program displays the result of the sequence and the number of recursive calls made.

oDo not touch this code. It is a simple test harness. oNote the DisplaySequence() method simply uses the

methods from the SequenceInterface.

oThe output of the program must match Output.txt exactly.

Slide 7

Math background

• Assume that everyone knows the definition of factorial.

oResearch this if you do not.
oYou must use iteration and recursion to calculate.

• The definition of a Fibonacci sequence is given in the comments of each file.

oSee also

• https://en.wikipedia.org/wiki/Fibonacci_number

• https://www.mathsisfun.com/numbers/fibonacci- sequence.html

oDo NOT use the golden ratio which is O(1).
oYou must use iteration and recursion to calculate.

Slide 8

SequenceInterface

• Each class you create must implement the SequenceInterface.
  
  
  


• The classes already have the constructor and helper methods created.
  
  
  


• The compute() method returns the result of the sequence evaluation of the argument. The method must also count the number of calls (recursive) that are made.
  
  o Note that for iterative implementations, the number of calls is always 1.
  
  
  


• Other methods get or reset the number of calls.
  
  
  


• You must implement the compute method for each
  
  type of sequence required.
  
  
  

Slide 9

Sequences

• You must complete the code for the following classes, which calculate factorial or Fibonacci number.
  
  o You need to complete the compute() method.
  o All other methods and the constructor are provided.
  
  
  


• Factorial
  o IterativeFactorial – must use only an iterative approach
  
  o RecursiveFactorial – must use only simple recursion o TailRecursiveFactorial – must use tail recursion
  
  
  


• Fibonacci – similar to Factorial above
  o IterativeFibonacci – must use only an iterative approach o RecursiveFibonacci – must use only simple recursion
  o TailRecursiveFibonacci – must use tail recursion
  
  
  


• Note that the number of calls for iterative is always 1.
  
  
  


• Note that the number of calls for tail recursion is
  
  
  

significantly less than normal simple recursion.

Slide 10

Grading