CSC 510/810: ANALYSIS OF ALGORITHMS I AND II

CSC 510 is an upper-division undergraduate core course on the design and analysis of algorithms. In this class, we will learn about major design methodologies for algorithms and how to apply them to designing algorithms for solving new problems, proving correctness and determining runtime of algorithms, and classic graph algorithms.

CSC 810 is the graduate version of the class, which covers the above material in more depth, in addition to some advanced topics, such as loop invariants, network flows, and hardness results. Slides below marked with an asterisk (*) indicate that some of the slides are only used for 810.

Review from previous courses, e.g. discrete math and data structures:

• Big-O Notation
• Pseudocode and Analyzing Runtime
• Proof by Induction
• Priority Queues and Heaps

Main course materials:

• Divide and Conquer
• Recursion and Divide-and-Conquer*
• Recursion Trees and the Master Theorem*
• Recursive Arithmetic*
• Backtracking
• Backtracking*
• More Backtracking Examples*
• Dynamic Programming*
• More Dynamic Programming*
• Greedy Algorithms
• Graph Algorithms
• Graph Representations
• Depth-First Search*
• Minimum Spanning Trees
• Shortest Paths

Topics exclusive to 810:

• Loop Invariants
• Network Flows
• Lower Bounds
• NP-Completeness
• Approximation Algorithms