Assignment 3 Hints
You have five problems, marked out of a total of 100 marks; each problem is worth 20 points.
Due on Friday July 17 at 9AM SHARP. Please be careful to upload correct files, they cannot be replaced.
NOTE: Your solutions must be typed, machine readable .pdf files. All sub- missions will be checked for plagiarism!
1. After the success of your latest research project in mythical DNA, you have gained the attention of a most diabolical creature: Medusa. Medusa has snakes instead of hair. Each of her snakes’ DNA is represented by an upper- case string of letters. Each letter is one of S, N, A, K or E. Your extensive research shows that a snake’s venom level depends on its DNA. A snake has venom level x if its DNA:
• has exactly 5x letters
• begins with x copies of the letter S • then has x copies of the letter N
• then has x copies of the letter A
• then has x copies of the letter K
• ends with x copies of the letter E.
For example, a snake with venom level 1 has DNA SNAKE, while a snake that has venom level 3 has DNA SSSNNNAAAKKKEEE. If a snake’s DNA does not fit the format described above, it has a venom level of 0. Medusa would like your help making her snakes venomous, by deleting zero or more letters from their DNA. Given a snake’s DNA, can you work out the maxi- mum venom level this snake could have? Your algorithm should run in time O(n log n)
Hint: Count the numbers ns, nn, na, nk, ne of occurrences of each letter S, N, A, K, E in the original sequence and let M = min{ns, nn, na, nk, ne}. Clearly, the largest possible venom level L satisfies L ≤ N. Use greedy strategy to see if
it is possible to delete some of the letters so that the remaining sequence is
SS . . . S NN . . . N AA . . . A KK . . . K EE . . . E
MMMMM
i.e.,ifL=M. Ifyousucceed,youaredone. Ifnot,trytoseeifL=M/2 works; if it does, see if L = 3/4M also works, etc.
1
2. Rock. Paper. Scissors. The rules are simple. The game is contested by two people over N rounds. During each round, you and your opponent simulta- neously throw either Rock, Paper or Scissors. Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. If your throw beats your opponent’s, you gain one point. Conversely, if their throw beats yours, you lose one point. Your opponent is very predictable. You know that they will throw Rock in the first Ra rounds, throw Paper in the next Pa rounds, then finally throw Scissors in the last Sa rounds, where Ra + Pa + Sa = N. You have to throw Rock in Rb rounds, Paper in Pb rounds, and Scissors in Sb rounds, where Rb + Pb + Sb = N. However, as you are an experienced player, you may throw these in any order you like. At the beginning of the game, you start with 0 points. How should you play to maximise the number of points you can finish with?
Hint: This is a straightforward one: reserve as many Papers as possible to counter as many as possible throws of Rock of your opponent; reserve as many as possible Scissors to counter as many as possible throws of Paper by your opponent and similarly reserve as many as possible Rocks to beat as many as possible Scissors of your opponent. The leftover throws of Rock (if you have any left) you distribute over as many as possible throws of Rock of your oponent and similarly for the rest.
3. You are given a time schedule of arrivals ai and departures di of n trains, so 1 ≤ i ≤ n, during each 24 hour period (note: a train can arrive before the midnight and leave after midnight; each train arrives and departs at the same time every day). You need to find the minimum number of platforms so that each train can stay at a platform without interfering with other arrivals and departures.
Hint: First go through the timetable schedule of arrivals and departures and count how many trains arrive before midnight and depart after midnight. This number is the initial value of your counter. Then make a single list of the departures and arrival times (labeled as such) sort such a list in an increasing sequence of times and go through such a list adjusting your counter accordingly. Such a counter can help to solve the problem.
4.Youaregivenasetofnjobswhereeachjobihasadeadlinedi ≥1and profit pi > 0. Only one job can be scheduled at a time. Each job takes 1 unit of time to complete. We earn the profit if and only if the job is completed by its deadline. The task is to find the subset of jobs that maximises profit. Your algorithm should run in time O(n2).
Hint: The principle used to solve this problem is important in logistics and is called “just in time”. Order the jobs in decreasing order of profit. Execute
2
each job at a time that minimally affects other jobs, namely as late as possible but before its deadline, if this is possible.
5. You have to produce and deliver N chemicals. You need to deliver Wi kilo- grams of chemical Ci. Production of each chemical takes one day, and your factory can produce only one chemical at any time. However, all of the chemicals evaporate, and at the end of each day you loose p percent of the amount you had at the end of the previous day, so you need to produce more than what you need to deliver. Schedule the production of the chemicals so that the total extra weight of all chemicals needed to produce to compensate for the evaporation loss is as small as possible.
Hint: First determine how much of a chemical is left after k many days and then compute how much of it has ben lost, and then apply greedy. More substance is produced early – more will evaporate.
3