Presentations
|
Chapters
|
Topics
|
Reading
|
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 9: Text
Processing
|
Pattern
Matching
|
Sections: 9.1.1 - 9.1.4
|
Chapter
13: NP-Completeness
|
P and NP,
NP-Completeness
Important
NP-Complete Problems
|
Sections: 13.1.1, 13.1.2, 13.2.1, 13.2.2
Section: 13.3.1-13.3.3
|
Demos
o
Minimum
Spanning Tree
o
Shortest
Path by Dijkstra's Algorithm
|
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.
|
|
HOMEWORKS
- Homework
#1: distributed on 1/15/2020, due 1/29/2020
- Homework
#2: distributed on 1/29/2020, due 2/05/2020
- Homework
#3: distributed on 2/05/2020, due 2/17/2020
- Homework
#4: distributed on 2/17/2020, due 2/24/2020
- Homework
#5: distributed on 3/04/2020, due 3/18/2020
- Homework
#6: distributed on 3/18/2020, due 4/08/2020
- Homework #7: distributed on 4/08/2020, due 4/15/2020
Office
hours: MW 1:45 - 3:45 pm or by
appointment (Room 254 MSB)
EXAMS
o
Monday, March 2, 2020, 12:30 pm - 01:45 pm (All material covered before Chapter 5) (Info, Overview)
Overview
for Midterm Exam is on Wednesday February 26, 2020
o Thursday, April
30, 2020, 10:15 - 12:30 p.m (Info, Overview)
Overview
for Final Exam is on Wednesday April 22, 2020
|