Past Exam for CS 404 - Analysis Of Algorithms at Northeastern Illinois University (NEIU)

Exam Information

Material Type:Final
Class:CS 404 - Analysis Of Algorithms
Subject:Computer Science
University:Northeastern Illinois University
Term:Fall 2003
  • Following List
  • Combinations
  • Performance
  • Elimination
  • Time Complexity
  • Following Numbers
  • In the Round
  • Binary Search
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

Sample Document Text

CS 404-31 - Analysis of Algorithms Final Exam December 3, 2003 1. Use Binary Search Recursion to search for the integer 26 in the following list of integers. Show the actions step by step. 15 26 39 41 44 50 55 60 2. Suppose that there are n = 2k teams in an elimination tournament, in which there are n=2 games in the rst round, with the n=2 = 2k 1 winners playing in the second round and so on. (a) Develop a recurrence equation for the number of rounds in the tournament (b) How many rounds are there in the tournament when there are 256 teams? (c) Solve the recurrence equation of part (a). 3. Sort the following list showing the actions step by step, by using (a) Mergesort (b) Quicksort 252 176 315 121 343 276 122 305 4. Write an algorithm that prints out all the subsets of four elements of a set of n elements. The elements of this set are stored in a list that is the input to the algorithm. De ne its basic operations and study its performance. Is that performance an every-case time complexity...
155, "/var/app/current/tmp/"