CS 758/858: Introduction to Algorithms
(Coordinator: Wheeler Ruml)
An introduction to important concepts in the design and analysis of algorithms and data structures, including implementation, complexity analysis, and proofs of correctness. Prereq: CS 515 and CS 659.
- This course is one of the CS electives designated as theory.
- This course can be taken as CS758H by honors students.
- principles of data structures: students understand and can implement fundamental data structures
- fundamental computer science algorithms: students understand and can implement a range of fundamental algorithms
- principles and techniques of calculus, probability and statistics, and mathematical proof techniques: students can prove time and space complexity of algorithms and NP-completeness of problems
- think abstractly and reason logically about computer science problems: students can analyze the tie and space complexity of algorithms and the NP-completeness of problems, students can choose data structures appropriately, students can design simple algorithms for new problems
Fourteen assignments (80%) and two exams (20%).
- radix sort
- binary trees
- red-black trees, including deletion
- dynamic programming
- greedy algorithms
- union-find, connected components
- spanning trees
- shortest paths
- network flow
- SAT, clique, and other examples
Coping with complexity:
Cormen et al. Introduction to Algorithms, MIT Press, 2009.
Kernighan and Ritchie. The C Programming Language, second edition, Prentice-Hall, 1989.