Exercise 11 Theory: Greediness

NB! A minor change was done at exercise 1i) 16:44 the 1. november 2009

Exercise 1

a) Greedy algorithms is beeing used to....
Create peace and harmony at earth
Solve optimalizationproblems
Bother students who takes the course Algorithms and Datastructures
Find a correct solution to this problem

b) What recognizes a greedy algorithm?
All greedy algorithms are iterativ
All greedy algorithms always produces an global optimal solution
All greedy algorithms is recursive
None of the alternatives are correct

c) With an optimal substructur we mean that ...
an optimal solution to the subproblem is also included in an optimal solution to the main problem
an optimal solution to the main problem is an optimal solution to the subproblem
an optimal solution to the subproblem is an optimal solution to the main problem
an optimal solution to the main prolem is included in an optimal solution to the subproblem

d) With greedy choice property we mean that...
an global optimal solution can be achieved by just taking an global optimal decision
an global optimal solution can be achieved by taking a local optimal decision
an global optimal solution can be achieved by taking a random decision since the problem is optimal
an global optimal solution can be achieved by taking a random decision since the subproblem is optimal

e) Does every decision during a greedy algorithm have to be unchangeable?
No
Yes
Nei, if they are local optimal
Yes, if they are local optimal

f) Does every decision during a greedy algorithm have to agree with the conditions?
No
Yes
Nei, if they are local optimal
Yes, if they are local optimal

g) What does Greedy Algorithms and Dynamic Programming have in common?
Both are solved top-down
Both ar solved bottum-up
Both exploit an optimal substructure
Both exploit recursion

h) Which of the following algorithm is not greedy?
Dijkstra
Floyd-Warshall
Prim
Kruskal
None of the alternatives are correct, they are all greedy algorithms

i) The following is due to an greedy algorithm to the Activity-Selection Problem (p.421  in Cormen).
   If we choose the activity that starts last, instead of the one that finishes first, the algorithm wil...
not be greedy any more
be greedy, but don't have an optimal solution
be greedy, and have an optimal solution
go into an infinite loop

j) which of the following problems will not allways give an optimal solution if we use a greedy algorithm?
"Fractional Knapsack Problem"
All-to-all "Shortest Path Problem"
"Minimum Spanning Tree"
"Traveling Salesman Problem"


Exercise 2

a) Use Huffmann's algorithm (pg. 388 in Cormen), with the following frequencies

a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21

Notice that if there are one or more equal values when you build the tree,
a letter can get different values depending on which is chosen first. In this
example 'a' can take 4 different values. Which value is not a possible value
for 'a'?

- 1111111
- 1111110
- 1111100
- 1111101
- 1110111

b) If 'a' has been given the value 1111111, what is the decoded message from the
sequence

	01101111111111111011110

- abhcd?
- hfabd?
- fbhcd?
- hfbda?
- The message does not correspond to a prefix traversal?

c) What is the maximal heigth of a huffmann tree? (n = numbers of symbols to code)

- log(n)
- log2(n)
- n
- n-1
- 2n
- 2*n

Exercise 3

Professor Midas drives his car from Bodø to Oslo, along E6. With a full gas tank
he can drive n kilometer(s), and Professor Midas has a map with the distances 
between the gas stations on his route. The car has f liter(s) of petrol when he starts.
The number of gas stations along the route is B.

You may assume that Professor Midas always drives closer to Oslo.

a) Is there a greedy algorithm for this problem?

- No, the problem does not have optimal substructure
- Yes, the problem can easily be solved with worst case linear run time, Theta(B)
- No, locally optimal choices will not give a globally optimal solution
- Yes, but the problem can not be solved faster than Theta(B log(B)) in worst-case

b) Which of the following algorithms solve the problem most effeciently?

- Make a graph where all gas stations, Bodø and Oslo are nodes, and edges between
  each nodes that can be reached from each other with full tank. Use a DFS
  (Depth-First-Search) from Oslo and finish the search when Oslo is found.
- For each gas station one passes, first check if the next gas station is reachable
  with the remaining amount of gas. If this is not the case, fill the tank at this 
  gas station.
- For each gas station, check if it is possible to get from Bodø to Oslo, if this
  gas station is removed
- Each time one fills the tank, do a binary seach for the next station which is 
  fartherst away, but reachable. Then drive to this gas station and fill the tank, 
  and repeat the procedure untill one reaches Oslo

Exercise 4

Given n positive floating point numbers x[1]...x[n], we want to find a parantheses
placement as given in the following example

(((x[1] + x[3]) + (x[2] + x[5])) + x[6])

which minimize the expression

p(1)*x[1] + p(2)*x[2] + … + p(n)*x[n]

where p(i) gives the parantheses depth of floating point number x[i].
(The number of parantheses outside x[i])

Notice that both the order of the numbers and the parantheses is chosen
freely.

In the example above we have, p(1) = p(2) = p(3) = p(5) = 3 and p(6) = 1.

In this problem we will consider the example given by

x[1] = 7/20
x[2] = 3/20
x[3] = 2/5
x[4] = 1/4
x[5] = 1/10
x[6] = 1/10
x[7] = 3/20

a) Which of the following design methods would you use to solve the problem efficiently?

- Divide and conquer
- Dynamic programming
- Greediness
- None of the above

b) What is the value of p(3) and p(5), when the expression is miminized?

- p(3) = 3 og p(5) = 5
- p(3) = 1 og p(5) = 4
- p(3) = 2 og p(5) = 2
- p(3) = 2 og p(5) = 4 

c) What is the minimal value of the expression?
- 2,55
- 4,70
- 3,30
- 3,95