Graph Algorithms: Monday, 2/27 - Friday, 3/3

Post date: Feb 26, 2017 6:56:21 PM

We are wrapping up our study of Graph Theory and of Discrete Mathematics this week. As a reminder, your Math Exploration is due to ManageBac at 10 PM on Monday, March 6th. Here again is the rubric for the Math Exploration, which includes some notes about what to include in which sections.

Monday, 2/27 - we looked at the Travelling Salesman Problem and found lower and upper bounds for solutions to these types of problems. Here are the slides from class. Here is the worksheet from class. Your HW is to work on your Math Exploration.

Tuesday, 2/28 - we did Travelling Salesman problems. Here are the problems from class. Your HW is to work on your Math Exploration.

Wednesday, 3/1 and Thursday, 3/2 - we practiced all the graph theory algorithm problems we've seen in preparation for our exam on Friday 3/3. Here are the IB style problems from class. Your HW is to work on your Math Exploration and study for your exam.

Friday, 3/3 - we have an exam on Graph Theory algorithms: Kruskal's algorithm and finding minimum spanning trees, Dijkstra's algorithm and finding minimum length paths, the Chinese Postman Problem and finding Eulerian circuits or other closed walks which visit all edges at least once, the Nearest Neighbor Algorithm for finding Hamiltonian cycles and an upper bound for the Travelling Salesman Problem and finally the Deleted Vertex Algorithm for finding a lower bound for the Travelling Salesman Problem.

Your HW is to work on your Math Exploration. As a reminder, your Math Exploration is due to ManageBac at 10 PM on Monday, March 6th. Here again is the rubric for the Math Exploration, which includes some notes about what to include in which sections.