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: TR 3:30 –
5:30 PM
HOMEWORKS
o
Homework
#1: distributed on 01/26/2010, due
02/04/2010 results
o
Homework
#2: distributed on 02/04/2010, due
02/16/2010 results
o
Homework
#3: distributed on 02/16/2010, due
03/02/2010 results
o
Homework
#4: distributed on 02/25/2010, due
03/09/2010 results
o
Homework
#5: distributed on 03/23/2010, due
04/08/2010 results
o
Homework
#6: distributed on 04/08/2010, due 04/22/2010 results
o
Homework
#7: distributed on 04/20/2010, due 05/04/2010 results
o
Extra credit problem: distributed on 03/25/2010, due 04/15/2010. results
EXAMS
o
Thursday, March 18, 2010, 12:30
pm - 1:45 pm (All material covered before
Chapter 5) Info
Overview Results
MidTerm Review is on March 16, 2010
o
Monday,
May 10, 2010, 12:45 - 3:00 p.m. (All material covered after Chapter 4) Info Overview Results
Final Exam Review is on May 6,
2010
Grades
|