CS 320 provides an introduction to algorithms, their correctness proofs, their complexity, algorithm classes, problems and problem classes.

The course is about learning and practicing principles for organizing your thinking when solving programming problems. Mastering these skills will allow you to discover and invent efficient algorithms of your own, by figuring out what steps are needed for correctness and to reduce running time. We will study a variety of subjects:

• Orders of magnitude
• Greedy algorithms and greedy proofs
• Tree and graph algorithms
• Depth-first, breadth-first search
• Bipartite graphs
• Topological sort
• Connected components
• Spanning trees and shortest paths, cycles
• Divide-and-conquer strategy and techniques for bounding running times of such algorithms
• Dynamic programming
• Dynamic multi-threading
• Reduction of one problem to another (polynomial time reduction)
• Problem classes (P, NP, NPC)