CS 325, Algorithms, Spring 2023
HW9 - Graphs (part 2), DP (part 4)

Due Monday June 5, 11:59pm. 
No late submission will be accepted.

Include in your submission: report.txt, dijkstra.py.
dijkstra.py will be graded for correctness (1%).

NOTE: This HW is smaller than normal because you need to start HW10 (6%) early.

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: you need a priority queue implementation that supports the classical "Decrease-Key" operation in textbooks. Unfortunately, most implementations (Python's heapq and C++/Java's) do not support it, because you need to combine a hash table (dict) and a priority queue, which is non-trivial. Luckily, there are several very good implemenations in Python:

   [1] heapdict:
   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

   [2] pqdict:
   https://github.com/nvictus/priority-queue-dictionary

   You can also use:
   https://classes.engr.oregonstate.edu/eecs/spring2023/cs325-001/hw9/pqdict.py

   from pqdict import pqdict

   [3] priority_dict:
   https://gist.github.com/matteodellamico/4451520#file-priority_dict-py

   Note: this is depecrated (Python2), and I've converted it to Python3 and made a few other changes to make the interface identical to heapdict and pqdict; please use:

   https://classes.engr.oregonstate.edu/eecs/spring2023/cs325-001/hw9/priority_dict.py

   from priority_dict import priority_dict


   They all share the exact same interface; you can use any one in your code (all these tools are installed in the grader).

   Speed: priority_dict < pqdict << heapdict ("<" means faster)   

   Q: What if you only have heapq, can you still make Dijkstra work (with the built-in heapq)? 
      Can you re-analyze the time/space complexities?

   Q: Is Dijkstra a greedy algorithm or dynamic programming algorithm?
      Most textbooks (such as KT and CLRS) classify it as a greedy algorithm,
      but some people have different opinions, e.g.:

      (a) https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Dynamic_programming_perspective
      (b) Dijkstra's algorithm revisited: the dynamic programming connexion, by M. Sniedovich (2006):
      http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf
      (c) https://www.quora.com/Is-Dijkstras-Algorithm-a-greedy-algorithm-or-a-dynamic-programming-algorithm
      (d) https://aclanthology.org/C08-5001.pdf
      
      What do you think?

   Q: for problems that can be solved by both Dijkstra and Viterbi, which one is faster? 


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. If you've passed all testcases, how many attempts did you use?
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.