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.
Course Delivery: online | 7 weeks | 14 sessions
Course Credits: 3 units | 37.5 Seat Hours | 75 Total Hours
Assignment Submission: All projects, articles, and quizzes will be submitted via the course page on Gradescope.
Course Dates: Wednesday, October 21 – Wednesday, December 9, 2020 (8 weeks)
Class Times: Monday, Wednesday at 9:30am–12:15pm (13 class sessions)
| Class | Date | Topics | Assignments |
|---|---|---|---|
| 1 | Wed, Oct 21 | Iterative Sorting Algorithms | |
| 2 | Mon, Oct 26 | Divide-and-Conquer Recursion | |
| 3 | Wed, Oct 28 | Recursive Sorting Algorithms | Due: Iterative Sorting Challenges |
| - | Mon, Nov 2 | Vote! - Civic Responsibility Break | |
| 4 | Wed, Nov 4 | Recursive Sorting Algorithms Lab | Quiz 1 |
| 5 | Mon, Nov 9 | Integer Sorting Algorithms | |
| 6 | Wed, Nov 11 | Prefix Trees (aka Tries) | |
| 7 | Mon, Nov 16 | Prefix Trees (aka Tries) Lab | |
| 8 | Wed, Nov 18 | Rotating Binary Search Trees[] | |
| 9 | Mon, Nov 23 | Trees Project Kickoff | Quiz 2 |
| - | Wed, Nov 25 | Holiday - Thanksgiving | |
| 10 | Mon, Nov 30 | Multiple Key Search Trees | |
| 11 | Wed, Dec 2 | Priority Queues & Heaps | |
| 12 | Mon, Dec 7 | Sorting Algorithms Comparison | Quiz 3 |
| 13 | Wed, Dec 9 | Trees Project Presentations | Due: Trees Project & Article |
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 all quizzes
- If you are not passing any assignment you have a week to fix any errors and resubmit
Any additional resources you may need (online books, etc.) can be found here. You can also find additional resources through the library linked below:
- Program Learning Outcomes - What you will achieve after finishing Make School, all courses are designed around these outcomes.
- Grading System - How grading is done at Make School
- Code of Conduct, Equity, and Inclusion - Learn about Diversity and Inclusion at Make School
- Academic Honesty - Our policies around plagerism, cheating, and other forms of academic misconduct
- Attendance Policy - What we expect from you in terms of attendance for all classes at Make School
- Course Credit Policy - Our policy for how you obtain credit for your courses
- Disability Services (Academic Accommodations) - Services and accommodations we provide for students
- Student Handbook - Guidelines, policies, and resources for all Make School students