SCHOOL OF ENGINEERING OF TECHNOLOGY
TCSS 343 – Programming Assignment
October 29, 2019 1 GUIDELINES
This is a group assignment. Each group may consist of 1 or 2 students. In other words, you can choose to work by yourself, or with one single colleague. Please state the names of your group members on your submission.
Each group is also expected to give a 5-minute presentation and demo of your submis- sion during the last two classes.
Details: In this assignment, you will implement algorithmic techniques in Java.
There is also a bonus challenge that also involves these techniques and an implementation
in Java.
Homework should be electronically submitted via Canvas by midnight on the due date. Each
group is expected to submit the following files:
• Report.ThesubmittedreportMUSTbetypesetusinganycommonsoftwareandsubmit- ted as a PDF. We strongly recommend using LATEX to prepare your solution. You could use any LATEX tools such as Overleaf, ShareLatex, TexShop etc. When presenting your results, use log-scale graphics if/when results are too different (tiny vs. huge) to coexist on the same linear-scale graphic.
• Java source code. Submit one single Java file containing all your code, except for the challenge which must be in one single separate Java file.
You must name your source code tcss343.java for the normal part of this assignment, and challenge.java for the bonus challenge.
• Yourinputtestingfiles.Submitalltheinputtestingfilesyoudocumentedinyourreport. The input testing files are tab-delimited text file. An example is provided on Canvas, except for the challenge (where all arguments are given in the command line).
1
Execution. We will use the following command to execute your program for the normal part of this assignment:
java tcss343 < input.txtThe challenge has its own format describes below.Remember to cite all sources you use other than the text, course material or your notes.22 PROBLEM STATEMENTThere are n trading posts numbered 1 to n, as you travel downstream. At any trading post i, you can rent a canoe to be returned at any of the downstream trading posts j > i . You are given a cost array R (i , j ) giving the cost of these rentals for 1 ≤ i ≤ j ≤ n . We will have to assume that R (i , i ) = 0 and R (i , j ) = ∞ if i > j . For example, with n = 4, the cost array may look as follows: Therowsarethesources(i-s)andthecolumnsarethedestinations(j’s).
1234 10237 2 024 302 40
The problem is to find a solution that computes the cheapest sequence of rentals taking you from post 1 all the way down to post n. In this example, the cheapest sequence is to rent from post 1 to post 3 (cost 3), then from post 3 to post 4 (cost 2), with a total cost of 5 (less than the direct rental from post 1 to post 7, which would cost 7).
3 YOUR TASKS 3.1 BRUTE FORCE
(4 points): Design a brute force solution to solve this problem. You need to print the cheapest solution, as well as the sequence.
What is the asymptotic complexity of this algorithm?
3.2 DIVIDE AND CONQUER
(7 points): Express the problem with a purely divide-and-conquer approach. Implement a recursive algorithm for the problem. Be sure to consider all sub-instances needed to compute a solution to the full input instance in the self-reduction, especially if it contains overlaps. As before, you need to print the solution, as well as the sequence.
What is the asymptotic complexity of this algorithm?
3.3 DYNAMIC PROGRAMMING
(7 points): Design a dynamic programming table for this problem. How is the table initial- ized? In what order will the table be filled? How would you use the table to find the cheapest sequence of canoe rentals from post 1 to post n? Implement the corresponding dynamic programming solution.
What is the asymptotic complexity of this algorithm?
3
3.4 DOCUMENTATION
(4 points): Provide a well prepared document that describes your solutions, complexity analy- ses, and result analyses. Use log-scale graphics whenever the discrepancy between the cases you consider is so large than linear-scale graphics will make it too hard to compare those cases visually.
You must submit your code which should be well documented as well. If there is any known error in the code, you must point that out.
Also, document the division of labor (who did what) in your report. Remember: your presentation should briefly describe all of these items.
3.5 TESTING
(4 points): Call a pseudo-random number generator to create a cost table of size n × n (notice only the upper diagonal of this matrix is full) for the following values of n: 25, 50, 100, 200, 400, 800.
For each n, consider two circumstances: in the first, the costs are entirely random (apart
from being positive); in the second, the costs are random but increasing along each row of the
cost matrix (add a random non-negative increment from the previous value on that row). Save your input testing files as tab-delimited text files. An example input file corresponding to the example input described in Section 2 is provided on Canvas as 〈sample_input.txt〉.
Include your java code of the above input generator in the source code of your submission. Your code is expected to read in one input testing file, and generate the solution correspond-
ing to each of the three approaches described in Sections 3.1, 3.2 and 3.3. 3.6 ANALYSIS OF RESULTS
(4 points): Analyze the results using visualization (you may use MS Excel or equivalent spread- sheet software for that). Use log-scale whenever the numbers you get are too discrepant to be easily distinguished in linear scale.
1. qualityofthesolutions(y-axismustpresentthecost,i.e.,theobjectivefunctionvalue) for varying x.
2. running time of the algorithms (y-axis will present the machine time the algorithms need to compute) for varying x.
Your analyses should be included in the submitted document.
Remember: use log-scale graphics if/when results are too different to coexist (i.e. when one
results is tiny and the other is huge), both in the submitted documentation and in your final
presentation.
4
4 BONUS CHALLENGE (5 POINTS): THE d-DIMENSIONAL n-QUEENS PROBLEM
The well-known 8-Queens problem consists of placing 8 queens on an otherwise empty chessboard in such a way that no two queens attack each other (hence, there are no two queens on the same row, column, or diagonal, and no other pieces on the chessboard), as shown in fig. 4.1.
Figure 4.1: Sample solution to the 8-Queens problem
A trivial generalization is the n-Queens problem, where the task is to place n queens on an n × n board instead. This problem has real-world applications like managing distributed memory storage or preventing deadlocks in computer networks.
A not-so-trivial generalization is the d-dimensional n-Queens problem, which simply asks how many queens can be placed on a d-dimensional chessboard of size n×n×···×n (d times, i.e. nd cells). The answer is easy for d = 2, since one can place exactly n queens on a 2-dimensional chessboard in non-attacking configuration (every queen must be alone on each row and each column, and there are n rows or columns on a 2-dimensional chessboard).
But for d > 2 the answer is not known exactly, and in general has to be determined by direct inspection. For instance, it is possible to place 4 non-attacking queens on a 3-dimensional chessboard of size 3 × 3 × 3.
4.1 FORMALIZATION
In general, a queen on a d-dimensional chessboard of size nd is specified by a tuple q := (q0,q1,…,qd−1)ofcoordinateswhere0≤qj
Reviews
There are no reviews yet.