SFWRENG 2C03 Study Guide - Midterm Guide: Topological Sorting, Time Complexity, Prims
2 Aug 2018
School
Department
Course
Professor
Document Summary
Greedy choices made so far are part of a universal, optimal solution, s (greedy choice. Imagine that you"re robbing a gold vault and trying to fill your backpack with soft gold bars; edge is item, node is state. Greedy algorithm: you always pick the most valuable item, the shortest edge, so you"re greedy, like the thief in the gold vault e. g. think of booze. At a party with free booze, if you want to get drunk fast drink whatever"s in front of you. Elements of a greedy algorithm: property). (optimal substructure). An advantage over divide and conquer algorithms, you have a choice of where you begin. Fractional knapsack: you may pick up parts of items, thus you look for the item with the highest money:weight ratio. 0-1 knapsack: only pick the whole items that fit; take it or leave it no middle way, buddhist crap; think of it like binary.
