CS 514, Analysis of Algorithms, Spring 2024

HW2 - Advanced Divide-n-Conquer: Recursion with byproduct
number of inversions, longest path in binary tree

Due Tuesday 4/16, 9:59pm (same submission instructions as HW1).
No late submission will be accepted.

Need to submit: report.txt, msort.py, inversions.py, and longest.py.
longest.py will be graded for correctness (1%).

To submit:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw2 report.txt {msort,inversions,longest}.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 hw2


Textbooks for References:
[0] H 1.4, 1.5
[1] CLRS Ch. 2
[2] R 3.2

1. Implement mergesort.
   
   >>> mergesort([4, 2, 5, 1, 6, 3])
   [1, 2, 3, 4, 5, 6]   
   
   Filename: msort.py
   
2. Calculate the number of inversions in a list.
   Hints: Use mergesort and "recursion with byproduct".

   >>> num_inversions([4, 1, 3, 2])
   4
   >>> num_inversions([2, 4, 1, 3])
   3

   Filename: inversions.py

   Must run in O(nlogn) time.

3. [WILL BE GRADED]
   Length of the longest path (in number of edges) in a binary tree .
   
   We will use the "buggy qsort" representation of binary trees from HW1:
   [left_subtree, root, right_subtree]

   >>> longest([[], 1, []])
   0

   >>> longest([[[], 1, []], 2, [[], 3, []]])
   2

   >>> longest([[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[], 7, [[], 9, []]]]])
   5

   Note the answer is 5 because the longest path is 1-2-4-6-7-9.   
   Hint: Do NOT write a separate function for height (i.e., depth). Use "recursion with byproduct".
   	 Write only one (helper) function that returns both the longest path length and the height.

   Filename: longest.py
   Must run in O(n) time.

   [ADDED] Analyze the complexity for the BAD version with separate longest() and depth() functions:

   	   def longest(tree):
       	       ... longest(...) ...
       	       ... depth(...) ...    # longest() calls both longest() and depth()
       
	   def depth(tree):
       	       ... depth(...) ...    # depth() just calls depth()


Debriefing (required!): --------------------------

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?
   Note you are encouraged to discuss with your classmates, 
   but each students should submit his/her own code.
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.