Algorithms

We start with the fundamentals including asymptotic notations, basic efficiency classes, mathematical analysis of recursive and non-recursive algorithms. We then study divide-and-conquer techniques (quick-sort, binary search, matrix multiplication, convex-hull problems), decrease-and-conquer (depth/breadth first search, topological sort), transform-and-conquer (Gaussian elimination, balanced trees, heaps), dynamic programming (Binomial coefficients, Warshall's and Floyd's algorithm, knapsack problem, optimal matrix multiplication order), string matching, hashing, greedy techniques (Prim's algorithm, Kruskal's algorithm, Dijkstra's Algorithm, Huffman trees). The last two weeks of the semester is an introduction of basic computability (tractability, P/NP/NP-complete classes).

• [Ali] Rats, that was not a good example. Sorry guys, I'm an idiot.
• [Greg] No, no, don't say that. We're all idiots.