Fundamental Algorithms Lecture Notes

G22.1170 Spring 2008

NOTICE TO STUDENTS:

Please report any errors or typos. Suggestions for improving the notes are welcome!

In this directory, "Lecture I, II, etc" (in roman numerals) refers to chapters 1, 2, etc, of my notes. It does not mean the 1st, 2nd, class lecture. Some of these chapters may be skipped or taught out of order.

Since some students like to also refer to a standard text book, I will correlate my notes below with chapters from the book "Introduction to Algorithms" (2nd Edition) by Cormen, Leiserson, Rivest and Stein. I will refer to this book as [CLRS]. This extra reading is optional.

--Chee Yap

Lecture I: Introduction to Algorithmics

Read Section 1 (General Intro)
Read Section 4 (Models -- esp. comparison-tree model)
Read Section 8 (Asymptotic Notations). CRITICAL to master this.
The rest can be read in order, at your leisure.
Use the Appendix for general reference in the future. BUT for now, read the parts on Logic, and on Proofs and Induction.
Exercise to do on your own: 8.4, 8.5.
See [CLRS] Chaps.1-3, and also Appendix B.

Lecture II: Recurrences

Skim Section 1.
Read Sections 2, 3, 4 (skip the end of Section 4).
Section 5: Know the arithmetic, geometric and harmonic series.
Section 6: Standard form, polynomial-type and exponential-type sum.
Section 10.2: Know the Master Theorem and how to apply it.
Sectin 11: Know the two rules.
See also [CLRS] Chap.4, and also Appendix A.

Lecture III: Balanced Search Trees

Read casually Sections 1 and 2. Be familiar with the definitions of Dictionary and Priority Queues (p. 4).
Read Sections 3: this section is essential, but it is mostly a review of basic Binary Search Trees (BST).
Read Section 4: AVL Trees.
Read Section 5: (a,b)-Trees.
See [CLRS] Chap.12, and initial part of 13.

Lecture IV: Pure Graph Algorithms

Read casually Sections 1.
Read Section 2 for overview. Some of the concepts are not needed, so use it for later reference. (Appendix in Lecture 1 also has some graph notations)
Sections 3 is easy background on graph representation.
Sections 4 and 5 is the heart of this chapter, on BFS and DFS.
Sections 6 and 7 are slightly more advance, and we will cover some selection from here.
See [CLRS] Chap.22.

Lecture V: Greedy Method

Read Sections 1,2,3,5.
Topics: linear bin packing, Huffman code algorithm, dynamic Huffman code algorithm, Minimum spanning tree
You may read Section 4 (on matroids) only lightly.
See [CLRS] Chaps.16, 23.

Lecture VI: Amortization Method

Read Sections 1,2,4,5,6,7.
Skip section 3 on splay analysis. You need to know the amortized complexity bounds when Fibonacci heaps are used to implement "mergeable queues" (Intro. to Section 5, p.18)
See [CLRS] Chap.17. (See also Chaps.20,21)

Lecture VII: Dynamic Programming

Study Sections 1, 2 and 4.
Read Section 3 more lightly.
See [CLRS] Chap.15.

Lecture VIII: Randomized Algorithms (also Derandomization and QuickSort)

Read notes on Quicksort.
For Lecture VIII, read Section 4 (random number generator).
See [CLRS] Chaps.5,7, and Appendix C.

Lecture IX: Hashing

Read the first five sections, including universal hashing.
See [CLRS] Chap.11.

Lecture XIV: Shortest Paths

Read the first five sections, including universal hashing.
See [CLRS] Chaps.24,25.

Lecture XXX: NP Completeness

Read all.
You must understand the concept of reduction to be able to do some simple problems. (Lemma 5 reducing HAM to SAT is a good example of this)
See [CLRS] Chap.34.