Lab 3 Spring 2015

This lab is to review parts of Chapter 2 of Das Gupta et al's text book. Please go to your lab, do the problems to get your full credit for the lab.

You are welcome to try this problem ahead of time.
  1. Implement merge3sort program to split an integer array (filled with randomly chosen elements from -10000 to 10000 )into 3 parts, sort the three parts and merge them. The size of the array is given as input.
  2. Implement linear time algorithm for the maximumsubarray problem and test with the input given in Benley's paper first page.{31,-41,59,26,-53,58,97,-93,-23,84} answer is 2 and 6 as the index starts from 0. (From Home work 3, read Section 4.1 of CLRS (third edition) - Wikipedia Article on Maximum subarray problem - Here is a nice write up by Bentley Dr. Bentley )
  3. Solve the problem 2.12 in the book , How many lines, as a function of n (in theta () form ) does the following program print? Write a recurrence and solve it. You may assume n is a power of 2.
    function f(n):
      if (n>1)
           print_line("still going")
           f(n/2)
           f(n/2) 
    
    For n=1, the number of lines printed is 0. for n=2, the number of lines printed is 1. For n=4, the number of lines printed is 3 and for n=8, the number of lines printed will be 7 (verify these).. Hint: You can guess a solution and check in the recurrence relation.
  4. Optional. How many lines will be printed for the following program?
    function f(n):
      if (n>1)
           print_line("still going")
           f(n/2)
           f(n/2)
           f(n/2)
           f(n/2)