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.