**Note:** This is the webpage for the *Fall 2020* offering of this course. It's only left here in case someone finds it useful as a reference.

**Instructor:** Pat Morin, 5177 HP, morin@scs.carleton.ca

# Final Exam Information

The final exam will have the same format as the midterm exam, but will be 120 minutes long. It will be available on CULearn at the scheduled time. To find the scheduled time, consult the Final Exam Schedule but note that the final exam will be 120 minutes, *not* 180 minutes.

# Learning Modality

Content for this course is delivered online, as a YouTube Live Stream on Wednesdays and Fridays at 14:30 (2:30pm). I give lectures from a classroom in my basement that students can tune into at the scheduled time (see the lecture schedule below). During the lecture students are encouraged to ask questions using the YouTube chat feature. In addition to being available as a live stream, these lectures are left on YouTube, so they can be watched later.

# 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.

# Important Dates

Sunday | Oct 4 | 23:55 | Assignment 1 due |

Sunday | Oct 18 | 23:55 | Assignment 2 due |

Wednesday | Oct 14 | 14:35 | Mid-term evaluation/exam |

Sunday | Nov 15 | 23:55 | Assignment 3 due |

Friday | Dec 11 | 23:55 | Assignment 4 due |

# Assignments

- The Assignment 4 submission deadline has expired. Here are sample solutions.
- The Assignment 3 submission deadline has expired. Here are sample solutions.
- The Assignment 2 submission deadline has expired. Here are sample solutions.
- The Assignment 1 submission deadline has expired. Here are sample solutions.

# 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

Assignments | 75% |

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
- Sep 16: The JCF, by example
- Programming with the Java Collections Framework
- Demo code: ListDemo.java, SetDemo.java, WordFun.java, varney.txt
- JCF performance reference

- Sep 18: Array-based lists
- ArrayStack and its amortized analysis (Section 2.1)

- ArrayStack and its amortized analysis (Section 2.1)
- Sep 23: Array-based lists
- ArrayQueue (Section 2.3)
- ArrayDeque (Section 2.4)

- Sep 25: Building a deque from two stacks
- ListSpeed.java
- DualArrayDeque (Section 2.5)

- Sep 31: A space-efficient array-based list
- RootishArrayStack (Section 2.6)

- RootishArrayStack (Section 2.6)
- Oct 2: Linked lists
- SLList and DLList (Chapter 3)

- SLList and DLList (Chapter 3)
- Oct 7: Skip lists I
- SkiplistSSet and SkiplistList (Chapter 4)

- SkiplistSSet and SkiplistList (Chapter 4)
- Oct 9: Skip lists II
- Analysis of skiplists (Section 4.4)

- Analysis of skiplists (Section 4.4)
- Oct 14: Midterm exam on cuLearn
- Oct 16: Binary trees
- Introduction to binary trees (Chapter 6)

- Introduction to binary trees (Chapter 6)
- Oct 21: Random binary search trees and treaps
- Treap (Chapter 7)

- Treap (Chapter 7)
- Oct 23: Scapegoat trees
- ScapegoatTree (Chapter 8)

- ScapegoatTree (Chapter 8)
- Nov 4: 2–4 trees and red-black trees
- 2–4 trees (Section 9.1)
- RedBlackTree (Section 9.2)

- Nov 6: Heaps and Heap-Sort
- Heaps and heap-sort (Section 10.1)
- Randomized meldable heaps (Section 10.2)

- Nov 11: Hashing
- ChainedHashTable (Section 5.1)
- Multiplicative hashing (Section 5.1.1)

- Nov 13: Hashing
- Hash codes and equality (Section 5.3)
- Source code

- Nov 18: Sorting
- Sorting algorithms (slides)(Chapter 11)

- Sorting algorithms (slides)(Chapter 11)
- Nov 20: Convex hulls and plane sweep
- Nov 25: Data structures for integers
- BinaryTrie, XFastTrie and YFastTrie (Chapter 13)

- BinaryTrie, XFastTrie and YFastTrie (Chapter 13)
- Nov 27: Data structures for strings I
- Tries
- C-strings versus P-Strings
- Patricia trees

- Dec 2: Data structures for strings II
- Dec 4: External Memory Data Structures
- B-Trees

- B-Trees
- Dec 9 & 11: Review time (no classes)