1. Engineering
  2. Computer Science
  3. 1 some short answers a what is an asymptotically tight...

Question: 1 some short answers a what is an asymptotically tight...

Question details

1. Some short answers (a) What is an asymptotically tight upper bound on the recurrence (n) 4T, (n/3) + 0(n2), T (1)-0(1)? And for the recurrence T2 (n)-27T2(n/3) O(n2), T3(1)-O(1)? (b) Eureka! A woman named Nessarts figured out how to multiply 4 × 4 matrices using 32 scalar mul- tiplications and 67 additions and subtractions. She finds that the elements of the matrix dont have to be scalars_ her method also works on large matrices split into 16 blocks (4 x 4). How fast can she multiply n x n matrices? (You can assume n is a power of a convenient number and use asymptoti<c notation.) (c) In a max-flow problem, we have found a minimum cut and it contains an edge e. Prove or give a (d) Express the problem of maximizing min(x+y, y+w, 3r+w) where r+y+w 1 as a linear program (e) In the vertex cover problem, the input is an undirected graph G - (V, E) and the goal is to find the counterexample: If we increase the capacity of e, the value of the max flow will increase smallest set SCVof vertices such that every edge touches a vertex in S. Here as an integer linear program for this problem min Vv E V,x, E 0,(*) Describe how to use a solution to the linear program, with the integrality constraints (*) replaced by 0 u 1, to provide a 2-approximation for the vertex cover problem on a general (non-bipartite) graph. (You are not allowed to look at the graph, only the values of xu in your algorithm.)

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution