Description

1. a typed preamble that contains:
(a) the list of people you worked with people for each question (if applicable),
(b) the sources you used,
(c) and if you wish, your impressions about the assignment (what was fun, what was difficult,
why…);
2. your solutions for all problems, typed (not handwritten)
1 Divide and Conquer
Let A be an array of n relative integers. We want to find the maximum sum of contiguous elements, namely, two indices i and j (1 ≤ i ≤ j ≤ n) that maximize Pjk=i A[k].
a) If the values in the array are A[1] = 2,A[2] = 18,A[3] = −22,A[4] = 20,A[5] = 8,A[6] = −6,A[7] = 10,A[8] = −24,A[9] = 13, and A[10] = 3, can you return the two indices and the corresponding optimal sum?
b) Design an algorithm that returns the maximum sum of contiguous elements with a divide-and-conquer algorithm.
2 Master Theorem
For each of the following recurrences, give the asymptotic solution if the recurrence can be solved with Master Theorem. Otherwise, briefly explain why Master Theorem is not applicable. a)
b)
c)
d)
e)
1
3 Dynamic Programming: George Learns Algorithms
{82,77,65,89,83,68,88,71,91,90}
George does not want to restrict himself to only contiguous years, since then it looks like he is never able to improve his performance for longer than 2 years ({65,89} or {68,88} or {71,91}). If he allows himself to leave out whatever years he likes, he could see his grade improving over the following 3 scores: {77,89,91}. Or better yet, the following 4 scores: {77,83,88,91}.
Feeling better about himself already, George defines a subsequence to be the original sequence with some (or all) of the elements removed. Now, he enlists the help of one his clever classmates from this year’s algorithms class (you) to find his longest subsequence of improving grades.
2. Write down a recurrence relation for this problem.
3. Design a bottom up DP algorithm to solve the problem. Include the time and space complexity of this algorithm to conclusively show George that your algorithm is better than an exhaustive search.
4 Optimizing Deep Learning
Deep learning is an emerging field in Computer Science that is finding applications with a wide spectrum of tasks, from identifying cats in images to beating Lee Sedol at Go. Almost all deep learning architectures rely on multiplying a large number of huge matrices.
For example, if the dimension of matrix A is (10,20), matrix B is (20,5), and matrix C is (5,30), then the time for computing (AB)C will be (10×20×5)+(10×5×30) = 2500 while that for computing A(BC) will be (20 × 5 × 30) + (10 × 20 × 30) = 9000.
More generally, given a series of matrices to multiply, one can enumerate all possible parenthesizations of the series in order to determine the multiplication order which takes the least total time. Can a more optimal algorithm be designed for the purpose? Justify your answer.
2