CSC 345 Lecture Notes - Lecture 5: Greedy Algorithm, Optimal Substructure, Dynamic Programming
16 Mar 2016
School
Department
Course
Professor
Document Summary
P(v) = u for each edge (u,v) in e[g] if ( d(v) > d(u) + weight(u,v) ) //this finds if there are any. //negative loops, because if anything changes in an extra. We will go through the nodes alphabetically, but you don"t have to. 3 can be replaced by -3, so there is a negative loop, so return false. You do use the updated values as soon as they are available. 0 inf inf predecessor(*) edge pass1 pass2 negative cycle. 0 inf inf inf predecessor(*) edge pass1 pass2 pass3. Divide and conquer: a) divide the problems into sub problems (2 or more, b) solve the subproblems, c) use the solutions to the subproblems to solve the original problem, examples, quicksort, merge sort: Example: assembly line scheduling problem: each assembly line has n stations (j = 1, 2, , n) denote the jth station in assembly line i as s_(i,j). But if you store the sub problems, then it is o(n)
