CSI2114: Data Structures (Spring 2006)

Professor

Dr. Amiya Nayak
Room: SITE 5001 (ext. 2165)
E-Mail: nayak@uottawa.ca
Office Hours: Thursday (13:00 – 15:00) & Friday (13:30 – 14:30)

Teaching Assistants

Shantanu Das
Room: SITE 4063
E-Mail: shantdas@site.uottawa.ca
Office Hours: TBD

Natasha Jindal
Room: CBY A709
E-Mail: njind029@uottawa.ca
Office Hours: Tuesday 9:00-10:00

Abolfazl Keshtkar
Room: SITE 5130
E-Mail: akeshtka@site.uottawa.ca
Office Hours: Monday 10:00-11:00

Lectures

Wednesday:  10:30-12:30  Vanier Hall 131

Friday: 10:00-12:00  Vanier Hall 131

Labs & Lab Materials

Lab:  Wednesday 12:30-14:30  STE 2060  (in charge: Shantanu Das)

Click here for lab materials.

Prerequisites

CSI 1101 or CSI 1102 or ITI 1221.

Course Objectives

Present in a systematic fashion the most commonly used data structures, emphasizing their abstract properties. Review implementation methods for those data structures. Discuss typical algorithms that operate on each kind of data structures, and analyze their performances.

Textbook

Michael Goodrich, Roberto Tamassia, Data Structures and Algorithms in Java (3^rd ed.), Wiley, 2004. 

The textbook has a web site at http://ww3.java3.datastructures.net/ with on-line demos and hints for exercises.

Other resources

D.E. Knuth, Sorting and Searching , vol. 3 of The Art of Computer Programming, Addison Wesley, 1973.

T.A. Standish: Data Structures in Java. Addison Wesley.

S. Sahni: Data Structures, Algorithms, and Applications in Java.

Marking Scheme

You must have at least 50% of mark in the midterm and the final exam, combined, to pass the course.

The final exam will be comprehensive, with the emphasis on the material not covered in the midterm exam. 

A student who has an official medical certificate (from the University Health Services) for being absent in the day of the midterm will have the final exam mark scaled up accordingly.  

Course Topics

Introduction to abstract data types. Trees, binary search trees, balanced trees. Searching. Sorting. Simple examples of complexity analysis. Graphs, simple graph algorithms: depth-first and breadth-first search, minimum spanning tree, shortest path. (Lab work will be done in the Java programming language).

Course Materials

Week 1:   Introduction (pdf file); Stacks, Queues and Deques (pdf file)
Week 2:   More Stacks (pdf file); Analysis of Algorithms (pdf file)

Week 3:   Vectors, Lists, Sequences (pdf file); Priority Queues (pdf file)
Week 4:   Trees (pdf file); Heaps (pdf file); Binary Search Trees (pdf file)
Week 5:   AVL Trees (pdf file); 2-4 Trees (pdf file)
Week 6:   Review for midterm; Midterm on June 9, 2005
Week 7:   Study Week (June 12 – June 16).
Week 8:   Hash Tables (pdf file); Graphs (pdf file); Traversals (pdf file)
Week 9:   Shortest Path (pdf file); Minimum Spanning Tree (pdf file)
Week 10:   Insertion Sort; Selection Sort; Bubble Sort  (pdf file)
Week 11:   Recursive Sort (pdf file); Radix Sort (pdf file)

Assignments

Assignment #1  
Assignment #2 
Assignment #3 

Assignment #4

Term Mark       Final Exam: Friday, July 21 in CBY B012 from 13:00 to 16:00