In this course students will implement and test advanced data structures and algorithms, benchmark performance, analyze algorithmic complexity, explore trade offs in performance and memory usage, and draw out elegant problem-solving techniques.
Key concepts include sorting algorithms, divide-and-conquer recursion, heaps, tries, self-balancing trees, and execution trees. Students will build an original project that applies these data structures to real-world problems such as autocomplete, family trees, and board games.
Students will also write technical articles about these topics to deepen their understanding and create their online presence as knowledgeable and proficient software engineers.
Term 4 Course Dates: Monday, March 30, 2020 – Friday, May 15, 2020 (7 weeks, 14 class sessions)
Class Times: 2:30–5:15pm on Monday & Wednesday (Section A) or Tuesday & Thursday (Section B)
| Class | Date by Section | Lesson Topics | Deliverable Due or Quiz |
|---|---|---|---|
| 1 | A: Mon, Mar 30 B: Tue, Mar 31 |
Iterative Sorting Algorithms | |
| 2 | A: Wed, Apr 1 B: Thu, Apr 2 |
Divide-and-Conquer Recursion | |
| 3 | A: Mon, Apr 6 B: Tue, Apr 7 |
Recursive Sorting Algorithms | Due: Sorting Challenges 1 & 2 |
| 4 | A: Wed, Apr 8 B: Thu, Apr 9 |
Integer Sorting Algorithms | |
| 5 | A: Mon, Apr 13 B: Tue, Apr 14 |
Prefix Trees (aka Tries) | Due: Sorting Challenges 3 & 4 |
| 6 | A: Wed, Apr 15 B: Thu, Apr 16 |
Prefix Trees (aka Tries) Lab | Quiz: Sorting Algorithms |
| 7 | A: Mon, Apr 20 B: Tue, Apr 21 |
Rotating Binary Search Trees | Due: Prefix Tree Challenges |
| 8 | A: Wed, Apr 22 B: Thu, Apr 23 |
Multiple Key Search Trees | |
| 9 | A: Mon, Apr 27 B: Tue, Apr 28 |
Trees Project Kickoff | |
| 10 | A: Wed, Apr 29 B: Thu, Apr 30 |
Trees Project Lab | Quiz: Self-Balancing Trees |
| 11 | A: Mon, May 4 B: Tue, May 5 |
Priority Queues & Heaps | |
| 12 | A: Wed, May 6 B: Thu, May 7 |
Trees Project Lab | Due: Binary Heap Challenges |
| 13 | A: Mon, May 11 B: Tue, May 12 |
Sorting Algorithms Comparison | Quiz: Binary Heaps & Heap Sort |
| 14 | A: Wed, May 13 B: Thu, May 14 |
Trees Project Presentations | Due: Trees Project & Article |
| Deliverable | Date Started | Date Due |
|---|---|---|
| Sorting Challenges 1 & 2 | Mon, Mar 30 | Tue, Apr 7 |
| Sorting Challenges 3 & 4 | Mon, Apr 6 | Tue, Apr 14 |
| Prefix Tree Challenges | Mon, Apr 13 | Tue, Apr 21 |
| Binary Heap Challenges | Mon, May 4 | Thu, May 7 |
| Trees Project & Article | Mon, Apr 27 | Thu, May 14 |
Students must pass the following course and demonstrate mastery of its competencies:
By the end of this course, students will be able to:
- implement and compare several sorting algorithms and know when to use which ones
- apply divide-and-conquer recursion techniques to elegantly solve complex problems
- analyze complexity of recursive algorithms with recurrence relations and master theorem
- implement abstract data types including priority queues, binary heaps, and tries
- implement self-balancing tree structures including AVL trees, splay trees, and 2-3 trees
- implement tree traversal algorithms: depth-first and breadth-first ordering
- utilize bit manipulation algorithms to store and access information in individual bits
To pass this course, students must meet the following requirements:
- Actively participate in class and abide by the attendance policy
- No more than two unexcused absences ("no-call-no-shows")
- No more than four excused absences (communicated in advance)
- Make up all classwork from all absences
- Complete the required challenges and final project
- Pass the summative assessment (total of all quiz scores)
- Review the quiz study guides with the lesson topics and learning outcomes (skills) you need to demonstrate, links to the best resources to review while preparing