CISC 235 - Data Structures

Winter 2011

Instructor:	Doug Wightman (wightman (at) cs.queensu.ca), (613) 449-0583, 636 Goodwin Hall
	Office Hours: by appointment

Teaching Assistants:	Lab A (Monday): Jesse Lu (8jjl1 (at) queensu.ca)
	Lab B (Friday): Zi Ye (zi (at) acm.org)

Class Location:	Mackintosh-Corry Hall, room B201
Times:	Tuesday 3:30, Thursday 2:30, and Friday 4:30
Times:
Lab A:	Monday 8:30 a.m., Walter Light Hall, Room 310
Lab B:	Friday 6:30 p.m., Walter Light Hall, Room 310
Lab B:
Required Text:	Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, MIT Press, Cambridge, Massachusetts, 2006
	This textbook is also used in CISC 365 and CISC 466. Free online access is available if you register for an account.

Announcement

On Tuesday, April 12th, at 2 p.m. there will be an informal problem-solving / final exam preparation session at Goodwin 636. Please feel welcome to join!

Course Description

Design and implementation of advanced data structures and related algorithms. Topics will include complexity analysis, trees, graphs, and hash tables.

How does Google return search results in less than a second? How do 3D games render millions of pixels sixty times a second? This course provides an introduction to some of the software methods that make these accomplishments possible.

Course Structure

Assignments	28% (7% each)
Quizzes	20% (10% each)
Midterm Exam	16%
Final Exam	36%
Class Participation	(up to 5%)

Assignments will require the implementation of data structures in Java. Quizzes will also consist of programming questions. You will be able to prepare yourself for the quizzes by completing the assignments.

The midterm and final will cover theoretical course content. There will be no programming on these exams.

The first lab will be in week 2.

Marks will be available on WebCT.

Schedule

IMPORTANT DATES:
The midterm will be in class on Thursday, March 3rd.

This section of the website will be updated each week:

Week	Dates	Description	Readings	Files
1	Jan. 11, 13, 14	Complexity, Summations	2.2, 3.1, Appendix A	Complexity Slides (ppt) Complexity Slides (pdf)
2	Jan. 18, 20, 21	Complexity, Recursion, Recurrence Relations	2.3, 4.3	Recursion Slides (ppt) Recursion Slides (pdf) Assignment 1
3	Jan. 25, 27, 28	General Trees, Binary Search Trees	Appendix B.5, 10.4, 12.1 - 12.3	Basic Tree Slides (ppt) Basic Tree Slides (pdf)
4	Feb. 1, 3, 4	Balanced Trees: AVL & Red-Black Trees Assignment 1 Due on Monday Quiz 1 on Tuesday	13.1 - 13.4	Balanced BSTs (ppt) Balanced BSTs (pdf) Assignment 2
5	Feb. 8, 10, 11	Dictionaries: Hash Tables	11.1 - 11.4	Hash Tables (ppt) Hash Tables (pdf)
6	Feb. 15, 17, 18	Game Trees Assignment 2 Due		Game Trees (ppt) Game Trees (pdf)
		Reading Week
7	Mar. 1, 3, 4	Midterm Review, Priority Queues: Heaps Midterm Thursday, March 3rd	6.1 - 6.5	Priority Queues, Heaps (ppt) Priority Queues, Heaps (pdf) Assignment 3 (due date extended)
8	Mar. 8, 10, 11	External Sorting: Multi-way Merge Sort External Searching: B-Trees	18.1 - 18.3	External Sorting (ppt) External Sorting (pdf)
9	Mar. 15, 17, 18	Graph Representations and Traversal	Appendix B.4, 22.1 - 22.3	Graphs (ppt) Graphs (pdf) Assignment 4 (due date extended)
10	Mar. 22, 24, 25	Graph Algorithms: Topological Sort, Minimum Spanning Trees Assignment 3 Due (extended) Quiz 2 on Tuesday	22.4, 23.1, 23.2	Graph Algorithms (ppt) Graph Algorithms (pdf)
11	Mar. 29, 31, Apr. 1	Graph Algorithms: Shortest Paths	24.1 - 24.3	Shortest Paths (ppt) Shortest Paths (pdf)
12	Apr. 5, 7, 8	Review Assignment 4 Due (extended)

Practice Exams

Practice Midterm Questions, Solutions

Practice Final Questions, Solutions

Note: I would like to thank Mary McCollam for her assistance in preparing this course. The slides and other course materials were derived from her materials and the course structure also benefited from her experience.