Final Practice problems
To prepare for the final first of all study carefully all examples which we did in class, and then attempt to solve as many problems below as possible.
(A) Dynamic Programming
1. Given a sequence of n real numbers A1 . . . An, determine in linear time a contiguous
subsequence Ai . . . Aj for which the sum of elements in the subsequence is maximised.
2. You are traveling by a canoe down a river and there are n trading posts along the way. Before starting your journey, you are given for each 1 ≤ i < j ≤ n the fee F (i, j) for renting a canoe from post i to post j. These fees are arbitrary. For example it is possible that F (1, 3) = 10 and F (1, 4) = 5. You begin at trading post 1 and must end at trading post n (using rented canoes). Your goal is to design an efficient algorithms which produces the sequence of trading posts where you change your canoe which minimises the total rental cost.
3. You are given a set of n types of rectangular boxes, where the ith box has height hi, width wi and depth di. You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
4. Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a1 . . . an and n cities on the northern bank with x-coordinates b1 . . . bn. You want to connect as many north-south pairs of cities as possible, with bridges such that no two bridges cross. When connecting cities, you are only allowed to connect the the ith city on the northern bank to the ith city on the southern bank.
5. You are given a boolean expression consisting of a string of the symbols true and false and with exactly one operation and, or, xor between any two consecutive truth values. Count the number of ways to place brackets in the expression such that it will evaluate to true. For example, there is only 1 way to place parentheses in the expression true and false xor true such that it evaluates to true.
6. Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.
程序代写 CS代考 加QQ: 749389476
7. You have n1 items of size s1, n2 items of size s2, and n3 items of size s3. You would like to pack all of these items into bins, each of capacity C, using as few bins as possible.
8. Find the number of partitions of n, i.e. the number of sets of integers {p1, p2, . . . , pk} such that such that p1 + p2 + . . . , pk = n. (Hint: try relaxation with respect to the number of elements in such a sum and the size of the largest number in such a sum.)
9. You are given a sequence of numbers with operations +, −, × in between, for example 1+2−3×6−1−2×3−5×7+2−8×9
Your task is to place brackets in a way that the resulting expression has the largest possible value.
10. You have an amount of money M and you are in a candy store. There are n kinds of candies and for each candy you know how much pleasure you get by eating it, which is a number between 1 and 100, as well as the price of each candy. Your task is to chose which candies you are going to buy to maximise the total pleasure you will get by gobbling them all.
11. You have invented a new version of hopscotch! On the ground you have drawn a line of n + 1 evenly spaced hopscotch squares indexed from 0 to n, and have written an integer (positive or negative) in each square. These squares can be represented by an array A[0..n] where A[i] is the number written in the square with index i.
You start in square 0 and will hop until you reach square n. Each time, you will jump from the current square to a square with a strictly greater index. Specifically, if you are at square with index i then you will jump to a square with index i + k for some k > 0. Since hopping is tiring, the length of each jump cannot exceed the length of the previous jump. Your first jump may be of any length.
Your score from such a jump sequence is the sum of the scores in all squares you have hopped onto. What is the maximum score you can earn?
(a) Design an O(n3) time algorithm that determines the maximum score you can earn.
(b) If necessary, explain how you might improve your algorithm for part (a) to run in O(n2) time.
12. Some people think that the bigger an elephant is, the smarter it is. To disprove this you want to analyze a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights are increasing but their IQs are decreasing. Design an algorithm which given the weights and IQs of n elephants, will find a longest sequence of elephants such that their weights are increasing but IQs are decreasing.
13. You have to cut a wood stick into several pieces at the marks on the stick. The most affordable company, Analog Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example, consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then at7. Thiswouldleadtoapriceof10+4+6=20,whichisbetterforus. Yourboss demands that you design an algorithm to find the minimum possible cutting cost for any given stick.
14. You are given an n×n chessboard with an integer in each of its n2 squares. You start from the top left corner of the board; at each move you can go either to the square immediately below or to the square immediately to the right of the square you are at the moment; you can never move diagonally. The goal is to reach the right bottom corner so that the sum of integers at all squares visited is minimal.
(a) Describe an algorithm which always correctly finds a minimal sum path and runs in time O(n2).
(b) Describe an algorithm which computes the number of such minimal paths.
15. A palindrome is a sequence of at least three letters which reads equally from left to right and from right to left.
(a) Given a sequence of letters S, find efficiently its longest subsequence (not nec- essarily contiguous) which is a palindrome. Thus, we are looking for a longest palindrome which can be obtained by crossing out some of the letters of the initial sequence without permuting the remaining letters.
(b) Find the total number of occurrences of all subsequences of S which are palin- dromes of any length ≥ 3.
16. There are N lily pads in a row. A frog starts on the leftmost lily pad and wishes to get to the rightmost one. The frog can only jump to the right. There are two kinds of jump the frog can make:
• The frog can jump 3 lily pads to the right (skipping over two of them) • The frog can jump 5 lily pads to the right (skipping over four of them)
Each lily pad has some number of flies on it. Design an algorithm that maximises the total number of flies on lily pads the frog lands on getting to the rightmost lily pad.
浙大学霸代写 加微信 cstutorcs
17. You have been handed responsibility for a business in Texas for the next N days. At the beginning of each day, you may hire an illegal worker, keep the number of illegal workers the same or fire an illegal worker. At the end of each day, there will be an inspection. The inspector on the ith day will check that you have between li and ri illegal workers (inclusive). If you do not, you will fail the inspection. Design an algorithm that determines the fewest number of inspections you will fail if you hire and fire illegal employees optimally.
18. Devise a dynamic programming algorithm that counts the number of non-decreasing sequences of integers of length N, such that the numbers are between 0 and M inclu- sive.
19. You are given a rooted tree. Each edge of the tree has a cost for removing it. Devise an algorithm to compute the minimum total cost of removing edges to disconnect the root from all the leaves of the tree.
20. You are given an ordered sequence of n cities, and the distances between every pair of cities. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimised.
21. A company is organising a party for its employees. The organisers of the party want it to be a fun party, and so have assigned a fun rating to every employee. The employees are organised into a strict hierarchy, i.e. a tree rooted at the president. There is one restriction, though, on the guest list to the party: an employee and their immediate supervisor (parent in the tree) cannot both attend the party (because that would be no fun at all). Give an algorithm that makes a guest list for the party that maximises the sum of the fun ratings of the guests.
22. ForbitstringsX=x1…xm ,Y =y1…yn andZ=z1…zm+n wesaythatZisan interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y. For example if X = 101 and Y = 01 then x1x2y1x3y2 = 10011 is an interleaving of X and Y, whereas 11010 is not. Give an efficient algorithm to determine if Z is an interleaving of X and Y.
(B) Max Flow
23. You are running a dating agency and have m guys and f girls as customers. Each guy and each girl have reviewed all profiles of the candidates of opposite sex and have sent you their corresponding lists of people whose profiles they liked. Your task is to organise a largest possible number of first dates so that everyone meets at most one
person of opposite sex and so that both parties liked each others profile (i.e., have included the other party on their list of people whose profile they liked).
24. Assume that you are the administrator of a network of computers; each computer is connected by unidirectional fiberoptic cables to a few other computers on the same network (so the network can be modeled by a directed graph). You noticed that computers P1, P2, …Pn are mounting an attack on computers Q1, Q2, …, Qm. The total number of computers on the network is N > m + n. Since it is a real emergency, you must disconnect some of the optical cables of the network so that none of computers P1, P2, …Pn can send packets to any of Q1, Q2, …, Qm. Since you must send crews to disconnect some of the fiberoptic cables, for each cable cij for traffic from a computer Xi to a computer Xj there is an associated cost cij for disconnecting it. Your task is to design an algorithm for determining which cables to disconnect to isolate computers Q1, Q2, …, Qm from all of the computers P1, …, Pn so that the total cost incurred is minimal.
25. You work for a new private university which wants to keep the sizes of classes small. Each class is assigned its maximal capacity – the largest number of students which can enrol in it. Students pay the same tuition fee for each class they get enrolled in. Students can apply to be enrolled in as many classes as they wish, but each of them will eventually be enrolled to at most 5 classes at any given semester. You are given the wish lists of all students, containing for each student the list of all classes they would like to enrol this particular semester and you have to chose from the classes they have put on their wish lists in which classes you will enrol them, without exceeding the maximal enrollment of any of the classes and without enrolling any student into more than 5 classes. Your goal is, surprisingly, to maximise the income from the tuition fees for your university. Design an efficient algorithm for such a task.
26. Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of books he wishes to borrow. You have to assign books to students, so that a maximal number of volumes is checked out.
27. The emergency services are responding to a major earthquake that has hit a wide region, and left n people injured who need to be sent to a hospital. Let P be the set of n people and H be the set of k hospitals. Several hospitals are available to treat these people, but there are some constraints:
(a) Each injured person needs to be sent to a hospital no further than one hour drive away. Let Hp be the set of hospitals that are within range for person p.
(b) Each hospital h has a capacity ch, the maximum number of people that the hospital can receive.
Design an efficient algorithm that determines whether it is possible to assign each person to a hospital in a way that satisfies these constraints, and returns such an
Programming Help, Add QQ: 749389476
assignment if so.
(C) String matching
28. You are given a string. Find the shortest palindrome that can be obtained by ex- tending such a string with additional characters on the right (after the right end of the string).
(D) Linear programming
29. An investor has decided to invest a total of $50,000 among three investment op- portunities: savings certificate, municipal bonds and stocks. The annual return on each investment is estimated to be 7%, 9% and 14% respectively. She would like to maximize her yearly return (based on the estimates for the returns) while investing a minimum of $10,000 in bonds. Also the investment in stocks should not exceed the combined total investment in bonds and savings certificates. And finally, she should invest between $5,000 and %15,000 in savings certificates. Formulate a linear program to optimally solve this problem.