Problem 1 The spread of third wave of COVID-19 in Pakistan has resulted in closure of academic Institutes. The management of FAST Lahore decided to save your academic year by conducting online sessions (video lectures). There are total n videos that need to be streamed one after the other. Each video vi consists of bi bits that needs to be sent at a constant rate over a period of ti seconds. There is only one connection allowed so two videos can’t be sent at a time. This means scheduling of videos is required (an order in which to send these videos). Whichever order is chosen, there cannot be any delays between the end of one video and the start of the next. The connection does not want its user taking up too much bandwidth, so it imposes the following constraint, using a fixed parameter r: For each natural number t > 0, the total number of bits you send over the time interval from 0 to t cannot exceed rt. A schedule is considered valid if it satisfies the constraint imposed by the connection. You are a computer science expert and management of FAST need your services. Given a set of n video streams specified by its number of bits bi and its time duration ti, they need to determine whether there exists a valid schedule that satisfies connection parameter r. For example you have 3 videos with (b1,t1)=(2000,1), (b2,t2)=(6000,2) and (b3,t3)=(2000,1) also r=5000. The schedule that runs videos in order 1, 2, 3, is valid because at time t=1 the first stream is sent and 2000 < 50001 at time t=2 2000+3000(half of second video)<5000*2 similar calculation can be done to check the constraint for t=3 and t=4. a. Design an efficient algorithm that takes a set of n streams each specified by bi and ti along with r and determines whether a valid schedule exists or not. b. Analyze the running time of your algorithm as a function of n. c. Prove that your algorithm works (Give informal argument). Problem 2 Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution. Problem 3 Suppose that we have a set of activities to schedule among a large number of lecture halls, where any activity can take place in any lecture hall. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall. Problem 4 Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and five other people whom they don't know. Give an efficient algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. Give the running time in terms of n.
gyponaxu/Design-and-Analysis-of-Algorithms--Spring-2021-Assignment-4
Problem 1 The spread of third wave of COVID-19 in Pakistan has resulted in closure of academic Institutes. The management of FAST Lahore decided to save your academic year by conducting online sessions (video lectures). There are total n videos that need to be streamed one after the other. Each video vi consists of bi bits that needs to be sent at a constant rate over a period of ti seconds. There is only one connection allowed so two videos can’t be sent at a time. This means scheduling of videos is required (an order in which to send these videos). Whichever order is chosen, there cannot be any delays between the end of one video and the start of the next. The connection does not want its user taking up too much bandwidth, so it imposes the following constraint, using a fixed parameter r: For each natural number t > 0, the total number of bits you send over the time interval from 0 to t cannot exceed r*t. A schedule is considered valid if it satisfies the constraint imposed by the connection. You are a computer science expert and management of FAST need your services. Given a set of n video streams specified by its number of bits bi and its time duration ti, they need to determine whether there exists a valid schedule that satisfies connection parameter r. For example you have 3 videos with (b1,t1)=(2000,1), (b2,t2)=(6000,2) and (b3,t3)=(2000,1) also r=5000. The schedule that runs videos in order 1, 2, 3, is valid because at time t=1 the first stream is sent and 2000 < 5000*1 at time t=2 2000+3000(half of second video)<5000*2 similar calculation can be done to check the constraint for t=3 and t=4. a. Design an efficient algorithm that takes a set of n streams each specified by bi and ti along with r and determines whether a valid schedule exists or not. b. Analyze the running time of your algorithm as a function of n. c. Prove that your algorithm works (Give informal argument). Problem 2 Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution. Problem 3 Suppose that we have a set of activities to schedule among a large number of lecture halls, where any activity can take place in any lecture hall. We wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy algorithm to determine which activity should use which lecture hall. Problem 4 Alice wants to throw a party and is deciding whom to call. She has n people to choose from, and she has made up a list of which pairs of these people know each other. She wants to pick as many people as possible, subject to two constraints: at the party, each person should have at least five other people whom they know and five other people whom they don't know. Give an efficient algorithm that takes as input the list of n people and the list of pairs who know each other and outputs the best choice of party invitees. Give the running time in terms of n.