Algorithms

    Question 1. Question 1 is about the following greedy algorithms for the activity selection problem: Algorithm A 1. Input S, the set of available activities. 
2. Choose an activity A ∈ S which has the smallest duration time. 
3. Form a sub-problem S′ from S by removing A and removing any ac- tivities that are incompatible with A. 
4. Recursively choose a set of activities X′ from S′. 
5. Output the activity A together with the activities in X′. 
Algorithm B 1. Input S, the set of available activities. 
2. Choose an activity A ∈ S which overlaps as few other activities 
as possible. 
3. Form a sub-problem S′ from S by removing A and removing any ac- 
tivities that are incompatible with A. 
4. Recursively choose a set of activities X′ from S′. 
5. Output the activity A together with the activities in X′. 
It was reasonable to consider Algorithms A and B, but it turns out that these algorithms would not provide the optimal solution for every input. Show that these algorithms do not work correctly by constructing inputs on which they get the wrong answer. The answers should be provided able of activities with starting finishing time as well as in the graphical format . Question 2. Question 2 is about the following optimisation problem. An instance is a set S of positive real numbers. These represent the loca- tions of houses along a street. For example, the input S = {1.0,1.9,8.0} corresponds to a street with three houses. The first house is 1 kilometre from the left end of the street, the second house is 1.9 kilometres from the left end of the street, and the third house is 8 kilometres from the left end of the street. A wireless network can be installed anywhere on the street. It covers an interval of 1 kilometre.1 A feasible solution is a placement of wireless networks along the street which covers every house. For example, if the input is S = {1.0,1.9,8.0}, the solution with one network covering the interval [1.0, 2.0) and another network covering the interval [7.5, 8.5) is a feasible solution. The goal is to find a feasible solution with as few networks as possible. Consider the following greedy algorithm. 1. Input S, the set of house locations. 
2. Let x be the smallest element of S (S is the location of the left-most 
house on the street.) Choose the interval I = [x, x + 1). 
3. Form a sub-problem S′ from S by removing houses covered by I. 
4. Recursively choose a set of wireless network intervals X′ for S′. 
5. Output the interval I together with the intervals in X′. 
Either show that the algorithm is correct, or show that it is not correct. Hint: To prove that it is not correct, you would just have to find an input on which it gets the wrong answer, as in Question 1. To show that it is correct, you should prove that the algorithm satisfies the Greedy Choice Property and the Recursive Property as in Tutorial 1 (see also lecture notes). Note that we first defined these properties in a specific way, for activity selection problems, but here you would need to use the more general definitions on Slide 38. 1Yes, that makes a mighty strong network! 2   Question 3. In this problem the task is to move a player along a path of n squares, starting at square 1 and moving forward at each step. At any point, you can do one of three things. • Push the blue button to move the player forward 2 squares. If the player has fewer than 2 squares left on the path, then this button terminates the game and you win. 
• Push the yellow button to move the player forward 3 squares. If the player has fewer than 3 squares left on the path, then this button terminates the game and you win. 
• Push the green button to move the player forward 5 squares. If the player has fewer than 5 squares left on the path, then this button terminates the game and you win. 
There is just one catch. Each square is painted either white or red. Square 1 is pained white. If the player lands on a red square after a move, you lose. 
For example, if there are 5 squares and these are all white, apart from square 5, then a winning play would be first to push the blue button to move from square 1 to square 3. Then push either the yellow button or the green button to win. A play that starts by pushing the blue button twice would cause you to lose, because the player would land on the red square. 
Describe an efficient algorithm that determines the minimum number of buttons that you need to push in order to win. (If it is impossible to win then your algorithm should determine this.) The input to your algorithm is n, the number of squares in the path, and an array A of length n. The value of A[i] tells you whether the i′th square is painted white or red. 
Hint: Use dynamic programming. 
Question 4 Modify your algorithm from Question 3 so that, in addition to telling you how many times you need to press buttons in order to win, it also tells you the correct sequence in which to push the buttons. For example, if there are 10 squares and only squares 6 and 9 are red, the algorithm from Question 3 should determine that it takes three button pushes to win. Your algorithm from this question should determine that one way to win in three button presses is to press yellow, then yellow, then green. 
Work out the running time of your algorithms from Questions 3 and 4. Justify your answer to get a full mark. 
3 
Question 5. The last question is about pattern matching. The alpha- bet A will be {a,b,c}. The pattern P will be abcaab. The text T will be cababcaabcaab. • Construct the finite automaton (the transition function δ) that is used in the algorithm on slide 27. You need to compute δ(q,x) for every q ∈ {0, 6} (because the pattern is 6 characters long) and every x ∈ A. 
• Simulate the process of running the algorithm on the pattern P and text T. Produce a table illustrating the simulation, like on slide 30 and explain the meaning of the value corresponding to the state of automata. 
• Explain why does the calculation of the σ(Ti+1) (the new q) just depend on the current value of q and the symbol a?