• CS4040/5040

• Insertion Sort

• Maximum Subarray

  1. Theta(n lg(n))

• Merge Sort, Divide and Conquer

  1. O(n lg(n)),
  2. Divid and conquer

• Master Method

  1. If we can separate the problem as b pieces, and each piece use a time to process and with f(n) extra time, then we compare (log_b a) with f(n). 1) if (log_b a) > f(n), then complexity is Theta(log_b a); 2) if (log_b a) = f(n) then Theta(f(n)*lgn); 3) if (log_b a) < f(n), then Theta(f(n)).

• Heap representation

  1. Max-Heap: The node equal or greater than its children. So the order is not completely sorted.
  2. Build the Max-Heap: O(n).
  3. Sorting by Max-Heap: O(n log(n)).

• Quick Sort

  1. Differences with Merge Sort: Merge sort just separate the list as two, Quick Sort separate the list as greater than a number and smaller than a number.
  2. Divid and conquer

• Counting Sort

  1. O(r+n), r is the largest number in the list.

• Radix Sort

• Find i th number

  1. Use Quick sort, and only process the part which contain the i th number.
  2. In Dr.Juedes's lecture notes, 1. find the median in Theta(n) time, 2. Then use this median to separate the two parts in O(n) time. But how to find median in Theta(n) time?
  3. A better separation strategy: Separate the whole list as 5 pieces and sort separately and then choose the medium of the 5 mediums as the k to separate the whole lists. And then to the rest list part which contain the i th number, do this again. The complexity is Theta(n).

• Closest Pair problem

  1. O(nlgn)
  2. Recursively solve it. Each recursive step is: 1) find the minimal closest pair of left side and the closest pair of right side and the shortest distance is D. Then use this D try to find any pair between left part and right part. Because the possible points are close to the middle line and the most large distance is D. So for the left points the possible close points are in a D*2D rectangle. So for left potential points just search the right rectangle and calculate the distance.

• MST problem, Greedy method

  1. Two Greedy methods.
     1. Kruskal's method: O(ElgE)
     2. Prime's method: O(ElgV)

• Shortest Path problem, Dijkstra's algorithm

• Fractional Knapsack problem, Greedy method

• 0/1 Knapsack problem, Dynamic programming

• Matrix Chain Multiplication

  1. O(n^3)

• Longest Common Sub-sequence, Dynamic programming

  1. O(nm)

• Coin change problem, Dynamic programming

  1. O(nk), k is the value need to change, n is the number of coin types.

• All-Pairs Shortest Paths, Dynamic programming

  1. O(n^3).
  2. A table contain all initial distances of two vertex, check if they can go through vertex i1 , the distance will becomes smaller or not; Then check go through i2, then i3...

• P VS. NP

  1. Decision problem, optimization problem
  2. Prove a problem is NPC
     1. If a problem is NP, and also NP-hard, then it is NPC
     2. So we need to prove 1) the problem is NP, 2) the problem is NP-hard.
     3. The problem is NP <==> given a solution we can verify it in polynomial time.
     4. The problem is NP-hard: a exist NPC problem can be polynomial reduce to the target problem. Assume we know how to solve the target problem. Then polynomial reduction need several elements: 1) for a input of the NPC problem, transfer it to the input of target problem, 2) prove it works, 3) prove the reduction is polynomial.
     5. For the 2) prove it works, we have two parts: 1) prove when the target problem is yes, the NPC problem is yes, 2) prove the target problem is no, the NPC problem is no. But usually we don't do the 2) directly. We prove NPC problem is yes, the target problem is also yes instead.
  3. Polynomial reduction of NPC

20. Useful materiels

i. Dynamic Programming [https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/](https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/]
ii. Greedy algorithm [https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/]
iii. Greedy algorithm (first part) [https://www.topcoder.com/community/data-science/data-science-tutorials/greedy-is-good/]