CS 442/442G Data Structures and Algorithm Analysis
  Fall 2009
Instructor: Qi Li

Office	TCCW 135, x6225, Qi.Li@wku.edu
Homepage	http://www.wku.edu/~qi.li
Office Hours	MW: 10:00—12:00, 13:30—14:30
	TR: 10:00—11:30
	and by appointments
Prerequisties	A grade of "C" or better in CS241, CS338
Text	Data Structures and Algorithm Analysis in Java by Mark Allen Weiss, Pearson
	2006 (2th Edition)
Grading	Test I and II 15%
	Final 30%
	Homeworks 35%
	Attendence 5%
Grading scale	90-100 A
	80-89 B
	70-79 C
	60-69 D
	< 60 F
Exam dates	Dates for the first two exams will be announced at least one week in advances.
	The final exam is scheduled for Friday Dec 18, 10:00pm-12:30pm.

Course Description:

• This course covers important data structures, algorithms, and their applications, emphasizing algorithm analysis and general algorithmic strategies. Topics include balanced search trees, hashing, priority queues, sorting, and graph algorithms.

Course Policy:

1. Submit your homeworks on time. If you have to submit homeworks after the due day, you must get the permission from the instructors TWO days before the due day.

2. Students are responsible for attending the exams on time. If you cannot attend the exam, you must get permission from the instructor, and present documented excuse.

3. If the instructor is late, students should remain in the class orderly working (studying) until the instructor arrive or until the class is dismissed officially by a person of authority.

4. No food or drink is permitted in the classroom, and no mobile phone usage in the classroom.

5. Plagiarism and other forms of academic dishonesty will result in F for the course. Copying code from other groups, or the Internet is not allowed.

Student Disability Services:

      In compliance with university policy, students with disabilities who require academic and/or auxiliary accommodations for this course must contact the Office for Student Disability Services in Downing University Center, A-200. The phone number is 270 745 5004.
      Please DO NOT request accommodations directly from the professor or instructor without a letter of accommodation from the Office for Student Disability Services.

Course Content: We will attempt to cover the following topics, as time allows.

• Best, worst, and average case run-time of an algorithm
• AVL, Red-Black, and B trees
• Various heaps and their impact on priority queue efficiency
• Disjoint set structure
• Hashing
• Analysis of sorting algorithms including insertion, quick, merge, topological sorting
• Recurrence and master theorem
• Graph Algorithms: single-source and all-pairs shortest path algorithms, maximum flow algorithms
• Dynamic programming, heuristics, pattern matching and string/text algorithms
• P, NP, and NPC classes