CPSC 311H - Analysis of Algorithms (Honors)

Syllabus

Notes and Announcements

The TA for the class will be Guangtong Cao. His information is as follows:
email: g0c7670@cs.tamu.edu
Office: 419C (Currently - could change to 419D)
Phone: 862-4535 (will change if office changes)
Office Hours: Tuesday, Thursday 4:00-5:00
Some substitution method examples (from last year - references to questions and "in class" refer to last year).
Dr. Keyser will be out of the office from Monday, 10/11 through Thursday, 10/14. Office hours are cancelled during that time.
On Homework 4, question 19. You do not need to solve the problem for t exactly, but should be able to get an OK approximation.
On Homework 5, question 3 should have been 21.3-1, not 21.3-4.
Dr. Keyser will be out of the office from Thursday, 11/18 and Friday, 11/19. Class was already cancelled on that Thursday, due to the Bonfire Memorial Dedication.

Final Grades are available HERE

Assignments

Culture Assignments
Homework 1 - Asymptotic analysis, sorting
Homework 2 - More sorts, order statistics, and hashing
Homework 3 - Hashing and tree data structures
Homework 4 - Dynamic Programming and Greedy Algorithms
Homework 5 - Disjoint sets and basic graph algorithms
Homework 6 - Graph algorithms
Homework 7 - NP completeness and Approximation Algorithms
Extra Credit Homework - Dijkstra's Algorithm with various heaps

Schedule

Future dates should be considered tenative for all information on class topics, chapters covered, and homework not yet assigned.

Day			Topics	Reading Covered or Assigned	Homework Assigned	Homework Due
1	Tue	Aug. 31	Introduction	Chapters 1,2
2	Thu	Sep. 2	Asymptotic Analysis and Recursion	Chapters 3,4
3	Tue	Sep. 7	Heapsort	Chapter 6	HW 1
4	Thu	Sep. 9	Quicksort	Chapter 7
5	Tue	Sep. 14	Linear Sorts, Order Statistics	Chapters 8, 9
6	Thu	Sep. 16	Basic Data Structures, Hashing	Chapters 10, 11	HW 2	HW 1
7	Tue	Sep. 21	Hashing and Binary Search Trees	Chapter 12
8	Thu	Sep. 23	Red-black trees	Chapter 13
9	Tue	Sep. 28	B-trees	Chapter 18	HW 3	HW 2
10	Thu	Sep. 30	Dynamic Programming	Chapter 15
11	Tue	Oct. 5	Exam 1 - through class 9
12	Thu	Oct. 7	Dynamic Programming, continued Greedy Algorithms	Chapter 16
13	Tue	Oct. 12	Greedy Algorithms (continued)		HW 4
14	Thu	Oct. 14	Guest Lecturer Guangtong Cao Distributed Algorithms			HW 3
15	Tue	Oct. 19	Disjoint Sets	Chapter 21
16	Thu	Oct. 21	Basic Graph Algorithms	Chapter 22	HW 5
17	Tue	Oct. 26	Minimum Spanning Trees	Chapter 23		HW 4
18	Thu	Oct. 28	Single-Source Shortest Paths	Chapter 24
19	Tue	Nov. 2	All Pairs Shortest Paths	Chapter 25	HW 6	HW 5
20	Thu	Nov. 4	NP-completeness	Chapter 34 through 34.1
21	Tue	Nov. 9	Exam 2 - Classes 10-19
22	Thu	Nov. 11	NP-completeness (continued)	Sections 34.2 through 34.4
23	Tue	Nov. 16	Proving Problems NP Complete	Section 34.5		First 3 Culture Assignments Due
24	Thu	Nov. 18	Class Cancelled - Bonfire Memorial Dedication
25	Tue	Nov. 23	NP Completeness Examples		HW 7	HW 6
26	Tue	Nov. 30	Approximation Algorithms	Chapter 35
27	Thu	Dec. 2	Guest Lecturer Ilya Hicks, TAMU Department of Industrial Engineering
28	Tue	Dec. 7	Computational Geometry Overview			HW 7 All Culture Assignments Due
	Wed	Dec. 15	Final Exam Time, 1:00-3:00