Computer Science  >  SOLUTIONS MANUAL  >  a02-solutions - University of Manitoba COMP 3170 (All)

a02-solutions - University of Manitoba COMP 3170

Document Content and Description Below

University of Manitoba COMP 3170, Winter 2019 Assignment 2 Due Date: February 9, at 8:00pm There is no hurry. We shall get there some day. Rivers know this . . . A.A. Milne (Winnie-the-Pooh) Sub ... mit your solutions electronically via Crowdmark. The assignment will be marked out of 65 (there is also 6 bonus marks). Please read http://www.cs.umanitoba.ca/~kamalis/ winter19/infoCOMP3170.pdf for guidelines on academic integrity. Problem 1 Quick-Select [6 marks] When doing Quick-Select and Quick-Select, it is desired to have a good pivot which is almost in the middle of the sorted array. When doing the average-case analysis of Quick-Select, we considered a good and a bad case; the good case happened when the pivot was among the half middle items of the sorted array, i.e., we had n/4 ≤ i < 3n/4 (i is the index of pivot in the partitioned array). In our analysis, we provided an upper bound for the time complexity of the algorithm in the good case and showed that T(n) ≤ T(3n/4) + cn in these cases for some constant c. Since the good case happened with probability 1/2, we could prove that the algorithm runs in linear time on average (see the recursion slide 10 of lectures on selections). Change the definition of the good case and assume the good case happens when we have n/10 ≤ i < 9n/10. Provide an upper bound for T(n) and use that to show that Quick-Select runs in O(n). Hint: start by calculating the probability of good case and bad case happening. Answer: We showed in the class that for the average cost of selection algorithm on an array of size n, we have T(n) ≤ cn + 1 n X i−1 j=0 T(n − j − 1) + Xn−1 j=i+1 T(j) ! Assuming n/10 ≤ j < 9n/10 (when pivot is good), we will have n − j − 1 < T(9n/10) and j − 1 < 9n/10. Consequently, T(n − j − 1) < T(9n/10) and T(j − 1) < T(9n/10). Note that 9n/10 − n/10 = 4n/5, i.e., with probability 4/ [Show More]

Last updated: 2 years ago

Preview 1 out of 6 pages

Buy Now

Instant download

We Accept:

Payment methods accepted on Scholarfriends (We Accept)
Preview image of a02-solutions - University of Manitoba COMP 3170 document

Buy this document to get the full access instantly

Instant Download Access after purchase

Buy Now

Instant download

We Accept:

Payment methods accepted on Scholarfriends (We Accept)
Report Copyright Violation

Reviews( 0 )

SOLUTIONS MANUAL

$5.00

Buy Now

We Accept:

Payment methods accepted on Scholarfriends (We Accept)

Instant download

Can't find what you want? Try our AI powered Search

107
0

Document information

Connected school, study & course

About the document

Uploaded On

Dec 12, 2022

Number of pages

6

Written in

All

Type

SOLUTIONS MANUAL

Seller

Profile illustration for jimmydarts
jimmydarts

Member since 4 years

80 Documents Sold

Reviews Received
4
2
1
1
5
Send Message
Additional information

This document has been written for:

Course

Computer Science

Category

SOLUTIONS MANUAL

Uploaded

Dec 12, 2022

Downloads

 0

Views

 107

Document Keyword Tags

More From jimmydarts

View all jimmydarts's documents »

Recommended For You

Get more on SOLUTIONS MANUAL »
$5.00
Buy Now
What is Scholarfriends

Scholarfriends.com Online Platform by Browsegrades Inc. 651N South Broad St, Middletown DE. United States.

Get to know us
About Us
Privacy Statement
Refund Policy
Terms and Conditions
Contact Us
Blog
We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter
Useful links
  • Join our Subreddit
  • Solutions Manuals for Accounting, Business, Economics and Management Text Books. The Popular and the Latest.
  • Popular NURSING Test Banks
  • Courses
  • Categories
    • We accept

    payment cards

    Copyright © Scholarfriends · High quality services·