Mapping the material covered in lectures to chapters
and pages of the textbook Kleinberg and Tardos:
Algorithm Design
The textbook contains about 90-95% of the material covered in lectures.
The very few missing items, such as the generalised Karatsuba algorithm,
are covered on lecture slides in detail and you do not need any other sources.
By their very nature, the lectures are more condensed than the textbook,
so you will find the textbook very useful to clarify any confusions you might
have. The textbook also contains many more examples and solved problems
as well as plenty of exercises for you to practice.
Note: while almost everything done in lectures is covered in the textbook,
the material is NOT in the same order. Also, the textbook contains the ma-
terial already covered in COMP2521 Data Structures and Algorithms, such
as BFS and DFS, the basic graph algorithms, sorting algorithms, hashing,
heaps, priority queues etc, so you will find the textbook useful to fill any
gaps that you might have in your knowledge.
We now map the material covered in lectures to chapters and sections
(and also to pages in the first edition) of the textbook.
1. Slides 1- A and 1 – B (Introduction): Chapter 1, only pages 1-12 covered
in class but the rest of the chapter, up to page 28 is very useful and
quick to read.
2. Slides 2 – A and 2 – B (Divide and Conquer): Chapter 5.3 pages 221-225
(Counting Inversions); Chapter 5.5 pages 231-234 (Integer Multiplica-
tion).
3. Slides 3 – A and 3 – B (Asymptotic Notation and Recurrences): Chap-
ters 2.1 and 2.2, pages 29-42, Chapter 2.4 pages 47-56; also Chapters 5.1
and 5.2 pages 210-221 (Our approach to recurrences is slightly different
and can be found in Cormen, Leiserson, Rivest and Stein, Introduction
to algorithms, available at the library (and worth buying, to use later
as a manual) however, the presentation on the slides is exhaustive and
should be sufficient).
4. Slides 4 – A and 4 – B (Fast Large Integer Multiplication): Chapter 5.5
pages 231-234. These lectures are the only ones which cover substan-
tial material not from the textbook (generalised Karatsuba algorithm).
1
However, this is an important example why asymptotic notation is not
enough and why we must also make sure that the constants hidden
by the asymptotic notation are not excessive. The presentation on the
slides is hopefully gentle and complete.
5. Slides 5 – A and 5 – B (The Fast Fourier Transform, Convolution and
Polynomial Multiplication): Chapter 5.6 pages 234-242.
6. Slides 6 – A and 6 – B (The Greedy Strategy): Chapters 4.1 and 4.2,
pages 115-131, Chapters 4.4 to 4.7 pages 137-177; the rest is really good
to read to master this important technique thoroughly.
7. Slides 7 – A and 7 – B (Dynamic Programming) Chapters 6.1 and 6.2,
pages 251-260, 6.4 pages 266-272, 6.8 pages 290-297, but sections we
skipped provide valuable additional examples of dynamic programming.
In fact, I have chosen somewhat different examples to increase the
diversity of examples available to you.
8. Slides 8 – A and 8 – B (Maximum Flow) Chapters 7.1 to 7.3, pages
337-356, Chapters 7.5 and 7.6 pages 367-378.
9. The rest of what we will cover depends on how we progress and this
mapping will be updated later accordingly.
Note: Given that we have only 9 weeks on our disposal, we cover some of
the chapters only partially. If you have time, try reading the whole chapters,
to really master algorithm design!!
2