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 3 Course Dates: Tuesday, January 22 – Thursday, March 7, 2019
Class Times: Tuesday & Thursday 3:30–5:20pm
| Class | Date | Topics |
|---|---|---|
| 1 | Tuesday, January 22 | Iterative Sorting Algorithms |
| 2 | Thursday, January 24 | Divide-and-Conquer Recursion |
| 3 | Tuesday, January 29 | Recursive Sorting Algorithms |
| 4 | Thursday, January 31 | Integer Sorting Algorithms |
| 5 | Tuesday, February 5 | K-ary Search Trees & Tries |
| 6 | Thursday, February 7 | Autocomplete Challenges |
| 7 | Tuesday, February 12 | Multiple Key Search Trees |
| 8 | Thursday, February 14 | Rotating Binary Search Trees |
| – | Tuesday, February 19 | President's Day (Observed) |
| 9 | Thursday, February 21 | Trees Project Code Review |
| 10 | Tuesday, February 26 | Priority Queues & Heaps |
| 11 | Thursday, February 28 | Self-Balancing Trees Recap |
| 12 | Tuesday, March 5 | Sorting Algorithms Comparison |
| 13 | Thursday, March 7 | Written Assessment (Final Exam) |
- Weeks to Completion: 7
- Total Seat Hours: 37.5 hours
- Total Out-of-Class Hours: 75 hours
- Total Hours: 112.5 hours
- Units: 3 units
- Delivery Method: Residential
- Class Sessions: 13 classes, 7 labs
Students must pass the following course and demonstrate mastery of its competencies:
- CS 1.3: Core Data Structures & Algorithms
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:
- 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
- Finish all required tutorials and projects
- Pass the summative assessment (final exam)
- Academic Honesty
- Accomodation Policy
- Diversity Statement
- Evaluation Methods
- Program Learning Outcomes
- Title IX Disclaimer
Please follow these instructions exactly to set up your fork of this repository.