CPSC 682 — Data Structures II — Fall 2009
This course is cross-listed with CPSC 482. Click here for the printed CPSC 682 course outline.
- Prerequisites
- Graduate standing in Computer Science or permission of the instructor.
- Important Information
-
Important information may be posted here from time to time.
The final examination is scheduled for Tuesday, December 08, 2009 in the morning. (Scheduling now confirmed.)
- Contact Information
- Click here for David’s contact information.
- Rooms and Hours
- Click here for David’s schedule.
- Handouts:
-
2009-09-14 STL Notes 2009-09-14 Asymptotics Worksheet 2009-09-23 Reversible Linked Lists 2009-09-23 Printed Outline 2009-11-?? Red Black Sets 2009-11-?? Notes on Red Black Trees - Grading Scheme:
-
Graduate Research Assignments 20% Programming Assignments 20% Midterm I 17% Midterm II 18% Final 35% - Research Assignment(s).
To be determined between the instructor and the student. This will likely consist of finding current literature relevant to the course and writing a préecis of the content.
- Dates:
-
Programming Assignments Occasional. Found here. Thanksgiving 2009-10-12 Monday Midterm I 2009-10-14 Wednesday Drop date 2009-10-20 Tuesday Midterm II 2009-11-132009-11-20 FridayCourse Evaluation 2009-11-27 Friday Last Class 2009-12-04 Friday Final 2009-12-08 morning. Definitive University calendar dates can be found on the University web-site here.
- Text:
Data Structures and Algorithm Analysis in Java by Mark Allen Weiss. (second edition). Isbn: 9780321370136. - References:
Purely Functional Data Structures by Chris Okasaki. (second edition). Isbn: 9780521631242.
(
)
The Art of Computer Programming by 
.
- Links
-
A Java StopWatch class C++ StopWatch Code - Goals
-
a student who successfully completes this course can successfully
reason about data structures.
In particular she (or he)
- can articulate appropriate criteria for choosing a data structure;
- can choose appropriate data structures based to solve a higher level problem;
- is familiar with classical data structures; and
- can design and implement new data structures.
- Topics
-
from (not necessarily in the order listed)
- Algorithm Analysis.
- Collection libraries in C++ and Java.
- Amortized complexity.
- Review of lists, trees, and hash-tables.
- Heaps.
- Union find structres.
- Tries.
- Purely functional versus imperative programming.
- Persistent verus ephemeral data structures.
- Strict versus non-strict evaluation. Laziness and thunks.
- General
-
- There will be approximately 4 programming assignments.
- Discussion of assignment topic is encouraged but all assignments must be done independently. Copied assignments are considered as “Academic Dishonesty.” Responses to academic dishonesty include assigning a mark of -100% and written notification of the Dean.
- Programming Assignments.
-
# Name Due Date 1 Reversible Linked Lists 2009-10-07 2 Red Black Sets 2009-11-30
