CS3364 - Design and analysis of Algorithms, Summer I / 2004

Homework 1

This is due Friday, June 11, 2004, 10 am

• Bring this recurrence relation in closed form (assume n is a power of 3):
  T(n) = 4T(n/3)+2n-1
  T(1) = 2
• Evaluate the original reccurence relation and the closed form for n=27. Show that both are equivalent. Show your work!
• Solve Problem 400 from the Valladolid Programming Contest Problem Set, to be found at: http://acm.uva.es/cgi-bin/OnlineJudge?Volume:4. Do not use a preprogrammed sort, but implement the sorting using mergesort. Since the emphasis is on the sorting, the formula for the presentation is
  int cols = ((60-maxlen)/(maxlen+2))+1;
  int rows = (v.size()/cols);
  if ((v.size()%cols)>0) rows++;
  Use any programming language, however, if you use C, C++, Java or Pascal you can have the online judge test your program.
  Give the recurrence relation for the sorting part of your program for the number of data comparisons. You do not need to put it in closed form.
• Solve Problem 694 from the Valladolid Programming Contest Problem Set, to be found at: http://acm.uva.es/cgi-bin/OnlineJudge?Volume:6. Use a recursive function to evaluate the value of the collatz function, do not use a for loop.
  Give the reccurence relation for your collatz function. Count the number of multiplications (division counts as multiplication) if the number is called with a parameter n. Please show all 4 cases. You do not need to put this relation in closed form.

Submit the mathematical part either electronically (please use PDF format) or on paper in class.

Submit the programming part eletronically, either by putting them on the unix accounts in the cs department in a folder that I can read, or by sending them via email to max@berger.name