CS3500B - Theory I
Summer 2003
Class Time: Monday, Tuesday, Wednesday, Thursday 1:20-2:30pm
Class Location: CoC 17
Class syllabus
Instructor: Yan Zhong Ding
Office Hours: Wednesday, Thursday 2:30-3:30pm
Location: CoC 234
E-mail: ding@cc.gatech.edu
TA: Ryan Johnston
Office Hours: Wednesday 11am-1pm
Location: CoC Common Area
E-mail: ryanrino@cc.gatech.edu
TA: Yarong Tang
Office Hours: Monday 3-5pm
Location: CoC Common Area
E-mail: yarongt@cc.gatech.edu
|
Announcements
The solutions are now posted. However although 4.5, and 7 are very readable they
aren't the best quality, I have trouble converting from the .ps of .pdf... but
I'll fix this. So check back and there will be a higher quality 4,5, and 7
later.
Numerous people got Problem 4 on HW5 CORRECT but I counted
it wrong, drop by today (sunday) or Monday to get your points.
Also I will probably be around all day Mon into the late
evening/morning to help people as much as they want.
Topics and Relevant Textbook Chapters
-
Finite Automata and Regular Languages. Sipser Chapter 1.
-
Context Free Languages. Sipser Chapter 2.
-
Turing Machines and Decidability. Sipser Chapters 3, 4.1.
-
Undecidability. Sipser Sections 4.2, 5.1, 5.3.
-
Introduction to Asymptotic Notations
and Analysis Algorithms. CLRS Sections 2.1 - 2, 3.1. Sipser Section 7.1.
(You may find CLRS Section 3.2 and Appendices A and B helpful.)
-
Introduction to Divide and Conquer: Merge Sort (CLRS Section 2.3),
Strassen's Matrix Multiplication Algorithm (CLRS Section 28.2).
(You may find CLRS Chapter 4 helpful.)
-
Quick Sort. CLRS Chapter 7. (You may find CLRS Chapter 5 and
Appendix C helpful for background in probability.)
-
Lower Bound for Comparison-Based Sorting Algorithms. CLRS Section 8.1.
-
Sorting in Linear Time: Counting Sort and Radix Sort. CLRS Sections
8.2 - 3.
-
Order Statistics. CLRS Chapter 9.
-
Introduction to Graphs. Breadth-First Search, Depth-First Search,
Topological Sort. CLRS Chapter 22.
-
Minimum Spanning Trees. CLRS Chapter 23.
-
Single-Source Shortest Paths. Dijkstra's Algorithm. CLRS Chapter 24.
-
Introduction to Dynamic Programming. CLRS Sections 15.2 - 4.
-
All-Pair Shortest Paths. Floyd-Warshall Algorithm. CLRS 25.1 - 2.
-
Introduction to Computational Complexity: P, NP, NP-Completeness.
Sipser Chapter 7. CLRS Chapter 34.