This course covers graph theory, data structures, algorithms, and analysis. Key concepts include graph traversals, pathfinding, 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.
Course Delivery: Synchronous | 7 weeks | 18 sessions
Course Credits:
Synchronous: 3 units | 37.5 Contact Hours/Term | 92 Non-Contact Hours/Term | 129.5 Total Hours/Term
Students by the end of the course will be able to ...
- Describe common graph algorithms including graph traversals, pathfinding, greedy algorithms, recursion, and dynamic programming.
- 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.
Course Dates: Monday, May 31 – Friday, July 16, 2021 (7 weeks)
Class Times: Monday, Wednesday, Friday at 2:15pm–4:00pm (19 class sessions)
| Class | Date | Topics | Assignments Due |
|---|---|---|---|
| - | Mon, May 31 | No Class - Memorial Day | |
| 1 | Wed, June 2 | Introduction to Graph Theory | |
| 2 | Fri, June 4 | Lab | |
| 3 | Mon, June 7 | How to Proof | Module 1 |
| 4 | Wed, June 9 | Graph Traversals | |
| 5 | Fri, June 11 | Lab | Module 2 |
| 6 | Mon, June 14 | Topological Sort | |
| 7 | Wed, June 16 | Graph Applications | |
| 8 | Fri, June 18 | Lab | Module 3 |
| 9 | Mon, June 21 | Weighted Graph Algorithms | |
| 10 | Wed, June 23 | Weighted Graph Algorithms | |
| 11 | Fri, June 25 | Lab | Module 4 Midterm (you must have modules 1-4 turned in) |
| 12 | Mon, June 28 | Recursion & Dynamic Programming | |
| 13 | Wed, June 30 | Recursion & Dynamic Programming | |
| 14 | Fri, July 2 | Lab | Module 5 |
| - | Mon, July 5 | No Class - Independence Day Observed | |
| 15 | Wed, July 7 | NP-Complete Algorithms | |
| 16 | Fri, July 9 | Lab | Module 6 |
| 17 | Mon, July 12 | Practice Problems | |
| 18 | Wed, July 14 | Practice Problems | |
| 19 | Fri, July 16 | Lab | Final Project |
Each lesson will have an associated module consisting of review, conceptual, and coding activities as well as interview prep related to the topic. At the end of each week you will turn your module work into gradescope for feedback and a score.
Students will also create a [final project] applying and implementing an advanced graph related topic
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 Make School 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.
To pass this course you must meet the following requirements:
- Pass all modules with a score 70% or higher
- Your lowest module will be dropped
- Complete the final project with a score of 70% or higher
- Actively participate in class and abide by the attendance policy
- Make up all classwork from all absences
- This course will use a self paced format
- You will be given recommended dates to turn assignments in to stay on track, but you can turn in any assignment later than the recommended date with no penalty provided Modules 1-3 are turned in no later than midterm (Fri June 25th) and modules 3-6 and the final project are turned in no later than the last day of class (Fri July 16th)
- You can resubmit any assignment after receiving feedback to improve your score provided it is turned in no later than the last day of class (Fri July 16th)
- Assignments should be completed by the recommended date in the above schedules section in order to receive timely feedback. Students falling behind should connect with the instructor for help staying on pace!
- The absolute last date to turn in Modules 1-3 is Fri June 25th and the last date to turn in modules 3-6 and the final project is Fri July 16th
- Any assignments not complete by the above midterm Fri June 25th and final day of class Fri July 16th dates will receive a score of 0
- Lectures will be given during the first hour of class and will be optional (2:15 pm - 03:15pm on M & W)
- Labs will be during the last portion of the class and all of Friday sessions and attendance will be required (3:30 - 4:00 pm M & W, 2:15 pm - 04:00pm F)
Any additional resources you may need (online books, etc.) can be found here. You can also find additional resources through the library linked below:
At Make School, we highly encourage collaboration between students on assignments. Working with other people is the best way to learn!
However, there's a big difference between collaboration (writing code together with another person) and plagiarism (copying code from a classmate or outside source without providing proper attribution).
Here are some guidelines to follow in order to avoid plagiarism:
- If you are looking at an outside source for help, close the window containing the code before writing your own solution.
- Do not write down a line of code unless you completely understand how it works. (This is true even if the source you're referencing is the lesson slides/examples/etc!)
- If your code is still similar to an outside source or another student's, provide attribution by adding a comment to your code explaining where it was taken from.
We take academic honesty very seriously at Make School. The consequences for violating the policy are as follows:
- You will be required to write a Self-Reflection Letter to reflect on how your actions affected others.
- If this is your first offense, you may be permitted to redo the assignment for a reduced grade (at the instructor's discretion).
- The incident will be added to your permanent record at Make School and you may be placed on a Participation Improvement Plan (PIP).
For subsequent offenses, more serious consequences may be considered. For more information, please see Make School's academic honesty policy.
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.
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
- Online Learning Tutorial - How to succeed in online learning at Make School
- Student Handbook - Guidelines, policies, and resources for all Make School students