1.2. Prerequisites

A discussion of advanced algorithms needs as a foundation a solid understanding of basic algorithmic concepts, as covered in CSCI 3110.

In terms of specific problems and algorithms to solve them, the prerequisites for this course are fairly modest. I assume that you know about sorting, selection, and binary search and understand the algorithms that solve these problems. I also expect you to know about basic graph traversals (BFS and DFS), their cost, and the type of problems they can be used to solve. Finally, I assume that you know what a minimum spannning tree or shortest path tree is, along with algorithms to compute them (Bellman-Ford, Ford-Fulkerson, Dijkstra, Prim, Kruskal). Any other algorithms needed as building blocks of algorithms discussed in this course are introduced as needed.

I assume a greater degree of preparedness in terms of your comfort with simply talking about algorithmic problems. You should have a solid understanding of and be able to comfortably work with \(O\)-, \(\Omega\)-, \(\Theta\)-, \(o\)-, and \(\omega\)-notation and you should have an appreciation for the need for formalism and rigour in describing algorithms and in arguing about their correctness and running times. Having said that, I will often appeal to your intuition about various algorithmic questions and will implicitly assume that you are able to translate this intuition into formal arguments.

As far as algorithmic techniques go, divide and conquer should be your bread and butter and you should be comfortable with greedy algorithms and dynamic programming, as they will be used extensively in this course to solve various subproblems in approximate and exact solutions to NP-hard problems.

If you cannot put a checkmark beside each of these topics, now is the time to open your CSCI 3110 textbook (most likely Cormen et al. or Kleinberg/Tardos) and refresh your memory on these topics.