Instructor: Pat Morin, 5177 HP, morin@scs.carleton.ca
Learning Modality
n Fall 2020, content for this course will be delivered online. Initially, at least, the plan is to do it as a YouTube Live Stream. I will give lectures from a classroom in my basement that students can tune into at the scheduled time (see the lecture schedule below). In addition to being available as a live stream, high-quality recordings of these lectures will be made available on YouTube, usually within 24 hours.
Here is the link for the first class live stream.
Course Objectives
This course is about storing data so that it can be efficient queried and (in some cases) updated. A detailed breakdown of topics is given below and here are some introductory slides.
Lecture and Office Hours Schedule
We have lots of office hours during which TAs or myself can help you with studying course material and offer you guidance for assignments. These will be posted here when they become available.
Day | Staff | Time | Location | |
---|---|---|---|---|
Wed | PM | Pat Morin | 14:30-16:00 | Lecture |
Fri | PM | Pat Morin | 14:30-16:00 | Lecture |
Important Dates
Sunday | Oct 4 | 23:55 | Assignment 1 due |
Sunday | Oct 18 | 23:55 | Assignment 2 due (in cuLearn) |
Oct 12–16 | Mid-term evaluation/exam | ||
Sunday | Nov 15 | 23:55 | Assignment 3 due |
Friday | Dec 11 | 23:55 | Assignment 4 due |
Assignments
Assignments will be posted here as they become available.
Please note the following rules and requirements about assignments:
- Late assignments will not be accepted.
- Assignments emailed to me will not be accepted.
- I will not respond to emails sent shortly before or after assignment deadlines asking for exceptions to the preceding two rules.
- You can type your solutions, or write them by hand and scan them (for example, using a scan app on your phone or using a real scanner).
- Solutions written-up in LaTeX are preferred, but not strictly required. In case you want to learn LaTeX, here is a tutorial. Learning LaTeX is a useful exercise, since many programs (including Microsoft Word) now use LaTeX for typesetting formulas.
- Each assignment must be submitted as one single PDF file through cuLearn.
Exams
The midterm and final exams will take place online. At the scheduled exam time, the exam will proceed as follows:
- You will login to Zoom with your camera turned and using your full real name.
- The Zoom session will have instructions on how to access the online exam
- If you have a question during the exam, you can "raise your hand" (a Zoom feature) and an exam proctor will contact you through Zoom chat.
- At some point during the exam, a proctor will check your student id (sign in).
- When you have completed and submitted your online exam, you will "raise your hand" and an exam proctor will contact you through Zoom chat to give you permission to leave (sign out).
Any online exams completed by a student who did not properly sign in and sign out will be discarded.
Academic Integrity (New—Please Read)
As of 2020, there are new penalties in place for academic integrity violations. These will be issued by the Associate Dean (Undergraduate Affairs) of Science to students who copy, in whole or in part, work they submit for assignments.
- First offence: F in the course
- Second offence: One-year suspension from program
- Third offence: Expulsion from the University
These are standard penalties. More-severe penalties will be applied in cases of egregious offences. Failure to inform yourself of the expectations regarding academic integrity is not a valid excuse for violations of the policy. When in doubt, ASK your instructor or TA.
For more information check the ODS website
Grading Scheme
The grading scheme is still being decided on.
Assignments | 25% |
Mid-term exam | 10% |
Final exam | 15% |
Textbooks
We will be using the following free (libre and gratis) textbook.
- Pat Morin. Open Data Structures, 2013. (Special HTML edition)
For some background material on some of the math used in this course, this book is excellent:
- Eric Lehman, F Thomson Leighton, and Albert R Meyer. Mathematics for Computer Science, 2018
Accommodation Statement
Carleton University is committed to providing access to the educational experience in order to promote academic accessibility for all individuals. Here is information on how to apply for academic accommodation.
Lecture topics
You should already be familiar with programming in Java and hopefully have had some introduction to discrete math, including Sigma-notation for sums, and big-Oh notation. We will review most of these concepts as we use them and you can use the relevant parts of Lehman et al if you find yourself struggling.
The following is a tentative schedule of topics that follows the schedule from a previous edition of the course. It will be updated as the course progresses.
- Sep 9: Introduction and interfaces
- Course overview.
- The Java Collections Framework: Interfaces
- Sep 11: Implementations
- Mmm DD: Array-based lists
- ArrayStack and its amortized analysis (Section 2.1)
- Mmm DD: Array-based lists
- ArrayQueue (Section 2.3)
- ArrayDeque (Section 2.4)
- Mmm DD: Building a deque from two stacks
- DualArrayDeque (Section 2.5)
- Mmm DD: A space-efficient array-based list
- RootishArrayStack (Section 2.6)
- Mmm DD: Linked lists
- SLList and DLList (Chapter 3)
- Mmm DD: Skip lists
- SkiplistSSet and SkiplistList (Chapter 4)
- Mmm DD: Skip lists
- Analysis of skiplists (Section 4.4)
- Mmm DD: Midterm exam and review
- Mmm DD: Binary trees
- Introduction to binary trees (Chapter 6)
- Mmm DD: Random binary search trees and treaps
- Treap (Chapter 7)
- Mmm DD: Scapegoat trees
- ScapegoatTree (Chapter 8)
- Mmm DD: 2–4 trees and red-black trees
- 2–4 trees (Section 9.1)
- RedBlackTree (Section 9.2)
- Mmm DD: Heaps and Heap-Sort
- Heaps and heap-sort (Section 10.1)
- Randomized meldable heaps (Section 10.2)
- Mmm DD: Hashing
- ChainedHashTable (Section 5.1)
- Hash code and equality (Section 5.3)
- Mmm DD: Sorting
- Sorting algorithms (Chapter 11)
- Mmm DD: Convex hulls and plane sweep
- Mmm DD: Data structures for integers
- BinaryTrie, XFastTrie and YFastTrie (Chapter 13)