CPT S 223: ADVANCED DATA STRUCTURES

FALL 2007, 3cr.

 

(AUG 20 DEC 14)

SCHOOL OF EECS

WASHINGTON STATE UNIVERSITY

 

 

MWF 9:10-10

SLOAN 150

 

Open lab hour: Monday 2-3pm, Sloan 353 (Linux lab)

 

COURSE DETAILS

 

The primary objectives of this course is as follows:

        Introduce advanced data structures

        Introduce algorithmic design and analysis

        Solve problems using different data structures and design techniques, and compare their performance and tradeoffs

        Express algorithms in a language independent manner (as pseudocodes)

        Implement algorithms and data structures in C++

 

INSTRUCTOR

 

ANANTH KALYANARAMAN

EME 237, 335-6760

Email:   ananth@eecs.wsu.edu

 

Office hours: Wednesday 4-5pm

 

TEACHING ASSISTANTS

 

            Rashmi Parthasarathy, Sloan 341

            Office Hours:    Thursday 12-1pm

                       

            Jonathan Brown, Sloan 338

            Office Hours:    Tuesday 1-2pm

 

PREREQUISITES

 

  • CPTS 122
  • MATH 216 or equivalent

 

TEXTBOOKS (REQUIRED)

 

-                       Data structures and algorithm analysis in C++

# Author: Mark Allen Weiss

# Publisher:Addison Wesley/Pearson; 3rd Edition (February 28, 2006)

# Errata: http://www.cs.fiu.edu/~weiss/dsaa_c++3/errata.html

 

-                       AcceleratedC++: Practical programming by Example

# Author: Andrew Koenig, Barbara E.Moo

# Publisher: Addison Wesley/Pearson; 1stEdition (January 15, 2000)

 

            Bothbooks are available at the bookie.

 

 

GRADING

 

        5 homeworks (45%)

        4 programs (15%)

        1 midterm (20%)

        1 final (20%)

 

COURSE POLICIES

 

        Homeworks must be submitted in class on the due date. Late submission on the same day before 5pm will be
accepted at the instructors office but with 10% penalty. No other late submissions will be allowed.

        Programming assignments are due by 5pm on the due date. No other late submissions will be allowed. Programs must be electronically submitted and instructions will be provided in class.

        All exams are closed-book and cumulative exams and cover the material up to and including the point indicated on the class schedule.

        All homeworks and assignments must be done individually unless otherwise explicitly indicated in the problem set. Anyone cheating will receive a zero for that assignment and will be subject to the university's academic dishonesty policy. Cheating involves giving assistance to or receiving assistance from another individual on work assigned in this class. If you have any questions regarding an assignment, see the instructor or teaching assistant.

        If there is a need for special accommodation based on disability, please meet with the instructor during the first week.

 

 

LECTURE NOTES

 

  • Course Introduction (PDF)
  • Mathematical Background (PDF)
  • Unix Background (PDF)
    1. Unix Lab Exercise here
  • Asymptotics (PDF)
  • Trees (PDF)
  • Heaps (PDF)
  • Union-Find (PDF)
  • Spatial and String Data Structures (PDF)
  • Sorting and Algorithm Design Techniques (PDF)
  • Course Overview (PDF)

 

 

 

HOMEWORKS & PROGRAMMING ASSIGNMENTS

 

 

  • Homework 1 (PDF)     Due 9/12/2007
  • Programming Assignment 1 (PDF) Due 9/14/2007
  • Homework 2 (PDF)     Due 9/26/2007
  • Homework 3 (PDF)     Due 10/10/2007
  • Midterm (PDF) 10/15
  • Programming Assignment 2 (PDF) Due 11/5/2007
    1. Input for PA2 (TXT)

(PS: The source of this input file is http://mclibrary.nhmccd.edu/lit/ss2.html)

  • Homework 4 (PDF)     Due 11/16/2007
  • Programming Assignment 3 (PDF) Due 11/28/2007

 

 

Tentative Homework, PA and Exams Schedule:

 

  • Final Exam:       Finals week (12/14, 8-9am)

 

SAFETY ON CAMPUS

 

http://www.ba.wsu.edu/em/emergencies.htm

 

Get familiar with the emergency procedures from the above link.