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

CPSC 482 — Data Structures  II — Fall 2009

This course is cross-listed with CPSC 682. Click here for the printed CPSC 482 course outline.

Prerequisites
A grade of C- or better in cpsc 281, and cpsc 340; or permission of 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-09 Printed Outline
2009-09-14 STL Notes
2009-09-14 Asymptotics Worksheet
2009-09-23 Reversible Linked Lists
2009-11-?? Red Black Sets
2009-11-?? Notes on Red Black Trees
Grading Scheme:
Programming Assignments20%
Midterm I20%
Midterm II20%
Final40%
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-11 other links

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

University Calendar