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.
:warning: Important: Please follow these instructions exactly to set up your clone of this course repository.
Course Dates: Tuesday, October 22 – Thursday, December 12, 2019 (7.5 weeks)
Class Times: Tuesday & Thursday 3:30–5:20pm
| Class | Date | Lesson Topics | Deliverable Due or Quiz |
|---|---|---|---|
| 1 | Tue, Oct 22 | Iterative Sorting Algorithms | |
| 2 | Thu, Oct 24 | Divide-and-Conquer Recursion | |
| 3 | Tue, Oct 29 | Recursive Sorting Algorithms | |
| 4 | Thu, Oct 31 | Recursive Sorting Algorithms Recap | |
| 5 | Tue, Nov 5 | K-ary Search Trees & Tries | |
| 6 | Thu, Nov 7 | Prefix Trees (aka Tries) Lab Day | |
| 7 | Tue, Nov 12 | Prefix Trees (aka Tries) Lab Day | Due: Sorting Challenges |
| 8 | Thu, Nov 14 | Rotating Binary Search Trees | Quiz: Sorting Algorithms |
| 9 | Tue, Nov 19 | Multiple Key Search Trees | Due: Prefix Tree Challenges |
| 10 | Thu, Nov 21 | Trees Project Kickoff | |
| 11 | Tue, Nov 26 | Trees Project Lab Day | Quiz: Self-Balancing Trees |
| – | Thu, Nov 28 | No Class (Thanksgiving Break) | |
| 12 | Tue, Dec 3 | Priority Queues & Heaps | |
| 13 | Thu, Dec 5 | Integer Sorting Algorithms | Due: Binary Heap Challenges |
| 14 | Tue, Dec 10 | Sorting Algorithms Comparison | Quiz: Priority Queues & Heaps Due: Integer Sorting Challenges |
| 15 | Thu, Dec 12 | Trees Project Presentations | Due: Trees Project & Article |
| Deliverable | Date Started | Date Due |
|---|---|---|
| Sorting Challenges | Tue, Oct 22 | Tue, Nov 12 |
| Prefix Tree Challenges | Tue, Nov 5 | Tue, Nov 19 |
| Binary Heap Challenges | Tue, Dec 3 | Thu, Dec 5 |
| Trees Project & Article | Tue, Nov 19 | Thu, Dec 12 |
Students must pass the following course and demonstrate mastery of its competencies:
By the end of this course, students will be able to:
To pass this course, students must meet the following requirements: