Reading Guide

 

SC       denotes  Siegel/Cole notes

CLRS  denotes  Cormen/Leiserson/Rivest/Stein text

RC       denotes  notes I have distributed in class

 

Background on asymptotics     SC  Sec 2.2, pages 28-34

Solving recurrence equations   RC

Writing recurrence equations   SC  Sec 2.3.2, pages 39-42

Divide & Conquer                    SC  pages 327-334

Background on Sorting

Merge Sort               SC  pages 108-110 ;      CLRS  pages 28-36

Heapsort                   SC  pages 111-113;       CLRS  pages 127-137

Quicksort algorithm SC pages 114-125 (a lot of detail)

                                             CLRS  pages 145-148

                             analysis   SC  pages 126-127; CLRS takes a quite different

                                                                                  approach, pages 155-158

Bucket sort, radix sort, lexicographic sort     SC  Sec 5.4.2-5.4.5, pages 139-151;

     CLRS uses the name bucket sort for a different problem and does

     radix sort on pages 170-173.

Quick Select   SC  pages 158-159; CLRS  pages 185-188 (my analysis was closer to CLRS).

Sorting lower bound  SC  pages 134-137; CLRS  pages 165-167.

Tree node count.   SC  pages 93-94 (example 2)

2-3 Trees.  RC

Amortized analysis

    Credit arguments    SC  pages 92-95;  CLRS  pages 410-412.

    Fibonacci heaps      SC  pages 285-288; CLRS  pages 457-462, 468-470, 476-495.

    Splay trees              SC  pages 292-297;

    Union-find             SC  pages 298-300; CLRS pages 498-508; analysis from RC


Shortest path algorithms   SC  pages 227-276; CLRS pages 580-587, 592-599, 620-633.
MST algorithms    SC pages 277-284; CLRS pages 561-579.


Dynamic Programming  SC pages 334-348; CLRS pages 323-369.


Randomized algorithms    RC

NP-completeness
    Reductions. Garey & Johnson, chapter 3; in particular, pages 45, 48-49, 54-60, 63-65, 72, 75-76.

    Cook's theorem.  Garey & Johnson, section 2.6, pages 38-44.

    Background.  Garey & Johnson, the rest of chapter 2.

    Alternative source.  RC


Formal language theory  RC; Sipser, chapters 1 and 2.