CSC 440: Design and Analysis of Algorithms is the upper-level undergraduate course on algorithms. I loosely use the "Berkeley" algorithms textbook ("Algorithms" by Dasgupta, Papadimitriou, and Vazirani) as opposed to the "MIT" textbook (CLRS, which is an excellent reference). This course is oriented around algorithm design techniques for most of the semester: divide and conquer, graph algorithms, greedy algorithms, dynamic programming, and network flow, followed by some time devoted to complexity theory (as URI does not require Theory of Computation as a requirement for the CS major). Recurring themes include invariants (loop and representation, as a tool for proving implementation correctness and termination), complexity analysis, and empirical computer science (benchmarking and analysis of implementations). Students write several implementations of algorithm design techniques.

A selection of assignments:

• Intro (Invariants)
• Convex Hull (Divide & Conquer)
• Rubik's Cube (Graph Algorithms)
• Huffman Coding (Greedy)
• Seam Carving (Dynamic Programming)