Week 1 (Jan 22, 24, 2007):
Lecture 1:
Course Overview
Analysis of
Insertion Sort
Lecture 2:
Matlab Tutorial
Matlab help documents/files: tutorial.m,
operations.m,
Matlab
tutorial (.ps)
The Divide and
Conquer Approach: Analysis
of Merge Sort
Reading Assignment: Chapters 1
and 2 from the textbook
Lab
1
|
Week 2 (Jan 29, 31, 2007):
Lecture 3:
The Divide and
Conquer Approach: Analysis
of Merge Sort
Lecture 4:
Master
Theorem:
Interpretation
and examples
Reading Assignment: Chapter 4 from the textbook
Lab
2
|
Week 3 (Feb 5, 7, 2007):
Lecture 5:
Master
Theorem:
Proof of
simplified Master Theorem
Growth of
Functions
Lecture 6:
Growth of
Functions - continued
Reading Assignment: Chapters 3,
4 from the textbook
Lab
3
|
Week 4 (Feb 12, 14, 2007):
Lecture 7:
Polynomial
Multiplication: Example of Divide-and-Conquer approach and use of
Master theorem to analyze its runtime
Lecture 8:
Quiz 1
Probabilistic
Analysis and Randomized Algorithms
The Hiring
Problem, overview of random variables, expectations
Reading Assignment: Chapter 5 from the textbook
Lab
4 and 5
|
Week 5 (Feb 19, 21, 2007):
Lecture 9:
Probabilistic
Analysis and Randomized Algorithms
The Hiring
Problem, overview of random variables, expectations
Homework 1 (Due Mar 4 before
class): Exercises 2.3-4, 2,3-5, 2.3-7, 3.1-3, 4.3-2, 4.3-4,
and Problems 3.2, 4.1 from the textbook
Lecture 10:
Elementary Data Structures
Lab
4 and 5
|
Week 6 (Feb 26, 28, 2007):
Lecture 11:
Quiz 2
Elementary Data
Structures
Lecture 12:
Binary Search
Trees
Lab
6
|
Week 7 (Mar 4, 6, 2007):
Lecture 13:
Binary Search
Trees
Homework 2 (Due Mar 20, before
class). Exercises: 10.1-1, 10.2-5, 10.3-1, 10.4-1, 12.1-1 12.2-4
12.2-1 a, b, c 12.3-1; Problem (at
the end of chapter 10): 10-1
Lecture 14:
Heapsort
Lab
7
|
Week 7 (Mar 18, 20, 2007):
Lecture 15:
Hashing
Lecture 16:
Graphs:
Depth-First Search
HW3 (Extra credit, Due Tue Mar 25,
in class). Exercises: 6.1-4 6.1-6 6.3-1 6.4-1 6.4-3 10.1-1 10.1-3
10.3-1 10.4-1 10.4-2 11.2-1 11.2-2 12.1-2 12.2-4 12.3-3
Lab
8
|
Week 9 (Mar 25, 27, 2007):
Lecture 17:
Midterm review
Graphs:
Depth-First Search
Thursday: MIDTERM
Lab
9
|
Week 10 (Apr 1, 3, 2007):
Lecture 18, 19:
Graphs:
Depth-First Search
Lab
10
|
Week 11 (Apr 8, 10, 2007):
Lecture 20, 21
Graphs: Breadth-First Search
Thursday: Quiz 3
Lab
11
|
Week 12 (Apr 15, 17, 2007):
Lecture 22, 23
Greedy Algorithms: Minimum Spanning Trees,
Set Cover, Huffman Encoding
Lab
12
|
Week 13 (Apr 22, 24, 2007):
Lecture 24, 25
Dynamic Programming
NP-Completeness
Thursday: Quiz 4
Homework
4
Lab
13
|
Week 14 (Apr 29, 2007):
Lecture 26, 27
Coping with NP-Completeness: backtracking,
branch-and-bound, approximation techniques, local search heuristics
Thursday: Quiz 3
Lab
14
|
|
|