Lecture Notes and Further Reading
The notes posted here are somehow sparse. They are (hopefully) a good summary for later reference but are by no
means a substitute for the actual lectures and/or the textbook.
- Introduction to the design and analysis of algorithms ( handout and overhead presentation). These
notes offer an overview of the basics of algorithm design and analysis; most of this material will be
reconsidered in more details as we move through the course.
The notes roughly correspond to Chapter 0 of the textbook. This chapter is definitely worth reading
as it discusses a few things not covered here (such as what is not an algorithm).
- Asymptotic order notations ( handout and overhead presentation). This matter is considered already
known in many algorithms textbooks including our primary textbook. The other two recommended
textbooks do contains a summary of the order notations (Cormen addresses this matter in Chapter 3
and Neapolitan in Chapter 1). Check out Moodle for more reading.
- Counting Steps and Recurrence Relations ( handout and overhead presentation). Here is a detailed
and rigorous step counting for the iterative binary search algorithm. This is mostly dedicated to
solving recurrence relations, which is in turn necessary when analyzing the performance of recursive
algorithms. The second part of this presentation is probably overkill for the purpose of the rest of the
course (and also real life). A more practical replacement would be Section 1.7 from the textbook.
Most of the presentation is according to Neapolitan’s Appendix B (which also offers proofs for most
of the theorems used).
- Correctness ( handout and overhead presentation). This section provides a brief introduction into
proofs of correctness. We will discuss correctness or our algorithms so keep this all in mind as we
more along.
I do not have a concise reference for this part, but note that most algorithms that we will see later
come in your textbook with arguments of correctness. Cormen is even more strict; in that textbook
everything is formally proven correct.
- Data Structures ( handout and overhead presentation). You are supposed to be familiar with many
data structures, the most important ones being summarized (though not defined of analyzed) here. In
addition, we also talk about disjoint sets and graphs, which will become useful later on.
Disjoint sets are defined in Cormen’s Chapter 19. Notice the use of a linked list instead of array, but
also notice that the basic algorithms and their properties are the same. Graphs are nicely introduced
in Cormen’s Chapter 20. Check out Moodle for details.
- Divide and conquer ( handout and overhead presentation). This is one of the most spectacular (i.e.,
simple and effective) technique of algorithm design, just keep in mind that it is not going to work
everywhere.
Divide and conquer is covered (though strangely enough not explicitly named) in Chapter 1 of the
textbook. The lower bound for comparison sorting is explained in many places, see e.g. Cormen.
- The greedy technique ( handout and overhead presentation). Yet another simple and effective
technique when it works (namely, when the problem has the greedy choice property).
Minimum-cost spanning trees are covered in Chapter 7 of the textbook, including some entertaining
historical information. Dijkstra’s algorithm is covered in Chapter 8 of the textbook, which also contains
additional information well worth reading. More greedy algorithms (including Huffman codes) are
the subject of Chapter 4. The greedy approach to the knapsack problems is covered very briefly in
Cormen (Section 15.2); we will meet these problems again.
Lecture Recording
Lectures are recorded as follows:
Note that Lecture 12 was a recap and Q&A session for the first examination and so was not recorded.