Introduction
，All source code files should contain author and partner identification in the comments at the top of the file.
，”.”，”Q”
Requirement
Lab 6 (Recursion)
CSC 172 (Data Structures and Algorithms)
Spring 2018
University of Rochester
Due Date: Sunday, March 11 @ 11:59 pm
Note: You can submit until March 18 @ 11:59 pm without penalty (not recommended)
Introduction
The labs in CSC172 will follow a pair programming paradigm. Every student is encouraged (but not strictly
required) to have a lab partner. Every student must hand in their own work but also list the name of their lab
partner if any on all labs.
In this lab, we will practice recursive thinking. You and your lab partner may discuss the lab with other pairs
in the lab. It is acceptable to write pseudocode on the whiteboard for the benefit of other lab pairs, but you are
not allowed to electronically copy and/or transfer files between groups.
Task 1 (Make Change) (50 pts))
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write
a method makeChange(int n) that takes ‘n’ cents as input, and returns the number of ways of representing
‘n’ cents. You can either write an iterative or a recursive solution. You are also allowed to have any number of
helper functions. Though we will allow iterative solution, we recommend you try the recursive solution for this
problem.
Task 2 (8-Queen Problem) (50 pts)
Write a java method findEightQueen to find and print at least one way of arranging eight queens on a chess
board so that none of them attack each other (i.e., they do not share the same row, column, or diagonal). Any
textual representation of the board is fine as long as the board is comprehensible. You are encouraged to draw a
blackwhite (or any color of your choice) chess board and make the squares holding the queens blue. [No extra
credit.]
Note: You need to find the solution. Just printing a solution will not give you any points.
Reference:
Submission
• Your submitted file must be named Lab6.zip . No .rar , .7z or any other formats will be accepted.
• The zip files must contain only two .java files — MakeChange.java and EightQueen.java . The
two methods you required to write must be named as makeChange(int n) and findEightQueen() .
You are recommended to supply us the test cases you used. You can make your methods static if you want.
Once again, we are looking for only two .java files. So, please do not upload the whole project. If you do
not know how to find the .java files, ask the lab TAs.
Submit Lab6.zip at the appropriate location on the Blackboard system at learn.rochester.edu. You
should hand in a single zip (compressed archive) Lab6.zip containing two java files and a README file.
Lab #6 (Recursion) Page 1 / 2
1. README,aplaintextfilemustincludeyourcontactinformation,yourpartner’sname,abriefexplanation
ofthelab(aone-paragraphsynopsis. Includeinformationidentifyingwhatclassandlabnumberyourfiles
represent.), and one sentence explaining the contents of any other files you hand in.
2. Two Java source code files EightQueen.java and MakeChange.java representing the work accom-
plished. Following the naming convention is mandatory. All source code files should contain author and
partner identification in the comments at the top of the file.
3. Any additional files as required.
Lab #6 (Recursion) Page 2 / 2