CS 514, Analysis of Algorithms, Spring 2026

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

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

Need to submit: 
1. msort.py (0.5 pts) -- whitebox grading on gradescope
2. inversions.py (0.5 pts) -- whitebox grading on gradescope
3. longest.py (1 pt) -- blackbox grading on gradescope
4. report -- on Google form: https://forms.gle/Ncf9MCzo9UByG3D2A

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

1. Implement mergesort. Make sure it runs in O(n \log n) time.
   
   >>> 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".
          Alternatively, you can also use quicksort.

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

   Filename: inversions.py

   Must run in O(n \log n) time.

3. [blackbox grading]
   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, see BAD version below). 
         Use "recursion with byproduct".
         Write only one function that returns both the longest path length and the height.

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

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

      def depth(tree):
          return 0 if tree == [] else max(depth(tree[0]), depth(tree[2])) + 1

      def longest(tree):
          return 0 if tree == [] else max(longest(tree[0]), longest(tree[2]), depth(tree[0]) + depth(tree[2]))


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.