Cosc 300 - Advanced Data Structures

Fall 2009

Dr. Donald Simon
Office / Phone: 416 College Hall / 396-6472
Office Hours: TTh 1:30 pm - 3:00 pm
E-mail address: simon@mathcs.duq.edu
Class Web page: http://www.mathcs.duq.edu/simon/Fall08/cs300.html

Text: Algorithms in C++, Third Edition, Parts 1-4 and Part 5 by Robert Sedgewick

Course Objectives: In this course, you will learn about advanced data structures and the algorithms for manipulating them, and how to analyze the time and memory requirements of them. Specifically, you will master some complex searching and sorting algorithms and their data structures, advanced types of trees, basic computational geometry procedures, and graph representations and graph algorithms. Also, you will learn when and how to use techniques for developing algorithms, such as divide-and-conquer and dynamic programming. We shall also discuss the topic of NP-completeness. Additional topics may be covered.

You will come out of this course with a deeper understanding of abstract data types, how to choose or create the proper ADT, how different implementations have different properties, including time and space complexity. You will also become skilled in algorithmic analysis and algorithm development using the latest techniques. You will be able to write correct, efficient, and perhaps even elegant programs at the conclusion of this course.

Assignments are due every other week on Thursday at class times. Due dates for programs are given in the tentative schedule below. Programs and assignments are not equally weighted. The final will be comprehensive but will stress material covered in the second half of the semester.

Grading Scale: 90-100 = A; 80-89 = B; 70-79 = C; 60-69 = D; less than 60 = F.

Programs must be written in either standard C++ and may use the C++ Standard Toolkit Library, or in Java and use the Java APIs.

Office Hours: Please feel free to make an appointment for other times if my office hours are not convenient to you.

Honor Policy: Students in this class fall under the mandate of the College of Liberal Arts plagiarism policy. Any student guilty of plagiarism will receive a grade of ``F'' for the course and will be reported to the Student Committee. Work done in this course is to be by the individual, not a group. You may not share (copy, give, show) your homework with other students in the course. Any code not your own that is included in your programs must be properly cited. This includes code from the book and that given by the professor. Submitted programs may include the code that was not written by you, from the book, nor given out by the professor only with specific permission by the professor for that assigmnent.

Late assignments: Assignments are due at the beginning of class. Late assignments will lose 10% per day that they are late. Weekends count as one day. All work must be turned in by 12/8.

Students with Disabilities: Students with documented disabilities are entitled to reasonable accommodations if needed. If you need accommodations, please contact the Office of Freshman Development and Special Student Services in 309 Duquesne Union (412-396-6657) as soon as possible. Accommodations will not be granted retrospectively.

Make-ups: Make-ups for tests will not be given except in cases of emergency.

Tentative Schedule:

	Date	Topic(s)	Readings	Assignments
1.	8/25	Introduction	1, 2, Notes,	Homework #1
			Connect.java
2.	9/1	Review: Stacks and Queues, ADTs	3, 4
3.	9/8	Recursion	5	Homework #2
4.	9/15	Advanced Sorting	6, 7, 8	Program #1 due
5.	9/22	Other Sorts	9, 10, 11	Homework #3
6.	9/29	Balanced Trees	12, 13
7.	10/6	Hashing, Radix Search, External Search	14, 15, 16	Program #2 due
	10/8	Mid-term Examination
8.	10/13	Computational Geometry	Notes Notes	Homework #4
9.	10/20	Graphs and Graph Search	17, 18	Homework #5, Program #2 due
10.	10/27	Digraphs and MST	19, 20
11.	11/3	Shortest Path and Network Flow	21, 22	Homework #6 Program #3 due
12.	11/10	Randomized Algorithms	Notes	Program 4 due
13	11/18	NP-Completeness	Notes	Homework #7
14.	11/23	NP-Completeness	Notes
15.	12/1	Algorithm Design	Notes	Program #5 due
	No work will be accepted after 12/8
	12/10	Final 11:00 am - 1:00 pm