CS 514, Algorithms, Spring 2024
HW5 - DP (part 1: simple)
Due Tuesday 5/7, 9:59pm.
No late submission will be accepted.
Need to submit report.txt, mis.py, bsts.py, bitstrings.py.
mis.py will be graded for correctness (1%).
To submit:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw5 report.txt {mis,bsts,bitstrings}.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 hw5
Textbooks for References:
[1] DP 101 slides
[2] H 2.1 (will be available around 5/3)
[3] CLRS Ch. 15
[4] KT Ch. 6
or Ch. 5 in a previous version:
http://cs.furman.edu/~chealy/cs361/kleinbergbook.pdf
0. (Optional) Is Fibonacci REALLY O(n)?
Hint: the value of f(n) itself grows exponentially.
1. Number of bit strings of length n that has
1) no two consecutive 0s.
2) two consecutive 0s.
>>> num_no(3)
5
>>> num_yes(3)
3
[HINT] There are three 3-bit 0/1-strings that have two consecutive 0s.
001 100 000
The other five 3-bit 0/1-strings have no two consecutive 0s:
010 011 101 110 111
Feel free to choose any implementation style.
Filename: bitstrings.py
[HINT] Like problem 1, you can also use the O(2^n) exhaustive search method to verify your answer.
2. [WILL BE GRADED]
Maximum Weighted Independent Set
[HINT] independent set is a set where no two numbers are neighbors in the original list.
see also https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
input: a list of numbers (could be negative)
output: a pair of the max sum and the list of numbers chosen
>>> max_wis([7,8,5])
(12, [7,5])
>>> max_wis([-1,8,10])
(10, [10])
>>> max_wis([])
(0, [])
[HINT] if all numbers are negative, the optimal solution is 0,
since [] is an independent set according to the definition above.
>>> max_wis([-5, -1, -4])
(0, [])
Q: What's the complexity?
Include both top-down (max_wis2()) and bottom-up (max_wis()) solutions,
and make sure they produce exact same results.
We'll only grade the bottom-up version (which is slightly faster).
Tie-breaking: any best solution is considered correct.
Filename: mis.py
[HINT] you can also use the naive O(2^n) exhaustive search method to verify your answer.
3. Number of n-node BSTs
input: n
output: number of n-node BSTs
>>> bsts(2)
2
>>> bsts(3)
5
>>> bsts(5)
42
[HINT] There are two 2-node BSTs:
2 1
/ \
1 2
Note that all other 2-node BSTs are *isomorphic* to either one.
Qa: What's the complexity of this DP?
Qb: What's the name of this famous number series?
Feel free to use any implementation style.
Filename: bsts.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.