CS 3510: Algorithms

Assignment 4

Assignment

Problems identified by x.y(z) denote the problem “y”, in chapter “x” of the textbook, with part “z”. If “z” is not noted, then the entire problem is required.

Assignment 4a

4.22 Read this problem, and write down your ideas and questions about how to turn it into a graph path problem, such that our shortest path algorithms can be modified to solve it.
Implement the binary heap from Figure 4.16 of the text book. Test it for correctness.

Assignment 4b

4.1(a) Run Dijkstra, tracking the problem data in a table.
4.12 Your algorithm should be O(|V|^2) or better.
Create a runtime measuring program for the binary heap. Include the ability to measure performance of individual methods as a function of the number of items in the heap. Use powers of 2 for the sizes.

Assignment 4c

4.1(b) Run Dijkstra, show shortest-path tree.
4.14 By efficient, we mean no worse than Dijkstra’s algorithm.
Measure the runtime of the makeheap(), deletemin(), insert() and decreasekey() methods. For powers of 2 from 2^4 to at least 2^28. Record the results in a spreadsheet.

Assignment 4d

4.2(a) Run Bellman-Ford, tracking the problem data in a table as we did in class. Each iteration is a new array, based on the previous array. Start from node S.
4.2(b) Draw the shortest-path tree, using your table data.
Add theoretical functions to your spreadsheet of results, include at least log n, n, n log n and n^2. Produce a table of these values normalized the deletemin() column at size 2^20. Chart this table.

Assignment 4e

4.8 (2 points) Prove = proof, disprove = counter-example
4.5 (2 points)

Assignment 4f

4.11 (2 points) How can you find cycles using path algorithms in this chapter?
4.15 (2 points)
4.19 (2 points ) Look for a modified version of Dijkstra that meets the criteria.

Assignment 4z, Due Never (optional)

Other problems from the chapter

Submission

Submit you solutions by the due date and time. For written problems, your work and answers as a PDF to Canvas. For code, submit the source code to the class git repository. For tables and graphs, submit a PDF to Canvas.

Last Updated 01/09/2023