There are n trading posts along a river numbered 1, 2, 3, ., n. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is impossible to paddle against the river, since it is too fast.) For each possible departure point i and each possible arrival point j (> i), the cost of a rental from i to j is known: it is C[i,j] > 0. However, it can happen that the cost of renting from i to j is higher than the total costs of a series of shorter rentals from i to j. In this case you can return the first canoe at some post k between i and j and continue your journey in a second (and, maybe, third, fourth.) canoe. There is no extra charge for changing canoes in this way. Give a O(n2) time dynamic programming algorithm to determine the minimum cost of a trip from trading post 1 to trading post n. ...

There are n trading posts along a river numbered 1, 2, 3, ., n. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is impossible to paddle against the river, since it is too fast.) For each possible departure point i and each possible arrival point j (> i), the cost of a rental from i to j is known: it is C[i,j] > 0. However, it can happen that the cost of renting from i to j is higher than the total costs of a series of shorter rentals from i to j. In this case you can return the first canoe at some post k between i and j and continue your journey in a second (and, maybe, third, fourth.) canoe. There is no extra charge for changing canoes in this way. Give a O(n2) time dynamic programming algorithm to determine the minimum cost of a trip from trading post 1 to trading post n. ...

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

IP Applications 4 Employment for Projects Formulate the following problem as integer linear programming problem. A company hires employees from a pool of 80 people. Employees are hired on a day to day basis. The pool contains 25 experienced persons. An experienced person can do twice as much work as an inexperienced person in the same time. Our company has n projects for which it has to recruit people. For the upcoming T days employees have to be divided over the projects. For project i (i = 1; :::; n) is w, the amount of required work on day t (t = 1; :::; T); an inexperienced employee can perform one unit of work per day. If an employee is hired on a certain day, he/she works on the same project all day. The cost for hiring a normal employee are c, per day and the cost for hiring an experienced employee are c, per day. Finally, for every day the minimal number of experienced employees that has to work on project i equals u,. The company wants to minimize the cost of hiring employees.…
You are the chief commander of US Army; you have been deployed in an ongoing war training of defusing the mine. Mines are placed on the ground which can be considered as a gird of size N*M. Each block (i, j) has a mine in it if and only if the summation of the block coordinates is divisible by 2. Your task is to move from the first row to the last row. The mines will not blow if the given rules are followed: • If you are on even row you can move to any cell that is in the neighborhood • If you are on odd row, you can only go the odd row that has mine on that and same with the unmined row. You have to develop a python program to calculate the number of ways to reach row number N starting from row number 1. Test Cases: 4 8 Output: 10
Consider the following case study: "Springfield University offers a number of courses. A course contains a number of units. Students enrol and elect a set of units every semester. Students are allowed to enrol in a maximum of 5 units in any given seme ster. They can only be enrolled into a single course at any given point in time. However, over a student's lifetime, they may undertake a number of different courses. Each unit has a set fee that is set at the start of the semester. This fee is to be paid up-front in full by the students once enrolled. Some units have pre-requisite unit requirements. Some units have co-requisite unit requirements. To be enrolled in some courses, you must have completed a certain course (e.g. to enrol into a Postgraduate course, you must have an Undergraduate degree)." Noun (bold)/verb (underline) analysis on the case study is marked for you to identify candidate classes, attributes, operations. Now, draw the domain model for the above case study.
A ski rental agency has n pairs of skis, where the height of the the ipair of skis is s; . There are n skiers who wish to rent skis, where the height of the ith skier is. h;. Ideally, each skier should obtain a pair of skis whose height matches her/his own height as closely as possible. We would like to assign skis to skiers so that the sum of the absolute differences of the heights of each skier and her/his skis is minimized. Design a greedy algorithm for the problem. Prove the correctness of your algorithm. (Hint: Start with two skis and two skiers. How would you match them? Continue to three skis and three skiers, and identify a strategy.)
A ski rental agency has n pairs of skis, where the height of the the ith pair of skis is si . There are n skiers who wish to rent skis, where the height of the ith skier is hi. Ideally, each skier should obtain a pair of skis whose height matches her/his own height as closely as possible. We would like to assign skis to skiers so that the sum of the absolute differences of the heights of each skier and her/his skis is minimized. Design a greedy algorithm for the problem. Prove the correctness of your algorithm. (Hint: Start with two skis and two skiers. How would you match them? Continue to three skis and three skiers, and identify a strategy.)
Problem 3: A day at the beach. A group of n people are lying on the beach. The beach is represented by the real line R and the location of the i-th person is some integer r; e Z. Your task is to prevent people from getting sunburned by covering them with umbrellas. Each umbrella corresponds to a closed interval I = [a, a + L] of length L e N, and the i-th person is covered by that umbrella if æ¡ € I. Design a greedy algorithm for covering all people with the minimum number of umbrellas. The input consists of the integers x1,..., En, and L. The output of your algorithm should be the positions of umbrellas. For example, if the input is r1 = 1, x2 = 3, r3 = 5, and L = 2, then an optimum solution is the set of two umbrellas placed at positions 2 and 5, covering intervals [1,3] and [4,6]. 1 2 3 4 5 6 Prove that your algorithm is correct and that it runs in time polynomial in n.
Suppose that the grading of x University courses is as follows:• Each student can get grades between 0 and 100.• If the student's grade is less than 40, the student is informed that the course failed (Unsuccessful).• If the student's grade is higher than 40,o The difference between the student's current grade and the number that is a multiple of 5 higher than the closest to his / her grade is less than 3.If it is lower, the student's grade is equal to the 5 fold higher than the closest one.o If the difference is 3 or more than 3, no change is made in the grade of the student.In this context, the updated grades of the students are calculated according to the entered student gradesWrite the Java code showing.Solve this question in c ++ language.ü Define the section to be calculated as Java object ("Question1").ü Question1; Take the note string as input.public Question1 (int [] input)ü Print out the updated notes as a series after the calculation is madeo public int [] gradingStudents…
Suppose that the grading of x University courses is as follows:• Each student can get grades between 0 and 100.• If the student's grade is less than 40, the student is informed that the course failed (Unsuccessful).• If the student's grade is higher than 40,o The difference between the student's current grade and the number that is a multiple of 5 higher than the closest to his / her grade is less than 3.If it is lower, the student's grade is equal to the 5 fold higher than the closest one.o If the difference is 3 or more than 3, no change is made in the grade of the student.In this context, the updated grades of the students are calculated according to the entered student gradesWrite the Java code showing.ü Define the section to be calculated as Java object ("Question1").ü Question1; Take the note string as input.public Question1 (int [] input)ü Print out the updated notes as a series after the calculation is madeo public int [] gradingStudents ()Code sample:public class Question1…
A school dance committee is to consist of 2 freshmen, 3 sophomores, 4 juniors, and 5 seniors. If 6 freshmen, 7 sophomores, 9 juniors, and 7 seniors are eligible to be on the committee, in how many ways can the committee be chosen? Your answer is:
Suppose you begin with one pair of newborn rabbits. At the end of the third month, and at the end of every month thereafter, they give birth to two pairs of rabbits. Each pair of offspring reproduces according to the same rule. Assume that none of the rabbits dic. Let fn be the number of pairs of rabbits at the end of month n, just after the new pairs have been born. We have f₁ = 1, f2 = 1, and f3 = 3. Which of the following is a recurrence relation for fn? Select one: O A. fn fn_1 + fn_3 O B. fn fn-1 +2fn_2 O C. fn fn-1 +2fn 3 O D. fn = fn-1 + fn_2 + fn_3
A group of n tourists must cross a wide and deep river with no bridge in sight. They notice two 13-year-old boys playing in a rowboat by the shore. The boat is so tiny, however, that it can only hold two boys or one tourist. How can the tourists get across the river and leave the boys in joint possession of the boat? How many times need the boat pass from shore to shore?
Ql: The Collatz conjecture function is defined for a positive integer m as follows. (COO1) g(m) = 3m+1 if m is odd = m/2 if m is even =1 if m=1 The repeated application of the Collatz conjecture function, as follows: g(n), g(g(n)), g(g(g(n))), ... e.g. If m=17, the sequence is 1. g(17) = 52 2. g(52) = 26 3. g(26) = 13 4. g(13) = 40 5. g(40) = 20 6. g(20) = 10 7. g(10) = 5 8. g(5) = 16 9. g(16) = 8 10. g(8) = 4 11. g(4) = 2 12. g(2) = 1 Thus if m=17, apply the function 12 times in order to reach m=1. Use Recursive Function.