Question 6 [1 A) Match each of the following techniques with its definition: Technique 1. Divide & Conquer 2. Dynamic Programming 3. The Greedy technique 4. Backtracking 5. Branch and Bound Definition a) is a technique used to solve difficult optimization problems, where a partial solution can only be expanded based on its bound. b) is a technique that builds the solution iteratively, by finding, in each iteration, a candidate that satisfies a local optimum, in the hope that the complete solution will be a global optimum. c) consists of building the state space tree of all solutions, but prunes the tree by not expanding on the non-promising nodes, thus improving the time efficiency. d) is a technique that divides the problem into subproblems, solves the subproblems then combine their solution to form the complete solution to the problem. e) is a technique based on the principal that states that in an optimal sequence, every subsequence is also optimal. B) Answer the following: 1. (T/F) Fractional Knapsack problem can be solved in polynomial time. 2. (T/F) Divide and Conquer always improves the time complexity. 3. (T/F) If applied on a sorted array, Quicksort that chooses the first element as pivot is 0 (n²). 4. (T/F) The Huffman code is considered a lossy compression technique. 5. (T/F) Kruskal's algorithm for finding the Minimum Cost Spanning Tree depends on which vertex we start from. 6. (T/F) Dijkstra's algorithm can find shortest paths in a directed graph with negative weights, but no negative cycles. 7. (T/F) The Dynamic Programming algorithm for finding an Optimal Binary Search tree always gives the BST with the minimum average search time. 8. (Short answer – 2 points) Given the 3 matrices A, B C, with dimensions 4x5, 5x2, 2x3 what is the number of multiplications needed to find the product ((A x B) x C)?

Question 6 [1 A) Match each of the following techniques with its definition: Technique 1. Divide & Conquer 2. Dynamic Programming 3. The Greedy technique 4. Backtracking 5. Branch and Bound Definition a) is a technique used to solve difficult optimization problems, where a partial solution can only be expanded based on its bound. b) is a technique that builds the solution iteratively, by finding, in each iteration, a candidate that satisfies a local optimum, in the hope that the complete solution will be a global optimum. c) consists of building the state space tree of all solutions, but prunes the tree by not expanding on the non-promising nodes, thus improving the time efficiency. d) is a technique that divides the problem into subproblems, solves the subproblems then combine their solution to form the complete solution to the problem. e) is a technique based on the principal that states that in an optimal sequence, every subsequence is also optimal. B) Answer the following: 1. (T/F) Fractional Knapsack problem can be solved in polynomial time. 2. (T/F) Divide and Conquer always improves the time complexity. 3. (T/F) If applied on a sorted array, Quicksort that chooses the first element as pivot is 0 (n²). 4. (T/F) The Huffman code is considered a lossy compression technique. 5. (T/F) Kruskal's algorithm for finding the Minimum Cost Spanning Tree depends on which vertex we start from. 6. (T/F) Dijkstra's algorithm can find shortest paths in a directed graph with negative weights, but no negative cycles. 7. (T/F) The Dynamic Programming algorithm for finding an Optimal Binary Search tree always gives the BST with the minimum average search time. 8. (Short answer – 2 points) Given the 3 matrices A, B C, with dimensions 4x5, 5x2, 2x3 what is the number of multiplications needed to find the product ((A x B) x C)?