CSCI 422: Advanced Algorithms

by Gara Pruesse
Fall 2021

Course Outline

Course Motivation and overview
This course will cover a selection of subjects from algorithm design and analysis. Algorithms, and the data structuring they require, are the soul of computer science. One important job of the computer scientist is to understand the requirements for a proposed system and, if possible, come up with a way to get the computer to function as desired -- to solve the instances of the given problem, if and when possible. We may know a computer language inside and out, and know all the system utilities we need, and be adept at engineering good software design so the end result is maintainable and modifiable. But we are still left with the essential problem. We know how to tell the computer to take steps, but what steps, in what order, and under what logic, do we tell it to take, so that the output is guaranteed to be correct?

As a student in this fourth-year computer science course, you are by now familiar with many algorithms -- that is, you'll have seen the end result of other's inspired search for algorithmic solutions to computer science problems. Likely you will also have devised algorithms of your own. In this course we seek to develop algorithmic sophistication, by expanding the range and depth of understanding of classic and innovative algorithms with an emphasis on how to find the appropriate problem-solving paradigm for a given problem, and by offering opportunities for you to devise and analyse algorithms of your own.

The course includes a selection of the following topics. Some of these topics have already been introduced to the students in earlier courses, in which case we will be deepening and expanding on the problems and their solutions.


  1. Recursion
  2. Backtracking
  3. Dynamic Programming
  4. Greedy Algorithms
  5. Hashing
  6. Disjoint Sets ("union-find")
  7. Graph Algorithms
  8. Poset Algorithms
  9. NP-hardness

    Contact information, materials

    Timetable and assessment