hw3-2

pdf

School

University of British Columbia *

*We aren’t endorsed by this school

Course

221

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by AdmiralStrawCrocodile17

Question 2: Assigned Parking You're in charge of assigning parking spots to tour buses at the Capilano Suspension Bridge. The parking spots are numbered 1,2,3,...,min order of distance from the entrance. At the start of the day, all spots are empty. When a bus arrives, the bus driver tells you the maximum distance from the entrance (i.e. parking spot number) he is willing to park at. He is equally happy to park in any spot numbered less than or equal to that number. If no such spot exists, he will leave (and take his bus to the Capilano Fish Hatchery down the road). You want to maximize the number of buses that park at the bridge. Every bus stays for the entire day. Let d; be the maximum parking spot number that the ith bus to arrive will park at (forz = 1,2,...,n). What is the best spot to tell the first bus driver to park in? (a) dl —1 (b) d1 (] (© T (It may help to consider the case when the first three buses have d; = 3,ds = 2, and d3 = 1) As the parking spots fill up, you need to be able to calculate the best acceptible parking spot number for the next bus that arrives, or tell the bus no such spot exists. You want to do this quickly and after thinking about it for a while, you decide that a disjoint- sets structure is the way to go. This is the key property you would like to maintain at all times: For each set S in the set of disjoint sets containing all spots, the representative of S (the root of the up-tree for S) is the best open spot for a bus that asks for a spot within the set S of spots. To find where the ith bus should park, you find its maximum spot d; in the set of disjoint sets of spots. This gives you the root of the up-tree for that set, which is the spot d where you tell the driver to park. Example Here is part of the disjoint-sets structure (shown as up-trees) that represents the state of assigned parking spots at some point during the day. The numbers in the circles are the parking spots. What parking spots are free (do not contain buses)? s() 6 7() 8 9 (] « 1] 12 13 14 Select all possible options that apply. @ How do you update the disjoint sets structure after a bus parks in spot d? The operations available on the disjoint-sets structure are: o create_set(a): Adds a new disjoint set to the disjoint-set structure containing only a with root a. e simple_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making a the root of the union. e size_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the larger tree the root of the union. e rank_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the taller tree the root of the union. o find(a): Return the root of the disjoint set containing a. To indicate that spot d is no longer available and to arrange that any future request for spot d will return the proper open spot, perform simple v (_100%] union( find(d-1) v (_100%). d v [Lox)). Fill in the blanks with the simplest correct approach. In the example above, did the bus with maximum spot 13 arrive before the bus with maximum spot 12? Yes No (]

What sets do you initially create? Assume that you may only create sets at the start of the day. Provide values for A and B in the following code to initialize your disjoint-sets structure. for( d = A ; d <= B; d++ ) { create_set(d); A= 0 @ ) & n o ) How to detect that no acceptible parking spot exists for a bus with maximum spot d? Provide the value for C in the following code to detect if a bus with maximum acceptible spot d can park at the bridge. L if( find(d) == C ) cout << "No acceptible spot exists!" C= 0 @ () (You might want to check that your answers for A and B (above) are consistent with this.) Runtime Suppose 71 buses ask to park and there are m parking spots. What is the maximum number of calls made to the following functions by your approach? O( m @ ) createSet calls. ©O( n @ ) union calls. (For this part only, you may assume m > n.) O( n (@) ) find calls. What is the worst case runtime for all of this? (Assume no path compression was performed. Your anwser should reflect the appropriate type of union chosen to solve the answer above; so double-check that answer carefully!) (a) O(m + n) (b) ©(m + nlog™ n) (c) ©(m + nlogn) d) O(m +n?)(] (e) O(mlogn) This question is complete and cannot be answered again. Correct answer What is the best spot to tell the first bus driver to park in? (b) dy (It may help to consider the case when the first three buses have d; = 3,dy = 2, andds = 1)) As the parking spots fill up, you need to be able to calculate the best acceptible parking spot number for the next bus that arrives, or tell the bus no such spot exists. You want to do this quickly and after thinking about it for a while, you decide that a disjoint- sets structure is the way to go. This is the key property you would like to maintain at all times: For each set S in the set of disjoint sets containing all spots, the representative of S (the root of the up-tree for S) is the best open spot for a bus that asks for a spot within the set S of spots. To find where the ith bus should park, you find its maximum spot d; in the set of disjoint sets of spots. This gives you the root of the up-tree for that set, which is the spot d where you tell the driver to park. Example

Here is part of the disjoint-sets structure (shown as up-trees) that represents the state of assigned parking spots at some point during the day. The numbers in the circles are the parking spots. What parking spots are free (do not contain buses)? 5 7 10 11 How do you update the disjoint sets structure after a bus parks in spot d? The operations available on the disjoint-sets structure are: e create_set(a): Adds a new disjoint set to the disjoint-set structure containing only a with root a. e simple_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making a the root of the union. e size_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the larger tree the root of the union. e rank_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the taller tree the root of the union. e find(a): Return the root of the disjoint set containing a. To indicate that spot d is no longer available and to arrange that any future request for spot d will return the proper open spot, perform simple _union( find(d-1) ,/d ). Fill in the blanks with the simplest correct approach. In the example above, did the bus with maximum spot 13 arrive before the bus with maximum spot 12? No What sets do you initially create? Assume that you may only create sets at the start of the day. Provide values for A and B in the following code to initialize your disjoint-sets structure. for( d = A ; d <=B; d++ ) { 4 create_set(d); } | A= 0 B=m How to detect that no acceptible parking spot exists for a bus with maximum spot d? Provide the value for C in the following code to detect if a bus with maximum acceptible spot d can park at the bridge. J ! if( find(d) == C ) cout << "No acceptible spot exists!"” i ' u C=o90 (You might want to check that your answers for A and B (above) are consistent with this.) Runtime Suppose n buses ask to park and there are m parking spots. What is the maximum number of calls made to the following functions by your approach? ©( m ) createSet calls. ©( n ) union calls. (For this part only, you may assume m > n.) ©( n ) find calls. What is the worst case runtime for all of this? (Assume no path compression was performed. Your anwser should reflect the appropriate type of union chosen to solve the answer above; so double-check that answer carefully!) (d) ©(m + n?) Submitted answer 2 Submitted at 2023-12-05 11:29:54 (PST) (0] (e What is the best spot to tell the first bus driver to park in?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

(b) dy (It may help to consider the case when the first three buses have d1 = 3,d2 = 2, andd3z = 1. As the parking spots fill up, you need to be able to calculate the best acceptible parking spot number for the next bus that arrives, or tell the bus no such spot exists. You want to do this quickly and after thinking about it for a while, you decide that a disjoint- sets structure is the way to go. This is the key property you would like to maintain at all times: For each set S in the set of disjoint sets containing all spots, the representative of S (the root of the up-tree for S) is the best open spot for a bus that asks for a spot within the set S of spots. To find where the ith bus should park, you find its maximum spot d; in the set of disjoint sets of spots. This gives you the root of the up-tree for that set, which is the spot d where you tell the driver to park. Example Here is part of the disjoint-sets structure (shown as up-trees) that represents the state of assigned parking spots at some point during the day. The numbers in the circles are the parking spots. T (9 (19 s ) 7() 10(]) 1) What parking spots are free (do not contain buses)? How do you update the disjoint sets structure after a bus parks in spot d? The operations available on the disjoint-sets structure are: e create_set(a): Adds a new disjoint set to the disjoint-set structure containing only a with root a. e simple_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making a the root of the union. e size_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the larger tree the root of the union. e rank_union(a, b): Takes the roots a and b of two up-trees and unions their sets together, making the root of the taller tree the root of the union. e find(a): Return the root of the disjoint set containing a. To indicate that spot d is no longer available and to arrange that any future request for spot d will return the proper open spot, perform simple _union( find(d-1) , d ). Fill in the blanks with the simplest correct approach. In the example above, did the bus with maximum spot 13 arrive before the bus with maximum spot 127 No (_100%) What sets do you initially create? Assume that you may only create sets at the start of the day. Provide values for A and B in the following code to initialize your disjoint-sets structure. for( d = A ; d <= B; d++ ) { create_set(d); } A= o] (o) 8= (1) How to detect that no acceptible parking spot exists for a bus with maximum spot d? Provide the value for C in the following code to detect if a bus with maximum acceptible spot d can park at the bridge. | if( find(d) == C ) cout << "No acceptible spot exists!"” C= o (_100%] (You might want to check that your answers for A and B (above) are consistent with this.) Runtime

Suppose n buses ask to park and there are m parking spots. What is the maximum number of calls made to the following functions by your approach? O( m (__100%]) createSet calls. ©( n (__100%]) union calls. (For this part only, you may assume m > n.) O( n (_100%)) find calls. What is the worst case runtime for all of this? (Assume no path compression was performed. Your anwser should reflect the appropriate type of union chosen to solve the answer above; so double-check that answer carefully!) (d) @(m + n?) Submitted answer 1 Submitted at 2023-12-05 00:57:14 (PST) saved, not graded | [ e ] [ show v l Homework 3 Assessment overview Question Submission status: Available points: — Total points: 8 /8 Auto-graded question [ Report an error in this question ] Previous question Next question Personal Notes No attached notes Notes can't be added or deleted because the assessment is closed.

hw3-2

Related Documents