/ACS-3110-Trees-Sorting

🌳 Explore 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.

Primary LanguagePythonMIT LicenseMIT

🌳 ACS 3110: Advanced Trees & Sorting Algorithms

Course Description

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.

Prerequisites

Course Specifics

Course Delivery: online | 7 weeks | 14 sessions
Course Credits: 3 units | 37.5 Seat Hours | 75 Total Hours

Learning Outcomes

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

Schedule

Course Dates: Monday, January 20 – Wednesday, May 12, 2021
Class Times: Monday, Wednesday, Friday at 4:30pm – 6:20pm

Class Topics
1 Iterative Sorting Algorithms
2 Divide-and-Conquer Recursion
3 Divide-and-Conquer Recursion
~ Lab Day
4 Recursive Sorting Algorithms
5 Integer Sorting Algorithms
~ Lab Day
6 Prefix Trees (aka Tries)
7 Prefix Trees (aka Tries) II
8 Rotating Binary Search Trees
9 Multiple Key Search Trees
10 Priority Queues & Heaps
~ Lab Day
11 Trees Project Presentations

Class Assignments

We will be using Gradescope, which allows us to provide fast and accurate feedback on your work. All assigned work will be submitted through Gradescope, and assignment and exam grades will be returned through Gradescope.

As soon as grades are posted, you will be notified immediately so that you can log in and see your feedback. You may also submit regrade requests if you feel we have made a mistake.

Your Gradescope login is your Dominican email, and your password can be changed at https://gradescope.com/reset_password. The same link can be used if you need to set your password for the first time.

Evaluation

To pass this course, students must meet the following requirements:

  • Complete each assignment below with a rubric score of 2 or higher.
    • Iterative Sort Challenges
    • Recursive Sort Challenges
    • Integer Sort Challenges
    • Prefix Trees Lab
    • AVL Trees Lab
  • Pass the Midterm Check In Assessment with a 70% or higher.
  • Complete the Technical Article AND Advanced Trees Project with a 70% or higher.
  • All deliverables above must be turned in on Gradescope.
  • Participate in online class sessions and asyncronous lab time.
  • Make up all classwork from all absences.