COMPSCI 61B Lecture Notes - Lecture 29: Call Stack, Binary Heap, Inductive Reasoning
1 Jun 2017
School
Department
Course
Professor
Document Summary
Autograder is basically just the tests we gave you plus a test of your tests. Labs this week will be used for review of midterm material. Today"s lecture not on midterm, but the rst 15 minutes are certainly pertinent. Both work in the absence of physical constraints on computers. Dfs and bfs both traverse entire graphs, just in a di erent order. Solving graph problems is often a question of identifying the right traversal. Goal: find the shortest paths from source vertex s to some target vertex t. Observation: solution will always be a path with no cycles (assuming non- negative weights), since this implies that the cycles can be removed to result in a shorter path which still satis es the goal. Trickier observation: solution will always be a tree. Can think of as the union of the shortest paths to all vertices. Edges in a shortest paths tree of g: v - 1 edges.
