Reading Guide  Basic Algorithms


Lecture 1, Jan 28: Chapter 1, all but Section 1.4. Sections 1.1-1.3, 1.6, 1.8 are largely background and motivation;
Sections 1.5 and 1.7 need more careful reading.
Lecture 2, Jan 30: Section 1.2, Page 57 bottom half (arbitrary trees), Section 2.8 (start at "a representative problem" go up till the start of Section 2.8.1; for now, interpret DFS as a recursive algorithm).

Lecture 3, Feb 4. Skim the section on pseudo code (pages 35-42): I will not cover this in class, but henceforth I will assume that you understand the pseudo-code being used. Section 2.6 up to page 71 (stop at expression trees); you can also skip the discussion of the iterative version of DFS (this is the last 2 paragraphs on page 63, the last two paragraphs on page 65, and the first paragraph on page 66). Skim Section 2.7.  Section 2.8.1 up to the top of page 86.
Lecture 4, Feb 6. Section 2.6.3 up to middle of Page 80.
Lecture 5, Feb 11.
Sections 3.1.1, 3.1.2, skim 3.1.3, 3.2 to page 119, and skim pages 120-128.
Lexture 6, Feb 13. Review of tree algorithms.
Lecture 7, Feb 18. Section 3.3.2, pages 131-135; Section 3.3.4 pages 142-153.
Lecture 8, Feb 20. Section 3.3.4 pages 136-141; Section 5.1.2; Section 11.2.1.
Lecture 9, Feb 25. Section 3.3.2, pages 136-141; Section 5.0.1; Section 5.32 up to the top of page 275 (the rest of this section gives a nice explanation of how to improve the quicksort code; it is a good demonstration of efficient coding in the small, i.e. of how to squeeze constant factors); Section 5.3.3 (my presentation in class differs a bit; consequently, you may prefer to follow this on the videos I will be preparing).
Lecture 10, Feb 27. Section 5.2.2, Heapsort.
Lecture 11, Mar 4. Section 5.4 up to the top of page 290.
Lecture 12, Mar 6.  Section 5.62, 5.63. Also, pages 261-262, 278.
Lecture 13, Mar 11. Section 6.3 through page 366.
Lecture 14, Mar 13. Midterm.
Lecture 15, Mar 25. Section 11.3, pages 607-612.
Lecture 16, Mar 27. Section 11.3, pages 614-624 (skip Latex history).
Lecture 17, April 1
Section 11.3, pages 626-642.
Lecture 18, April 3. Chapter 7, pages 391-402.
Lecture 19, April 8. Chapter 7, pages 406-417.

Lecture 20, April 10. Chapter 8, pages 433-442.
Lecture 21, April 15. Chapter 8,  pages 444-451.

Lecture 22, April 17. Chapter 8, pages 456-459, skim "the fine points" (page 464),
page 465.
Lecture 23, April 22. Chapter 8, pages 492-502.
Lecture 24, April 24. Chapter 11, Section 11.4, pages 669-679.
Lecture 25, April 29. Hashing. In class notes.

Lecture 26, May 1. Hashing. In class notes.





Last modified: April 22, 2014