[next] [prev] [prev-tail] [tail] [up]

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.

  1. 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).
  2. 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.
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.

[next] [prev] [prev-tail] [front] [up]