Prerequisites

One of our main references this semester will be Jeff Erickson’s book on Algorithms, which is freely available (legally!). Jeff has some nice things to say about how you should think of algorithms. Start with Chapter 0: Introduction. We recommend that you read it before our first class since it is an accessible introduction to thinking about algorithms and what a complete description of an algorithm entails. The specific algorithms and historical commentary in this chapter aren't considered course content that you need to know, but you may find them familiar and entertaining.

Algorithms and their analyses may involve formal mathematics and are written to be understood by others. They utilize data structures and are implemented in programming languages, such as Java or Python.

For that reason, CS 201 (Data Structures & Algorithms) and CS 230 (Discrete Mathematics), or its approved substitutes, are prerequisites for this class. This document is intended to provide a few specific details about what we expect you to know from those classes. We provide a non-exhaustive list of resources you may find helpful to brush up on a previous topic.

Data Structures & Algorithms

You should be familiar with the content of a course like CS 201 (Data Structures & Algorithms). The most recent offerings by Professors Astrachan and Nemecek in fall 2025 can be accessed here, including notes and lecture recordings. In addition to programming (see the section below) we expect you to have gained some familiarity with the following topics. If you need to brush up, you can follow the references from the free online Open Data Structures book (hereafter ODS), by Pat Morin. ODS comes in multiple editions, including both a pseudocode/Python version and a Java version. See the direct links to the corresponding chapters in the list of topics below. See also the [CLRS] reference book (Introduction to Algorithms) also discusses many of these topics and can be found under Files on Canvas.

Things we expect you to have seen before include:

• Arrays and Array-based Lists. See ODS Chapter 2 (Python, Java).
• Linked Lists. See ODS Chapter 3 (Python, Java).
• Binary Heaps, the standard implementation of a Priority Queue. See ODS Chapter 10 (Python, Java).
• Binary Search Trees (normal/unbalanced and balanced). Note that the implementation details of self-balancing trees are not expected. See ODS Chapter 6 (Python, Java) and ODS Chapter 10 (Python, Java).
• Adjacency Lists and Matrices for Graphs. See ODS Chapter 12 (Python, Java).
• Basic Hashing: Including that hash table operations are NOT worst-case $O(1)$ complexity without further assumptions. See ODS Chapter 5 (Python, Java).
• Sorting: At least one quadratic $O(n^2)$ algorithm (likely insertion sort or selection sort) and at least one $O(n\log (n))$- time algorithm (likely mergesort). See ODS Chapter 11 (Python, Java).

Discrete Mathematics

You should be familiar with the content of a course like CS 230 (Discrete Mathematics) . Here is the version Professor Munagala taught in Spring 2023. If you need to brush up, we will provide additional references from the free online An Active Introduction to Discrete Mathematics and Algorithms book by Charles Cusack (hereafter Cusack). Additional resources include Alex Brandt's Discrete Structures for Computing and Mathematics for Computer Science by Lehman, Leighton, and Meyer (hence some refer to this book as [LLM]).

Things we expect you to have seen before include:

• Asymptotic Analysis and Notation. See Chapter 7 of Cusack.
• Sets and Functions. See Chapter 4 of Cusack and Chapter 2 of Brandt.
• Proofs, especially by induction. See Chapters 2 and 8.1 of Cusack and Chapters 1.3 and 5.1 of Brandt.
• Recursion and Recurrence relations. See Chapters 8.2 and 8.3 of Cusack and Chapter 5.2 of Brandt.
• Sequences and Summations. See Chapter 6 of Cusack and Chapter 3.2 of Brandt.
• Graphs: See Chapter 10 of Cusack and Chapter 7 of Brandt.
• Counting and Probability: See Chapters 18 and 19 of [LLM] and Chapter 6 of Brandt.

Programming

While this course certainly involves implementing algorithms in programming languages and analyzing their empirical performance, this course is not about programming itself. We expect that you are already comfortable with programming, having taken a minimum of two semesters of programming (for example, CS 101 and CS 201) or equivalent.

Specifically, we expect you to be comfortable in at least one of Python 3 or Java and able to look up language documentation as needed. We will not teach these languages nor cover language-specific concepts in class, and hence these details will never be topics for exams.

For either language, we expect only familiarity with their standard libraries and writing code in an editor of your choice (we recommend Visual Studio Code for both). Python and Java have lots of external libraries (e.g., NumPy and pandas in Python), but you do not need to have any knowledge of or experience with them. Typically, our applied/coding homework problems do not allow external packages but you can use anything in the standard libraries. Any exceptions to this will be clearly noted on the assignments, and if a particular package is to be used (e.g., NetworkX when working with graphs), documentation will be provided.

If you need to brush up on Python or Java, there are many free resources on the web.

Python vs. Java

We recommend that you use the language you are most comfortable and/or interested in using; the choice is entirely up to you and you can choose to use either language on all applied homework problems. (If you are indifferent, for what it is worth, Python is preferred 3-4x over Java in recent semesters.)

There are too many freely available and excellent resources about these languages on the web. We point to a few below:

• Python
  • Python 3.x standard library docs
  • The Python Tutorial
  • A Byte of Python
• Java
  • Oracle's Java Tutorials
  • dev.java tutorials
  • Java standard library docs