### 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)

- Consider the following
**weighted undirected**graph:

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).

- (a)
*(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`

.

- How many
- 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:**MST**s 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’*.

- (a)
**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):

- tinyEWG.txt (8 vertices, 16 edges)
- mediumEWG.txt (250 vertices, 1,273 edges)
- 1000EWG.txt (1,000 vertices, 8,433 edges)
- 10000EWG.txt (10,000 vertices, 61,731 edges)
- largeEWG.txt (one million vertices, 7,586,063 edges)