Presentations
|
|
Chapters
|
Topics
|
Reading
|
|
Instead of
Introduction
|
By Jeff Edmonds
|
|
|
Chapter 1: Algorithm
Analysis
|
Analysis of
Algorithms
|
Sections:
1.1,1.2,1.3,1.4
|
|
Chapter 2: Basic Data
Structures
|
· Elementary
Data Structures
· Vectors
· Stacks
· Queues
· Sequences
· Trees
· Heaps
· Priority
Queues
· Hash Tables
· Dictionaries
|
· Sections: 2.1,2.2,2.3
· Sections: 2.2.1
· Sections: 1.5,2.1.1
· Sections: 2.1.2
· Sections: 2.2.2,2.2.3
· Sections: 2.3.1 - 2.3.4
· Sections: 2.4.1,2.4.3
· Sections: 2.4.1 - 2.4.4
· Sections: 2.5.1 - 2.5.6
· Sections: 3.1.1 - 3.1.6
|
|
Chapter 3: Search Trees
and Skip Lists
|
· Binary
Search Trees
· Red-Black
Trees
|
· Sections: 3.1.1 - 3.1.6
· Sections: 3.3.3
|
|
Chapter 4: Sorting, Sets,
and Selection
|
· Merge Sort
· Quick Sort
· Sorting
Lower Bound
· Sets
· Radix
Sort
· Selection
|
· Sections: 4.1.1
· Sections: 4.3.1, 4.6
· Sections: 4.4
· Sections: 4.2.1
· Sections: 4.5.1,
4.5.2
· Sections: 4.7, 4.7.1 -
4.7.3
|
|
Chapter 5: Fundamental
Techniques
|
· Greedy Method
· Divide-and-Conquer
· Dynamic
Programming
|
· Sections: 5.1,5.1.1,
5.1.2
· Sections: 5.2, 5.2.1 -
5.2.3
· Sections: 5.3, 5.3.1 -
5.3.3
|
|
Chapter 6: Graphs
|
· Graphs
· Depth-First Search
· Breadth-First Search
· Biconnectivity
· Directed Graphs
|
· Sections: 6.1- 6.2
· Sections: 6.3.1
· Sections: 6.3.3
· Sections: 6.3.2
· Sections: 6.4.1, 6.4.2,
6.4.4
|
|
Chapter 7: Weighted
Graphs
|
· Shortest Paths
· Minimum Spanning
Tree
|
· Sections: 7.1,
7.1.1-7.1.3, 7.2, 7.2.1
· Sections: 7.3,
7.3.1-7.3.3
|
|
Chapter 8: Network Flow
and Matching
|
· Network Flow
|
· Sections: 8.1.1,
8.1.2, 8.2.1-8.2.3
|
|
Chapter 9: Text
Processing
|
· Pattern
Matching
|
· Sections: 9.1.1
- 9.1.4
|
Demos
· Minimum
Spanning Tree
· Shortest
Path by Dijkstra's Algorithm
· A Stable Marriage
Applet
· An Applet of SkipList
|
Textbook: Algorithm Design: Foundations,
Analysis, and Internet Examples, Wiley, 2002,
ISBN 0-471-38365-1
|
|
|
by
Michael T. Goodrich,
Univ. of California, Irvine
and
Roberto Tamassia,
Brown Univ.
|
|
Book's web site
Office hours: R 1:30 –
3:00 PM, TR 5:00 – 6:00 PM
HOMEWORKS
o
Homework
#1: distributed on 9/8/2009, due
9/15/2009 results
o
Homework
#2: distributed on 9/15/2009, due
9/24/2009 results
o
Homework
#3: distributed on 9/24/2009, due
10/8/2009 results
o
Homework
#4: distributed on 10/1/2009, due
10/15/2009 results
o
Homework
#5: distributed on 11/03/2009, due
11/10/2009 results
o
Homework
#6: distributed on 11/10/2009, due
11/24/2009 results
o
Homework
#7: distributed on 11/24/2009, due
12/03/2009 results
o
Extra credit problem: distributed on 11/10/2009, due 11/24/2009. results
HW SUMMARY
EXAMS
o
Thursday, October 29, 2009, 3:45 pm -
5:00 pm (All material covered
before Chapter 5) Info
Overview Results
MidTerm
Review is on October 27, 2009
o
Friday, December 18, 2009,
7:45 am - 10:00 am (All
material covered after Chapter 4) Info Overview Results
Final Exam Review is on December
10, 2009
|