CS 758/858: Introduction to Algorithms

(Coordinator: Wheeler Ruml)

Catalog description

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.

Attributes

  • This course is one of the CS electives designated as theory.
  • This course can be taken as CS758H by honors students.

Outcomes

  • 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

Evaluation

Fourteen assignments (80%) and two exams (20%).

Topics

  • Sorting:
    • radix sort
  • Searching:
    • heaps
    • hashing
    • binary trees
    • red-black trees, including deletion
    • tries
  • Optimization:
    • dynamic programming
    • greedy algorithms
  • Graphs:
    • traversal
    • union-find, connected components
    • spanning trees
    • shortest paths
    • network flow
  • Complexity:
    • NP-completeness
    • SAT, clique, and other examples
    • undecidability
  • Coping with complexity:
    • approximation
    • backtracking

Textbooks

  • Cormen et al. Introduction to Algorithms, MIT Press, 2009.

  • Kernighan and Ritchie. The C Programming Language, second edition, Prentice-Hall, 1989.