Submitting:

  • All homeworks should be turned in electronically to myCourses.
  • Paper submissions may be scanned in if legible.
  • If you take a photo of your paper solution, please take the photo outside or close to a bright window, for legibility.

Due dates:

  • Homeworks are due by 10pm on the due date (Thu).
  • No late submissions are accepted.
  • If there are extenuating circumstances, contact the instructor as soon as possible to make arrangements.

References:

  • If you find a resource helpful (from internet search, blog post, Stack Overflow, online courses, our lecture notes, etc), be sure to cite it. Citation format doesn’t matter, but make it easy for the TA to find the source: e.g., a clickable link.
  • Code / pseudocode should be your own work. If you find code online, understand how it works, then go write up your solution on your own.
  • The basic machine model was discussed in Lecture 1. Don’t use library functions which obviate the bulk of a question. E.g., if you’re asked to implement a sort, don’t use Python’s sorted().

Programming assignments:

  • Please submit all your code, either separately uploaded or in a ZIP (or tar) file. Up to 20 files (20MB total) may be uploaded to myCourses.
  • Make it easy for the TA to recompile and run it if needed.
  • Include a short, informal write-up describing your code. Make it easy for the TA to understand your code.
  • Include extensive test cases (valid and invalid input, simple and complex) demonstrating each aspect of your code. Document the purpose of each test case, and include a demo with actual output.
  • You are encouraged but not required to use revision control like Git and Github.

HW9 (40pts) (solutions)

  1. Consider the following weighted undirected graph:
    MST
    Where there is a choice, consider vertices in alphabetical order, and edges in lexicographic order of endpoints: e.g., (a,c) < (a, d) < (b, d).
    • (a) (3 pts) Demonstrate Kruskal’s minimum spanning tree algorithm on the graph.
    • (b) (4 pts) Demonstrate Prim’s algorithm on the graph, starting at vertex a. Illustrate the progress of the vertex queue.
    • (c) (1 pt) Find a different MST of this graph, other than what you found in parts (a) and (b).
  2. (4 pts) Demonstrate the Bellman-Ford algorithm on the following weighted directed graph to find shortest-paths from the source a.
    Iterate over edges in lexicographic order, and show v.d for all vertices after each iteration.
    • How many iterations were needed to achieve convergence?
    • Show the tree of shortest-paths to all vertices from a.
    • BF
  3. Given a weighted undirected graph `G = (V, E, w)` with `w(u,v) > 0, forall (u,v) in E`, consider increasing each edge weight by 1:
    Let `w’(u,v) = w(u,v) + 1, forall (u,v) in E`, and `G’ = (V, E, w’)`.
    • (a) (3 pts) Prove or disprove via counterexample: MSTs are preserved by this transformation. I.e., if T is an MST of G, then T is also an MST of G’.
    • (b) (3 pts) Prove or disprove via counterexample: shortest paths are preserved by this transformation. I.e., if p is a shortest path from u to v in G, then p is also a shortest path from u to v in G’.
  4. Programming project: Implement Prim’s algorithm for minimum spanning tree. Input format is discussed below. Allow the user to specify a start node. Output is the weight of the MST, and for each non-root node, its parent in the MST.
    You may use a library for priority queue (e.g., Python’s heapq); you don’t have to implement that yourself.
    • (12 pts) Correct, working code.
    • (5 pts) Documentation: write-up, readable code, good identifiers, etc.
    • (5 pts) Tests, including edge cases, actual output, etc.
    • (4 pts extra credit) A nice graphical user interface.

Input format for the programming project: a weighted edge list in plain text:

[num vertices]
[num edges]
[source] [dest] [weight]
[source] [dest] [weight]
...

Some test input (from Sedgwick + Wayne):