DOC PREVIEW
BU CS 333 - Assignment 2

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS333 Assignment 2Instructor: KD [email protected] Name:• This homework is due at the beginning of the class on March 10, 2009. Timely submission ofyour homework is recommended, because there will be 10% late penalty per day.• Always try to be precise and concise. Finally, always make sure your answers are readable!1: [20 points] Using the quicksort algorithm in the textbook (pages 60 − 66), showhow to sort the following list of integers.1, 2, 3, 4, 5, 6, 7(a) [10 points] Use the first element in a (sub)list as the pivot item. Show the sorting actionsstep by step.(b) [10 points] Randomly choose an element in a (sub)list as the pivot item. Show the sortingactions step by step.2: [20 points] Do Exercise 2.6. (Algorithm: 10 points and Time complexity analysis:10 points)3: [10 points] Do Exercise 2.11.4: [10 points] The behavior of a recursive algorithm is expressed by the followingrecurrence relations.T (n) = 7T (n/5) + 10n for n > 1T (1) = 1(a) [5 points] Find T(125).(b) [5 points] What is the time complexity of this algorithm? [Hint: Refer to Theorem B.5 inAppendix B.]5: [10 points] Do Exercise 2.7.6: [10 points] You need to write a program to compute the nthFibonacci term forinput n, which is a positive integer greater than 1. Answer the following questions.1HW2 CS333Instructor: KD [email protected](a) [2 points] Will you use Algorithms 1.6 or 1.7?(b) [8 points] Justify your choice in part (a).7: [10 points] Do Exercise 1.28.8: [10 points] Do Exercise


View Full Document

BU CS 333 - Assignment 2

Download Assignment 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Assignment 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Assignment 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?