Week 5 Flashcards
What are the 3 fundamental techniques?
- The Greedy Method
- Divide and Conquer
- Dynamic Programming
Describe the Greedy Method?
- a problem solving strategy used in optimisation problems
- involves making locally optimal choices at each step in the hope these choices lead to a globally optimal solution
- so at every decision point, it selects the best available option without considering overall future consquences
Why might we not use a greedy method approach?
- because this doesn’t guarantee the optimal solution
How does the greedy method decide what is the best/optimal local decision to make?
- it uses a given criteria to decide what the best choice to make is
Give examples of problems solved by the greedy method
- Fractional knapsack problem
- interval scheduling
- task scheduling
- minimum spanning trees
- shortest paths (Dijkstra’s algorithm)
- change making (smallest number of coins)
- maximum spacing of k-clustering
What is the fractional Knapsack Problem?
Have a set S of n items, each item has a positive benefit bi and weight wi
- goal is to find the maximum benefit subset that does not exceed total weight W
- we can take arbitrary fraction xi of each item where each fraction is 0 <= xi <= wi
- the sum of all the fractions must be <= max W
What is the objective function for solving the fractional knapsack problem?
- the total benefit of items taken is determined by the sum of each item whose fraction xi/wi of it’s benefit to the solution
What is the general method for solving the FKP?
- Compute the value index for each item = vi = bi/wi
- select items to pack into the knapsack by choosing from highest value index to lowest
- once we reach the max weight W, we stop
What is the greedy element in the greedy method’s solution for the FKP?
- that in each iteration locally we’re choosing the next item to pack and our greedy criteria is to take the item with the highest value index
What amount do we add to the total benefit after an item is packed?
- We add the value index multiplied by xi (we don’t add bi to the benefit)
- for example if item 3 has vi = 3/2 and we add item 3’s full wi of 2, we add 3/2 * 2 = 3 to the total benefit
What is the {0,1} knapsack problem?
Similar to the Fractional knapsack problem, however only a whole item’s weight can be packed into the knapsack
- so an item can only get packed or not rather than a fraction of it
- optimal solution isn’t always found with the greedy method
- can be solved by dynamic programming
What is interval scheduling?
- have a set T of n tasks and a single machine that can process these tasks
- goal is to select a subset of tasks to maximise the number of tasks we can schedule
- the tasks cannot overlap (conflict)
- ni is the start time and nf is the finish time
- two tasks are non-conflicting if fi<=fj or fj<=fi
How do we use a greedy algorithm to solve the interval scheduling problem?
- we order tasks by completion/finish time, so we put them in order of finishes first to finishes last.
- we then take the task that finishes first and add it to the schedule, we then remove any task that conflicts with this added task
- we then repeat doing this until there are no tasks left.
What data structure can we use to implement the solution of a greedy algorithm for both the fractional knapsack problem and the interval scheduling problem
- We can use a heap data structure for the implementation of these problems
- root holds highest value index in FKP
- root holds smallest finish time in ISP
What is clustering?
- when we tr to group together a collection of n objects based on the idea of distance
- we have n objects: O1, O2, …On and a distance function that compares how far a pair of objects are.
- this distance function has 3 axioms (properties)
1. d(Oi,Oi) = 0 - distance between identical objects = 0
2. d(Oi, Oj) > 0 for all i != j - distance between different objects must be positive
3. d(Oi,Oj) = (Oj, Oi) - distance between a and b is the same as distance between b and a - We want to group objects into k (non empty) clusters C1,…Cn where k «_space;n (much less than)
