Class Material

Lecture Slides

I will post here all the lecture slides used. As the class progresses I will keep adding material.

0 - Introduction (last update: 18/09/2018)
1 - Correction and Loop Invariants (last update: 18/09/2018)
2 - Asymptotic Analysis (last update: 02/10/2018)
3 - Amortized Analysis (last update: 08/10/2018)
4 - Probabilistic Analysis and Randomized Algorithms (last update: 22/10/2018)
5 - Lower Bounds (last update: 22/10/2018)
6 - Linear Algorithms for the Selection Problem (last update: 20/10/2018)
7 - Sorting in Linear Time (last update: 29/10/2018)
8 - String Matching (last update: 11/11/2018)
9 - Greedy Algorithms (last update: 03/12/2018)
10 - Dynamic Programming (last update: 03/12/2018)
11 - NP-Completeness (last update: 03/12/2018)

Exercises

I will post some exercises here.

Exercises #01 - Loop Invariants (18/09/2018)
Exercises #02 - Asymptotic Analysis (25/09/2018)
Exercises #03 - Solving Recurrences (02/10/2018)
Exercises #04 - Amortized Analysis (09/10/2018)
...

Recommended Books

The main book you should read is:

Introduction to Algorithms (CLRS), TH Cormen, CE Leiserson, RL Rivest and C Stein

Other suggested books that present similar material and/or complement CLRS book are:

Algorithm Design (KL), J Kleinberg, E Tardos
Algorithm Design Manual (ADM), S Skiena
Algorithms, (SW) R Sedgewick and K Wayne

For a more practical take on algorithms, including actual code:

Competitive Programming, S Halim, F Halim

Selected Topics

More info (external links) about the topics I'm talking about.

Correctness and Invariants

(CLRS) chapters to read:
- Chapter 2: Getting Started
  - Section 2.1: Insertion Sort
Introduction to Loop Invariants (Robert McCloskey, Univ. Scranton)
Invariants and Proofs of Correctness (Univ. Berkeley)
Game of petals (Kayles): applet to play online

Asymptotic Analysis, Order of Growth and Recurrences

(CLRS) chapters to read:
- Chapter 2: Getting Started
- Chapter 3: Growth of Functions
- Chapter 4: Divide-and-Conquer
Other Books:
- (KL) Chapter 2: Algorithm Analysis
- (ADM) Chapter 2: Algorithm Analysis - Slides [2] [3]
Trominoes: A Divide and Conquer Puzzle

Amortized Analysis

(CLRS) chapters to read:
- Chapter 17: Amortized Analysis
Other Books:
- (KL) Data Structures I (amortized analysis)
Notes on Amortization (CMU, D. Sleator)
Lecture on Amortized Analysis (CMU, A. Blum)
Lecture on Amortized Analysis (Cornell)
Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2), 306-318.

Probabilistic Analysis and Randomized Algorithms

(CLRS) chapters to read:
- Chapter 5: Probabilistic Analysis and Randomized Algorithms
- Section 7: Quicksort (particularly section 7.3, with randomized quicksort)
Other Books:
- (KL) 13 - Randomized Algorithms
Randomized Min Cut (Jeff Erickson)

Lower Bounds

(CLRS) chapters to read:
- Section 8.1: Lower bounds for sorting
Lower Bounds (Jeff Erickson)

Linear Algorithms for the Selection Problem

(CLRS) chapters to read:
- Chapter 9: Medians and Order Statistics

Sorting in Linear Time

(CLRS) chapters to read:
- Section 8.2: Counting Sort
- Section 8.3: Radix Sort
- Section 8.4: Bucket Sort

String Matching

(CLRS) chapters to read:
- Chapter 32: String Matching
Useful Links:

Substring Search (Princeton University)
Visualizing String Matching Algorithms (justinj)
Visualgo (Steven Halim, National University of Singapore)

Suffix arrays â€“ a programming contest approach (A. Vladu and C. Negruseri)
Implementation of Suffix Arrays (Topcoder, wack-a-mole)

Papers

"Fast pattern matching in strings", DE Knuth, JH Morris, Jr, VR Pratt - SIAM journal on computing, 1977 - SIAM
Suffix arrays: a new method for on-line string searches, U Manber, G Myers - Siam Journal on Computing, 1993 - SIAM

Greedy Algorithms

(CLRS) chapters to read:
- Chapter 16: Greedy Algorithms
- Chapter 23: Minimum Spanning Trees
- Chapter 6: Heapsort
Other Books:
- (KL) Chapter 4: Greedy Algorithms [1] [2]
Useful Links:

Proof methods and greedy algorithms (Magnus Lie Hetland)
Guide to Greedy Algorithms (CS161 - Stanford)

Dynamic Programming

(CLRS) chapters to read:
- Chapter 15: Dynamic Programming
Other Books:
- (KL) Chapter 6: Dynamic Programming [1] [2]
- (ADM) Dynamic Programming
Useful Links:

Dynamic Programming â€“ From Novice to Advanced (TopCoder Tutorial)

NP-Completeness

(CLRS) chapters to read:
- Chapter 34: NP-Completeness
Other Books:
- (KL) Chapter 8: Intractability [1] [2]
- (ADM)

Algorithms (CC4010)