blog-static/code/cs325-langs/hws/hw9.txt

167 lines
5.2 KiB
Plaintext
Raw Permalink Normal View History

2019-12-27 23:18:00 -08:00
CS 325, Algorithms, Fall 2019
HW9 - Graphs (part 2), DP (part 4)
Due Monday Nov 25, 11:59pm.
No late submission will be accepted.
Include in your submission: report.txt, dijkstra.py, nbest.py.
dijkstra.py will be graded for correctness (1%).
Textbooks for References:
[1] CLRS Ch. 22 (graph)
[2] my DP tutorial (up to page 16):
http://web.engr.oregonstate.edu/~huanlian/slides/COLING-tutorial-anim.pdf
[3] DPV Ch. 3, 4.2, 4.4, 4.7, 6 (Dasgupta, Papadimitriou, Vazirani)
https://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf
https://www.cs.berkeley.edu/~vazirani/algorithms/chap4.pdf
https://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
[4] KT Ch. 6 (DP)
http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdf
[5] KT slides: Greedy II (Dijkstra)
http://www.cs.princeton.edu/~wayne/kleinberg-tardos/
***Please answer time/space complexities for each problem in report.txt.
1. [WILL BE GRADED]
Dijkstra (see CLRS 24.3 and DPV 4.4)
Given an undirected graph, find the shortest path from source (node 0)
to target (node n-1).
Edge weights are guaranteed to be non-negative, since Dijkstra doesn't work
with negative weights, e.g.
3
0 ------ 1
\ /
2 \ / -2
\/
2
in this example, Dijkstra would return length 2 (path 0-2),
but path 0-1-2 is better (length 1).
For example (return a pair of shortest-distance and shortest-path):
1
0 ------ 1
\ / \
5 \ /1 \6
\/ 2 \
2 ------ 3
>>> shortest(4, [(0,1,1), (0,2,5), (1,2,1), (2,3,2), (1,3,6)])
(4, [0,1,2,3])
If the target node (n-1) is unreachable from the source (0),
return None:
>>> shortest(5, [(0,1,1), (0,2,5), (1,2,1), (2,3,2), (1,3,6)])
None
Another example:
1 1
0-----1 2-----3
>>> shortest(4, [(0,1,1), (2,3,1)])
None
Tiebreaking: arbitrary. Any shortest path would do.
Filename: dijkstra.py
Hint: please use heapdict from here:
https://raw.githubusercontent.com/DanielStutzbach/heapdict/master/heapdict.py
>>> from heapdict import heapdict
>>> h = heapdict()
>>> h['a'] = 3
>>> h['b'] = 1
>>> h.peekitem()
('b', 1)
>>> h['a'] = 0
>>> h.peekitem()
('a', 0)
>>> h.popitem()
('a', 0)
>>> len(h)
1
>>> 'a' in h
False
>>> 'b' in h
True
You don't need to submit heapdict.py; we have it in our grader.
2. [Redo the nbest question from Midterm, preparing for HW10 part 3]
Given k pairs of lists A_i and B_i (0 <= i < k), each with n sorted numbers,
find the n smallest pairs in all the (k n^2) pairs.
We say (x,y) < (x', y') if and only if x+y < x'+y'.
Tie-breaking: lexicographical (i.e., prefer smaller x).
You can base your code on the skeleton from the Midterm:
from heapq import heappush, heappop
def nbest(ABs): # no need to pass in k or n
k = len(ABs)
n = len(ABs[0][0])
def trypush(i, p, q): # push pair (A_i,p, B_i,q) if possible
A, B = ABs[i] # A_i, B_i
if p < n and q < n and ______________________________:
heappush(h, (________________, i, p, q, (A[p],B[q])))
used.add((i, p, q))
h, used = ___________________ # initialize
for i in range(k): # NEED TO OPTIMIZE
trypush(______________)
for _ in range(n):
_, i, p, q, pair = ________________
yield pair # return the next pair (in a lazy list)
_______________________
_______________________
But recall we had two optimizations to speed up the first for-loop (queue initialization):
(1) using heapify instead of k initial pushes. You need to implement this (very easy).
(2) using qselect to choose top n out of the k bests. This one is OPTIONAL.
Analyze the time complexity for the version you implemented.
>>> list(nbest([([1,2,4], [2,3,5]), ([0,2,4], [3,4,5])]))
[(0, 3), (1, 2), (0, 4)]
>>> list(nbest([([-1,2],[1,4]), ([0,2],[3,4]), ([0,1],[4,6]), ([-1,2],[1,5])]))
[(-1, 1), (-1, 1)]
>>> list(nbest([([5,6,10,14],[3,5,10,14]),([2,7,9,11],[3,8,12,16]),([1,3,8,10],[5,9,10,11]),([1,2,3,5],[3,4,9,10]),([4,5,9,10],[2,4,6,11]),([4,6,10,13],[2,3,5,9]),([3,7,10,12],[1,2,5,10]),([5,9,14,15],[4,8,13,14])]))
[(1, 3), (3, 1), (1, 4), (2, 3)]
>>> list(nbest([([1,6,8,13],[5,8,11,12]),([1,2,3,5],[5,9,11,13]),([3,5,7,10],[4,6,7,11]),([1,4,7,8],[4,9,11,15]),([4,8,10,13],[4,6,10,11]),([4,8,12,15],[5,10,11,13]),([2,3,4,8],[4,7,11,15]),([4,5,10,15],[5,6,7,8])]))
[(1, 4), (1, 5), (1, 5), (2, 4)]
This problem prepares you for the hardest question in HW10 (part 3).
Filename: nbest.py
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. 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.