CS320 Algorithms - Theory and Practice, Spring '17, Frederick   

Policies  ·  Schedule  ·  Syllabus

Instructor: Teaching Assistant: Textbook: Prerequisites: Lectures

Course Goals

The course is about learning and practicing principles for organizing your thinking when solving programming problems, and not about memorizing details and facts. You must practice ways of establishing that an algorithm is correct and anlyzing its time bound. Getting good at these skills will allow you to come up with efficient algorithms of your own, by figuring out what steps are needed in the pseudocode or program code to get the proof of correctness to go through, or to reduce the running time. You will also learn to recognize what kinds of optimizations on a program are a waste of time, as they will have little or no impact on the running time of the program as a whole.

We will study big-O analysis at a more advanced level than in CS200; algorithms of unlabeled graphs, including mathematical properties of depth-first search, how to recognize bipartite graphs, topological sort, finding strongly-connected components; various examples of greedy algorithms and greedy proofs; examples of the divide-and-conquer strategy and techniques for bounding running times of divide-and-conquer algorithms; dynamic programming; NP-completeness.