Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)

Q4 10 Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job j; each has a start time s; and finish time f;. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job late by y minutes, (there is no travel time between jobs). Otherwise, there is no allowed overlap. So I can have a job that goes 1pm-1:37pm and start another one that goes from 1:30pm to 2:30pm PART A Create and analyze code for a greedy algorithm that follows the greedy strategy of choosing the job that starts the latest compatible to currently selected jobs. (HINT you can order jobs in order of decreasing start time) Part B Prove that the greedy strategy of choosing the job that starts the latest is possible in an optimal solution. (Greedy choice property)

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter5: Control Structures Ii (repetition)

Section: Chapter Questions

Problem 20PE: When you borrow money to buy a house, a car, or for some other purpose, you repay the loan by making...

See similar textbooks

Similar questions

Bus Loading Problem. You are in charge of filling busses with passengers at a bus terminal. Each bus has space for ten (10) passengers. Four (4) of those spaces can hold only wheelchair passengers, and the other six (6) can hold only non-wheelchair passengers. Busses and both types of passengers arrive at random. As busses arrive, you are to fill them up with passengers. Once a bus is full (containing 6 non-wheelchair, and 4 wheelchair passengers), it is allowed to leave the terminal, along with its passengers. You are responsible only for loading the passengers on the bus and having the bus depart. You do not need to worry about what happens to the busses or passengers after they leave. Each bus process has available to it the functions ArriveAtTerminal(), OpenDoors(), CloseDoors(), and DepartTerminal(). Each passenger process has available to it the functions ArriveAtTerminal() and GetOnBus(). Executing GetOnBus() loads the passenger on the bus, and the function returns when the…
Subject -CSE
JAVA Based Prgm
Dinah Shore of Shore We Can Building is attempting to determine the cost forbuilding a custom lumber dog house. Each dog house starts at a cost of $1000. Eachhouse has a different possible size in square feet, which the user will enter. The sizein square feet must be in the range of 1200-2000 inclusive. However, since each doghouse is made from found wood, the actual size of the dog house varies depending onthe materials they have on hand. Once the size has been entered, create a randomnumber to determine the actual size the house will be. This size number should be inthe range of 800 to 2200. If the actual size of the dog house is over the squarefootage the user entered, they only get charged $3 per square foot. If the actual sizeis equal to or under the square footage entered they get charged $4 per squarefoot. The program should calculate the total cost for the dog house. The output forthis program must include the customer’s name, entered size, actual size and totalcost, in that…
Interest on a credit card’s unpaid balance is calculated using the average daily balance. Suppose that netBalance is the balance shown in the bill, payment is the payment made, d1 is the number of days in the billing cycle, and d2 is the number of days payment is made before billing cycle. Then, the average daily balance is: averageDailyBalance =netBalance x d1-payment x d2d1 If the interest rate per month is, say, 0.0152, then the interest on the unpaid balance is: Interest= averageDailyBalance * 0.0152 Write a program using c++ compiler that accepts as inputnetBalance, payment, d1,d2, and interest rate per month. The program outputs the interest. Format your output to two decimal places.
Q3: Interplanetary Spaceflight Milan Tusk is the richest person in the universe. After devoting decades of his life to further our space exploration technologies, he’s finally ready to retire. Being a space enthusiast, the first thing he wants to do is visit n planets p1, p2, …, pn, in this order. He’s currently on planet p0. Milan knows that the distance between planets pi and pi + 1 (for 0 ≤ i < n) is d[i]light years. His spaceship uses 1 tonne of fossil fuels per light year. He starts with a full tank and can fill up his tank at any of the n planets (but he must not run out in between two planets). There’s a huge cost to set up the spaceship for refuelling. Due to financial constraints (he’s not THAT rich), he can fill up his tank at most ktimes. In order to save money and make his spaceship lighter, Milan is looking for the smallest possible fuel tank that enables him to complete his space travel and reach planet pn. What is the smallest tank capacity that enables him to do so?…
There are four people who want to cross a rickety bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person's pace. Write the specification of an algorithm that solves the problem.
Scenario As you surely know, due to some astronomical reasons, years may be leap or common. The former are 366 days long, while the latter are 365 days long. Since the introduction of the Gregorian calendar (in 1582), the following rule is used to determine the kind of year: if the year number isn't divisible by four, it's a common year, otherwise, if the year number isn't divisible by 100, it's a leap year. otherwise, if the year number isn't divisible by 400, it's a common year. otherwise, it's a leap year. none of the above year int(input("enter the year")) if (year%4 1-0) and (year%400 -0) or (year % 1000): print (year is common year") else: print(year, is leap year") year= int(input ("enter the year")) if (years !-0) or (year480 1-0) and (year % 1001-0): print(year is common year") else: print(year, "is leap year") D year= int(input("enter the year"))
One hundred tickets, numbered 1, 2, 3, . . . , 100, are sold to 100 different people for a drawing.Four different prizes are awarded, including a grand prize. How many ways are there to awardthe prizes if:a) the person holding ticket 35 wins the grand prize?b) the person holding ticket 64 wins one of the prizes?c) the person holding ticket 18 does not win a prize?d) the people holding tickets 30 and 50 both win prizes?
The game of Pig is a simple two-player dice game in which the first player to reach 100 or more points wins. Players take turns. On each turn, a player rolls a single six-sided die: • If the player rolls a 1, then the player gets no new points and it becomes the other player's turn. • If the player rolls 2 through 6, then he or she can either o ROLL AGAIN or o HOLD: At this point, the sum of all rolls for that turn is added to the player's overall total score and it becomes the other player's turn. Write a Java program that plays the game of Pig, where one player is a human and the other is the computer. When it is the human's turn, the program should show the score of both players and the previous roll. Allow the human to input whether to roll again or hold. The computer program should play according to the following rules: Keep rolling when it is the computer's turn until it has accumulated 20 or more points, then hold. • If the computer wins or rolls a 1, then the turn ends…
When you borrow money to buy a house, a car, or for some other purpose, you repay the loan by making periodic payments over a certain period of time. Of course, the lending company will charge interest on the loan. Every periodic payment consists of the interest on the loan and the payment toward the principal amount. To be specific, suppose that you borrow $1,000 at an interest rate of 7.2% per year and the payments are monthly. Suppose that your monthly payment is $25. Now, the interest is 7.2% per year and the payments are monthly, so the interest rate per month is 7.2/12 = 0.6%. The first months interest on $1,000 is 1000 0.006 = 6. Because the payment is $25 and the interest for the first month is $6, the payment toward the principal amount is 25 6 = 19. This means after making the first payment, the loan amount is 1,000 19 = 981. For the second payment, the interest is calculated on $981. So the interest for the second month is 981 0.006 = 5.886, that is, approximately $5.89. This implies that the payment toward the principal is 25 5.89 = 19.11 and the remaining balance after the second payment is 981 19.11 = 961.89. This process is repeated until the loan is paid. Write a program that accepts as input the loan amount, the interest rate per year, and the monthly payment. (Enter the interest rate as a percentage. For example, if the interest rate is 7.2% per year, then enter 7.2.) The program then outputs the number of months it would take to repay the loan. (Note that if the monthly payment is less than the first months interest, then after each payment, the loan amount will increase. In this case, the program must warn the borrower that the monthly payment is too low, and with this monthly payment, the loan amount could not be repaid.)
A year in the modern Gregorian Calendar consists of 365 days. In reality, the earth takes longer to rotate around the sun. To account for the difference in time, every 4 years, a leap year takes place. A leap year is when a year has 366 days: An extra day, February 29th. The requirements for a given year to be a leap year are: 1) The year must be divisible by 4 2) If the year is a century year (1700, 1800, etc.), the year must be evenly divisible by 400 Some example leap years are 1600, 1712, and 2016. Write a program that takes in a year and determines whether that year is a leap year. Ex: If the input is: 1712 the output is: 1712 - leap year Ex: If the input is: 1913 the output is: 1913 - not a leap year