Algorithms and Computing Theory

Catalog description

The purpose of this course is to acquire a thorough grounding in the core principles and foundations of computer science, building upon the knowledge gained in the prereq course of Algorithms and Data Structures. Students will learn methods for expressing and comparing algorithm complexity (worst- and average-case upper bounds, lower bounds) as well as to verify correctness. Algorithm-design techniques (divide-and-conquer, dynamic programming) as well as data structures (trees, heaps, graphs) widely used in modern software development will be studied. The knowledge gained will be applied to a variety of practical problems, such as sorting (in linear time), selection by rank, and graph problems (shortest paths, minimum spanning trees). The question of what problems are hard to compute will be addressed with an introduction to NP-completeness theory, including the development of the NP-complete classification and the identification of NP-hard problems by reductions.