COMP2002-COMP2402: Data Structures

Announcements | Outline | Assignments |TAs | Notes | Textbook | Office Hours | Grading | Dates | Cheating | Special Needs

Announcements

• The classroom for this course has been changed to UC-282 the days and times remain the same.
• Assignment 1 is already posted.
• Assignment 2 due date will be Tuesday June 5^th
• The assignment 2 on web CT was modified. Please resubmit the files before. (Tuesday June 5th)
• Midterm Thursday June 7^th
• The midterm will cover the content seen in the last three classes ( May 24^th , May 29^th and May 31^st )
• It will be short answer question like the previous midterm.
• Assignment 3 already posted. Due date Tuesday, June 19^th
• The due date for assignment 3 will be extended 2 more days (June 21^st). Since you will not be able to upload it to WebCT you should email the zip file to the TA(Tawfic Abdul-Fatah)

Course outline

This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be

• The Java Collections Framework
• Sequences: lists, stacks, queues, deques
• Array-based implementations of sequences
• Linked-list based implementations of sequences
• Unordered sets - hash tables
• Ordered sets - balanced binary search trees, skiplists
• Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

Assignments

• Assignment 1: Solutions
• Assignment 2:
• Assignment 3:

TA

• Andrew Trenholm
• Tawfic Abdul-Fatah

There are no office hours for TAs but they will be checking regularly the Web-CT discussion and Carleton Computer Science Society. You can put any question you have, on any of those two sources and you will receive a prompt answer. It is recommended that you check it regularly since you can find answer for some question you could have.

Course notes

− Note that the slides could slightly change before the lecture

• Introduction
• Java Collections Framework
• Array Based List
• Rootish Array and Linked List
• Hash Tables and SkipLists
• Binary Trees, Binary Search Trees and Treaps
• Scapegoat tree, 2-4 tree, Red black tree
• Binary heaps, Randomized meldable heaps, Sorting algorithms
• Graphs, Traversal of the graph
• Shortest path, minimum spanning tree

Textbook

The official textbook for this course is Open Data Structures (in Java). This open-content textbook is completely free as a greyscale pdf (for printing), a color pdf, and an online version. You can also download complete Java source code for the data structures that appear in the book.

There is also some mathematical content in the course. We will use asymptotic analysis, logarithms, and factorial functions. Mathematics for Computer Science by Lehman, Leighton, and Meyer is an excellent reference for this material, and is also free. A PDF copy of this book is also available on the Open Data Structures website, in the related projects section.

Class Schedule

• This is a tentative schedule for the course.

Date	Topics	References
May 8	Introduction
May, 10	The Java Collections Framework I: Interfaces and Implementations	Sun Tutorial
May 15	ArrayLists (ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques)	Sec. 2.1, 2.5
May17	RootishArrayStacks and Linked lists	Sec. 2.6, Chap. 3
May 22	Mid-term exam - bring your student card
May 24	Hash tables Skip lists	Chap. 5, Chap. 4
May 29	Binary trees and Binary search trees Treaps	Sec. 6.1 and Sec. 6.2 Chap. 7
May 31	Scapegoat trees and 2-4 and red-black trees	Chap. 8 Chap. 9
June 5	Binary heaps Randomized meldable heaps Sorting algorithms and lower bounds	Sec. 10.1 Sec. 10.2 Chap. 11
June 7	Mid-term exam - bring your student card
June 12	Graph, Graph Traversal, MST, Shortest Path	Chap. 12
June 14	Review lecture

Office hours

Office hours are as follows. If this doesn't work, then meeting times can be arranged by email.

Tuesday and Thursday from 4:30pm to 5:30pm HP-5347

Grading scheme

Grades will be assigned using the following grading scheme.

Assignment 1	10%
Assignment 2	10%
Midterm Exam 1	15%
Assignment 3	10%
Midterm Exam 2	15%
Participations in class	5%
Final exam	40%
Total	100% + 5% bonus

The bonus for active participation cannot be used to pass the course if it was failed but it could slightly improve the mark for the course.

I may, at my discretion, increase the grades of certain students to raise the class average or change the distribution. This will never cause a student's grade to go down, nor will it change the relative rankings of students so, e.g., it is not possible for a student who earned an 80% to receive a lower grade than a student who earned a 75%.

Important dates

A tentative schedule will be posted here when it is ready.

Policy regarding unoriginal work

Students are encouraged to collaborate on assignments, but at the level of discussion only. That is, they may work together to solve problems, but when writing down the solutions they should do so on their own. No student should show another student his or her written solutions.

Any student who is caught submitting work that they did not do themselves will have the relevant material sent to the Dean of Science, who will decide on the appropriate action.

Students with Special Needs

Students with special needs should obtain documentation from the Paul-Menton Center and notify me as soon as possible.