CS 514, Algorithms, Spring 2024
HW8 - Graphs (part I); DP (part III)
Due on Tuesday May 28, 9:59pm.
No late submission will be accepted.
Include in your submission: report.txt, traversal.py, topol.py, viterbi.py.
viterbi.py will be graded for correctness (1%).
To submit:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw8 report.txt {traversal,topol,viterbi}.py
(You can submit each file separately, or submit them together.)
To see your best results so far:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/query 514 hw8
Textbooks for References:
[1] CLRS Ch. 23 (Elementary Graph Algorithms)
[2] KT Ch. 3 (graphs), or Ch. 2 in this earlier version:
http://cs.furman.edu/~chealy/cs361/kleinbergbook.pdf
[3] KT slides (highly recommend!):
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/03Graphs.pdf
[4] Jeff Erickson: Ch. 5 (Basic Graph Algorithms):
http://jeffe.cs.illinois.edu/teaching/algorithms/book/05-graphs.pdf
[5] DPV Ch. 3, 4.2, 4.4, 4.7 (Dasgupta, Papadimitriou, Vazirani)
https://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf (decomposition of graphs)
https://www.cs.berkeley.edu/~vazirani/algorithms/chap4.pdf (paths, shortest paths)
[6] my advanced DP tutorial (up to page 16):
http://web.engr.oregonstate.edu/~huanlian/slides/COLING-tutorial-anim.pdf
Please answer non-coding questions in report.txt.
0. For the following graphs, decide whether they are
(1) directed or undirected, (2) dense or sparse, and (3) cyclic or acyclic:
(a) Facebook
(b) Twitter
(c) a family
(d) V=airports, E=direct_flights
(e) a mesh
(f) V=courses, E=prerequisites
(g) a tree
(h) V=linux_software_packages, E=dependencies
(i) DP subproblems for 0-1 knapsack
Can you name a very big dense graph?
1. BFS and DFS
Implement both BFS and DFS for directed graph.
bfs(n, edges) and dfs(n, edges) where nodes are 0...(n-1) and edges is a list of (u, v) pairs.
e.g., for the following example:
0 --> 1 --> 2 --> 3
| v
+---> 4 --> 5
>>> bfs(6, [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (3, 5)])
[0, 1, 2, 4, 3, 5]
>>> dfs(6, [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5), (3, 5)])
[0, 1, 2, 3, 5, 4]
Filename: traversal.py
2. Topological Sort
For a given directed graph, output a topological order if it exists.
Tie-breaking: ARBITRARY tie-breaking. This will make the code
and time complexity analysis a lot easier.
e.g., for the following example:
0 --> 2 --> 3 --> 5 --> 6
/ \ | / \
/ \ v / \
1 > 4 > 7
>>> order(8, [(0,2), (1,2), (2,3), (2,4), (3,4), (3,5), (4,5), (5,6), (5,7)])
[0, 1, 2, 3, 4, 5, 6, 7]
Note that order() takes two arguments, n and list_of_edges,
where n specifies that the nodes are named 0..(n-1).
If we flip the (3,4) edge:
>>> order(8, [(0,2), (1,2), (2,3), (2,4), (4,3), (3,5), (4,5), (5,6), (5,7)])
[0, 1, 2, 4, 3, 5, 6, 7]
If there is a cycle, return None
>>> order(4, [(0,1), (1,2), (2,1), (2,3)])
None
Other cases:
>>> order(5, [(0,1), (1,2), (2,3), (3,4)])
[0, 1, 2, 3, 4]
>>> order(5, [])
[0, 1, 2, 3, 4] # could be any order
>>> order(3, [(1,2), (2,1)])
None
>>> order(1, [(0,0)]) # self-loop
None
Tie-breaking: arbitrary (any valid topological order is fine).
You need to implement both versions:
- bottom-up (BFS): order(n, edges)
- top-down (DFS from n-1), order2(n, edges)
filename: topol.py
questions:
(a) did you realize that bottom-up implementations of DP use (implicit) topological orderings?
e.g., what is the topological ordering in your (or my) bottom-up bounded knapsack code?
(b) what about top-down implementations of DP? what order do they use to traverse the graph?
3. [WILL BE GRADED]
Viterbi Algorithm For Longest Path in DAG (see DPV 4.7, [2], CLRS problem 15-1)
Recall that the Viterbi algorithm has just two steps:
a) get a topological order (use problem 1 above)
b) follow that order, and do either forward or backward updates
This algorithm captures all DP problems on DAGs, for example,
longest path, shortest path, number of paths, etc.
In this problem, given a DAG (guaranteed acyclic!), output a pair (l, p)
where l is the length of the longest path (number of edges), and p is the path. (you can think of each edge being unit cost)
e.g., for the above example:
>>> longest(8, [(0,2), (1,2), (2,3), (2,4), (3,4), (3,5), (4,5), (5,6), (5,7)])
(5, [0, 2, 3, 4, 5, 6])
>>> longest(8, [(0,2), (1,2), (2,3), (2,4), (4,3), (3,5), (4,5), (5,6), (5,7)])
(5, [0, 2, 4, 3, 5, 6])
>>> longest(8, [(0,1), (0,2), (1,2), (2,3), (2,4), (4,3), (3,5), (4,5), (5,6), (5,7), (6,7)])
(7, [0, 1, 2, 4, 3, 5, 6, 7]) # unique answer
Note that longest() takes two arguments, n and list_of_edges,
where n specifies that the nodes are named 0..(n-1).
Tie-breaking: arbitrary. any longest path is fine.
Filename: viterbi.py
Note: you can use this program to solve MIS, knapsacks, coins, etc.
Debriefing (required!): --------------------------
0. What's your name?
1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. Did you work on it mostly alone, or mostly with other people?
4. How deeply do you feel you understand the material it covers (0%-100%)?
5. Take a moment to reflect on your midterm performance; separate the data structures and DP parts.
Now, do you understand all the problems you didn't solve correctly?
6. Any other comments?
This section is intended to help us calibrate the homework assignments.
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.