Fall 2022
Instructor: Liang Huang
Course Website: https://classes.engr.oregonstate.edu/eecs/fall2022/cs514-001/
HW1:
- quick select (qselect.py)
- quick sort (qseort.py)
HW2:
- number of inversions of a list of numbers (invertsions.py)
- the length of the longest path in a tree (longest.py)
- merge sort (msort.py)
HW3:
- find k closest elements to val in a sorted list of size n (closest_sorted.py)
- find k closest elements to val in a unsorted list of size n (closest_unsorted.py)
- find all pairs of (x,y,z) such that x+y = z in the list (xyz.py)
HW4:
- given a very big datastream, find smallest k values in O(k) space (datastream.py)
- k-way mergesort (kmergesort.py)
- find all pairs (x,y) such that the following pairs (x,y) is 'smaller' that (x',y'). (nbest.py)
- Smaller := x+y < x'+y' and y < y'.
HW5:
- number of n-bit strings that match certain conditions. (bistrings.py)
- with '00' in it.
- without '00' in it.
- number of n-node bsts(bsts.py)
- maximum independent sets (mis.py)
HW6:
- unbounded Knapsack (knapsack_unbounded.py)
- bounded Knapsack (knapsack_bounded.py)
HW8:
- topological Sort (dijkstra.py)
- viterbi Algorithm (viterbi.py)
HW9:
- Dijkstra (topol.py)
- Traveling Salesman Problem (tsp.py) (skipped)
HW10:
- 1-best structure (rna.py)
- number of structures (rna.py)
- k-best structures (rna.py)