1. Show how to multiply the complex numbers a + bi and c + di using only three multiplications of real numbers. The algorithm should take a, b, c, d as inputs andproduce the real component ac-bd and the imaginary component ad+bc. There is no limit on the number of addition and subtraction operations required by your algorithm

2. Suppose we have a method of multiplying two a x a matrices using b multiply operations and c add/subtract operations. Assume that the method does not require commutativity of multiplication, so that it is applicable when the elements of each matrix are themselves square matrices.

  • Briefly describe a recursive algorithm, based on the given algorithm, for multiplying two a^k x a^k matrices
  • Let M(k) be hte number of multiply operations and P(k) the number of add/subtracat operations required by the recursive algorithm to multiply two a^k x a^k matrices. Give recurrence relations for M(k) and P(k).
  • Show that, when n is of the form a^k, the number of operations required by the recursive algorithm to multiply two n x n matrices is theta(n^{log_a(b)})

    3.

  • Give an algorithm in the spirit of the FFT for evaluating a polynomial of degree 3^k - 1 at the 3^k 3^kth roots of unity. Hint: Split the polynomial into three polynomials of degree 3^{k-1} - 1.
  • Using a recurrence relation, determine the number of operations required by your algorithm as a function of k.

    4. Give a dynamic programming algorithm for the following problem: Find a shortest path from vertex 1 to vertex n in an acyclic digraph where each edge (i,j) has a length w(i,j). Assume that the vertices are numbered 1, 2, ... , n and the every edge is directed from a lower numbered vertex to a higher numbered vertex.

    5. Let a1, a2, ... an be a sequence of integers. The sequence ai1, ai2, ... ail is called a subsequence if i1 < i2 < ... il. Such a subsequence is called increasing if ai1 < ai2 < ... ain. For example, the sequence 13, 23, 7, 42, 31, 56, 28, 45 contains the increasing subsequence 13, 23, 42, 56. The length of a subsequence is the number of elements it contains. Give a dynamic programming algorithm with running time O(n^2) for computinga longest increasing subsequence of a sequence of length n.

    6. Significant flavor removed :) You are in charge of organizing a party for "Bill Yates". Assume you are given a tree of employees each with a convivality index. which is a real number. Assuming that both an employee and his/her direct supervisor can not both be at the party, describe an algorithm to determine a set of attendees of maximum total convivality, and analyse the running time of your algorithm. Hint: for each vertex v, let F(v) be the maximum total convivality of a set of attendees including v and lying in the subtree rooted at v. Give a recurrence relation permitting the determination of F(v) for all vertices v.