9 Midterm Notes

It was kinda hard for me.

It asked about the hoffman encoding, which I forgot for the most part, except the fact you need to split into two groups of the variables to encode. It asked for two algorithms that can detect negative weight cycles, which I answered Bellman-Ford and Floyd-Warshall. It's to be seen if i'm correct. It asked for a greedy proof, which I think I got; it was for minimizing the total average cost, where the avg cost is computed at each i as i increases to n. The next question asked for an algorithm that can determine the number of intersections of lines in a box. I answered some type of mergesort, although I didn't have time to code it out. Got stuck for a while :. It proceeded to ask for a DP solution the maximum subarray problem, which I think i got although I didnt clarify it properly, the recurrence cases depended on value i didn't explicitly calculate anywhere. Don't think that one went too well. Last one (i think) asked for a DP solution to a crazy graph, where you need to find the independence set of nodes with the maximum value. Barely answered the first question proving a greedy algorithm is not optimal. Anyway, I can cr/ncr so nbd.