Readme,
Course Information,
Course Description,
Policies,
Video
Dates,
Photo,
Fun,
Your Marks,
Forum
Readme,
Course Information,
Course Description,
Policies,
Video
Dates,
Photo,
Fun,
Your Marks,
Forum
|
|
Readings
[HTA]
How to Think about Algorithms:
York
Bookstore
Amazon
Cambridge House Press
Desk Copies
[Video] Someone was kind enough
to film all my lectures one term.
YouTube
Video
[Video]
MIT Videos
[LN] Andy Mirzaian's Notes
[CLRS] Cormen, Leiserson, Rivest, and Stein (Some remaining parts of this book are studied
in the sequel courses CSE4101/5101/6121)
[More Notes]
Umesh
Vazirani's Book
Jeff
Erickson's Notes
Introduction (ppt) (1 class: 1)
General course description
(HTA 0; LN 0,1; CLRS1)
Unit 0: Relevant Mathimetics (0 classes: blended with in)
(logic.ppt,
math.ppt,
more_math.ppt,
steps,
ass,
ass sol,
practice,
practice sol,
fun)
Existential and Universal Quantifier (HTA 22)
Time Complexity of Algorithms (HTA 23; LN 1; CLRS 2)
Logarithms and Exponentials (HTA 24
Asymptotic Notations (HTA 25; LN1; CLRS 3)
Summations: arithmetic, geometric,
harmonic (HTA 26; CLRS A)
Recurrence Relations (HTA 27; LN 2;CLRS 4)
Unit 1: Loop Invariants for Iterative Algorithms (5 classes: 2,3,4,5,6)
(ppt,
steps,
ass,
ass sol,
practice,
practice sol)
Understanding Algorithms Abstractly (HTA 1,2)
Home to School Problem
Steps in an Iterative Algorithm
Assertions
Insertion Sort
Designing an Algorithm
Finding Errors
Typical Loop Invariants
Binary Search Like Examples (HTA 13,14,4)
The Partition Problem
Greatest Common Divisor (HTA 6)
Bucket (Quick) Sort for Humans (HTA 5; CLRS 8)
Radix/Counting Sort
Lower Bound for Sort (HTA 7)
Unit 2: Recursive Algorithms (6 classes: 7,8,9,10,11,12)
(ppt,
steps,
ass,
ass sol,
practice,
practice sol)
Multiplying (mp3,HTA 92; CLRS 282,30,31)
Recurrence Relations (HTA 27; LN 2;CLRS 4)
Code
Stack of Stack Frames
Tree of Stack Frames
Friends and Strong Induction (HTA 8;CLRS 23, 334)
Towers of Hanoi
Check List
Merge & Quick Sort
Simple Recursion on Trees (HTA 31,10)
Generalizing the Problem
Things not to do
Heap Sort & Priority Queues (HTA 91; LN 2,4; CLRS 7,9)
Trees Representing Equations
Pretty Print
Parsing with context free grammars (HTA 12)
Recursive Images (HTA 11)
Ackermann's Funcition (HTA 11)
Unit 3:
Relevant Mathimetics (see unit 0)
Graph Search Algorithms (4 classes: 13,14,16,17)
(ppt,
ass,
ass sol,
Soccer Strategies)
Review definitions and graph
terminology (HTA 31;CLRS B)
Generic Search (ppt)
Breadth-First-Search (BFS)
and shortest paths (HTA 141, 142; CLRS 222)
Depth-First-Search
(DFS) (HTA 144, 145; CLRS 223)
Single Source Shortest Paths (Dijkstra) (HTA
143; CLRS 24)
Dags
and topological sorting (HTA 146; CLRS224)
Network Flow (2 class: 18,19)
Optimization Problems Definition (HTA 13)
Network Flow Defn (HTA 15;CLRS 26)
Simple Example
Application: Matching
Flow Strategy
Hill Climbing
Augmenting Flow
Primal-Dual Hill Climbing
Min Cut
Max Flow = Min Cut
Running Time
Linear Programming
Unit 4: Greedy Algorithms Methods (5 classes: 20,21,22,23,24,25)
Unit 5: Dynamic Programming (6 classes: 26,27,28,29,30,31)
(ppt,
steps,
ass,
ass sol,
practice,
practice sol)
Techniques (HTA 17,18; LN6; CLRS 15)
Optimization Problems
Recursiv Backtracking
A Sequence of Decisions
The Little Bird & Friend
Optimal Substructure
Memoization
Set of Sub-Instances
Tracing Dyn. Prog. Alg
Reversing
Code
Speeding Up Running Time
Multiple Opt Solutions
Review
Question for Little Bird
Review & Don'ts
Problems
Best Path
Printing Neatly
Longest Common Subsequence (HTA 191)
Knapsack Problem
The Event Scheduling Problem (HTA 193)
Parsing (HTA 198)
Satisfiability
All Pairs Shortest Paths (HTA 196; CLRS 25)
Unit 6: Reductions and NP-Completeness (HTA 20; CLRS 34) (3 classes: 32,33,34)
Review
Topics not covered:
Yes covered a lot In fact, most of the book
Topics that we did not cover:
Lowerbounds (ppt)
2.2: Deterministic Finite Automaton
3: Abstract Data Types
15.3: The Steepest Ascent Hill Climbing Algorithm
21: Randomized Algorithms
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.