This course covers graph theory, data structures, algorithms, and analysis. Key concepts include recursion, greedy algorithms, memoization and dynamic programming. Students will build an original project whose underlying structure requires the use of graph structures and algorithms to solve real-world problems such as airplane routing, social networking, and board games.
Graphs can be used to model and solve a wide variety of problems, including systems of roads, airline flights from city to city, how the Internet is connected, or even the sequence of classes you must take to complete your degree here at Make School! Understanding graphs allows you to build models of these problems and use those models to find optimal or best case solutions.
Students by the end of the course will be able to ...
- Describe common graph algorithms.
- Model and solve real world problems using graph algorithms.
- Implement graph algorithms in code.
- Develop algorithmic thinking skills to expand on common graph algorithms and improve problem solving approaches.
NOTE: Due to the shorter summer sessions, for some class sessions you will see multiple topics covered. This is to ensure that we cover the same material that we normally would in non-summer terms.
Course Dates: Monday, July 8 – Wednesday, August 14, 2019 (6 weeks)
Class Times: Monday and Wednesday at 1:30–3:20pm
| Class | Date | Topics | Assignments |
|---|---|---|---|
| 1 | Mon, July 8 | No Class | -- |
| 2 | Wed, July 10 | Introduction to Graph Theory | Start Tutorial |
| 3 | Mon, July 15 | Graph Properties & Modeling | Challenge #1 - Midnight |
| 4 | Wed, July 17 | Graph Traversals | Quiz #1 |
| 5 | Mon, July 22 | Weighted Graph Algorithms | Challenge #2 - Midnight |
| 6 | Wed, July 24 | Dijkstra's Algorithm | Quiz #2 Tutorial Work Day |
| 7 | Mon, July 29 | Advanced Recursion & Dynamic Programming | Tutorial Due Project Proposal Due Challenge #3 - Midnight |
| 8 | Wed, July 31 | Advanced Recursion & Dynamic Programming Part 2 | Quiz #3 |
| 9 | Mon, Aug 5 | Traveling Salesman Problem | Challenge #4 |
| 10 | Wed, Aug 7 | Algorithm Classification | Challenge #5 Quiz #4 |
| 11 | Mon, Aug 12 | Final Presentations | Project Due Project Presentations Optional quiz retake |
| 12 | Wed, Aug 14 | No Class - Mock Interviews | - |
To pass this course you must meet the following requirements ( submit to course progress tracker
-
Complete all required challenges - you will be able to resubmit some of these to improve score.
-
Pass the Graph Properties and Algorithms Tutorial according to the associated Graph Tutorial Rubric
-
Pass the - Graph Properties and Algorithms Project according to the associated Project Rubric
-
Pass the 4 quizzes given during the term (1 retake allowed at the end of the term). See the Quiz Study Guide for more information.
-
Actively participate in class and abide by the attendance policy
-
Make up all classwork from all absences
The following resources were used in developing this course and are a great place to start for learning more. These resources are used through the Attribution / Share Alike license.
Much of the code you will be implementing in this class is for standard algorithms and thus is readily available from many sources. By using these resources, we can focus on deepening our understanding of the algorithms themselves and on the process of solving real world problems with these algorithms. This means it may be likely that class members will have relatively similar algorithmic implementations, however, in keeping with the Academic Honesty Policy, you are expected to always give credit to code sources (online or classmates), write each line of code yourself with full understanding, add appropriate comments, and fully test your code.