| |
For programming assignments it is best to make a script (log) file showing
your compilation, executions and results:
script
do your compilation and runs
exit
Then all you did under "script" will be logged in a file with name typescript.
You may edit it a little to make it look nice.
You may do the programming assignments in a language of your choice.
Assignment 1. Asymptotic notation, performance analysis.
Due: 01/23/24
Read:
HSR book Sections 1.3.3, 1.3.4
Neapolitan book Ch I
Neapolitan book, Ch. I Problem set 1.4: pp. 45-48 ## 19 (+ prove using definitions of big O and Omega), 27 (using limits; show all work for determining the limits), 32, 35 (also implement and run for the values listed in 35(a); add timing statements, run, and plot timing graph; determine the values of n so that you obtain a nice graph).
[ pdf ]
Submit a zip file including: a scanned copy of your written assignment,
your typescript or log file (showing compilation, input and output), and
code of your implementation.
Code samples:
[ time.c ]
[ rand1.c ]
[ rand2.c ]
[ erand-example.c ]
[ erand-example2.c ]
Assignment 2. Recurrence relations, performance analysis.
Due: 02/09/24; upload in Elearning drop box.
Read:
HSR book, Neapolitan book, and slides: Divide-and-conquer and recurrence relations
Written assignment:
Solve recurrences using the characteristic equation,
and determine the order of complexity of the solution:
Neapolitan App. B exercises pp. 637-641 ##12(b,c,d), 15(b), 16, 19(b).
For ##12(b,d) and #16, only determine the general solution (not the coefficients).
For the other problems, determine the coefficients and also check your solution
(by plugging it into the recurrence, and checking the initial conditions).
Show all work!
Programming assignment:
Solve and implement #4. Make a timing graph for a suitable range
of n, and compare your
experimental results with your theoretical solution.
[ Neapolitan pp. 637-641 ]
Assignment 3. Programming Assignment: Huffman trees
Due: 02/29/24, in dropbox.
Read:
HSR book Ch. II), slides
Write a program to generate a Huffman tree and corresponding message
codes. Build a min-heap keyed with the frequencies.
Output the message code for each frequency, as well as the total weighted external path length for the tree.
- Run for the frequencies of (select three of A, B, C and D):
A. the English alphabet, as given in
Moret and Shapiro p. 294, Figure 5.9;
B. Cyrillic symbols; see the symbols and frequencies;
C. Hiragana syllabic symbols in the Japanese writing system;
see a list of symbols and frequencies.
Calculate the frequencies more accurately based on the Count
and Total count, e.g., for the first frequency listed:
645670/10182184 = 0.063412,
and for the last one, 386/10182184 = 0.000038.
D. Arabic letters; see symbols and frequencies.
-
Generate sets of n frequencies at random and run your program for
increasing n. Time the execution of (1) building the initial heap
keyed with the frequencies ; and (2) the complete generation of
the Huffman tree. Graph the times as a function of n.
Notes: (a) To get more accurate results, you can repeat the
Huffman tree construction a number of times and use the average time.
(b) The size of the problem should not be limited by the use of
static arrays (use dynamic memory allocation).
Your report should include a comparison of the observed performance with
the expected theoretical behavior. Note that the building of the heap
should be done in linear time.
Assignment 4. Programming Assignment: Dynamic programming for TSP.
Due: 04/02/24, in dropbox.
Read:
HSR book Ch. 5, 5.9, and slides V.
Implement the dynamic programming method for TSP covered in class (based on HSR).
Input and output the number of cities and the cost adjacency matrix.
Also output the g-functions, minimum cost and associated tour, and
execution time.
Run for the example covered in the slides, and another example.
Assignment 5. Programming Assignment: Branch and bound method for the 15-puzzle ((n^2 - 1)-puzzle).
Due: 04/20/24, in dropbox.
Read:
HSR book Ch. 8, 8.1.2-3, and slides VII (based on Papadimitriou
and Steiglitz)
Programming assignment: 15-puzzle.
Implement Least Cost (LC) search. The cost for a node x in the state
space tree is the length of the path from the root to the nearest goal
node (if any) in the subtree with root x. Use the approximate cost
C(x) = f(x) + G(x),
where f(x) = the length of the path from the root to node x,
and G(x) = the number of non-blank tiles not in their goal position.
At least G(x) moves will have to be made to transform state x to the
goal state, but more may be needed. Refer to the state space tree of
Figure 8.3.
At each step, a node of least cost is selected for expansion, until
the goal state is reached. For an efficient selection,
use a min-heap keyed with the costs.
Input and output the initial configuration of the puzzle.
Also output some intermediate configurations (and final), and total execution time.
Run your program for five initial states that lead to a goal state.
Extra credit: generalize to the (n^2 - 1)-puzzle.
Extra-credit assignment 6.
Select an extra credit assignment that does not overlap with
your semester project.
Due: 04/20/24; upload in Elearning drop box.
Programming assignment
A. Backtracking
Read:
HSR book, and slides: Backtracking
For the n-queens problem we found that some solutions are
reflections or rotations of other ones. Observe that, for finding
inequivalent solutions, the NQueens backtracking algorithm needs
only to set x[1] = 2, 3, ... , ceiling(n/2).
(a) Modify NQueens so that only inequivalent solutions are
computed (and implement).
(b) Run for n = 4, 5, ..., 8, 9, and 10. Tabulate the number of solutions
found for each of these values of n.
Time the runs as a function of n,
and add a timing graph to your report.
B. k-th order selection
Read (the sections we covered in class):
HSR book Section 3.6
Neapolitan book Section 8.5.4
class notes (slides)
- Implement k-th order selection, k-th smallest element: (i) version with pivotitem using median of medians;
(ii) randomized version.
- Run with data showing worst case behavior, and with random data set. Time and compare the performance of the two algorithms for increasing array size n. For n use odd multiples of 5.
- Call the two methods for the same data, preferably from the same main program. Demonstrate and discuss your findings in your report.
Note that the same random data set can be regenerated by using the same seed for the random number generator.
- Submit a zip archive with programs, data and report. Include typescript or log files or screenshots showing your compilation, sample execution with (small) input data and resulting output.
|
|