## Exam Information

Login / Sign Up to View Document

## 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...

© Copyright 2021 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.