Last modified: 2016-10-04
This is a course page of
David Casperson
Associate Professor
Computer Science
University of Northern British Columbia

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 Assignments20%
Programming Assignments20%
Midterm I17%
Midterm II18%
Final35%
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 AssignmentsOccasional. Found here.
Thanksgiving2009-10-12 Monday
Midterm I2009-10-14 Wednesday
Drop date2009-10-20 Tuesday
Midterm II 2009-11-132009-11-20 Friday
Course 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:
Book Picture Data Structures and Algorithm Analysis in Java by Mark Allen Weiss. (second edition). Isbn: 9780321370136.
References:
Book Picture Purely Functional Data Structures by Chris Okasaki. (second edition). Isbn: 9780521631242.
(Picture of Chris Okasaki)
Book Picture The Art of Computer Programming by Book Picture.
Links
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
Home page Semesters Site Map
go back Fall 2009 go forward
2017-12 other links

Java
CPSC 200
CPSC 482/682
Dates
Policies
David’s Schedule

University Calendar