[Solved] COMP9101 Homework3

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 uppercase string of letters. Each letter is one of S, N, A, K or E. Your extensive research shows that a snakes 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 snakes 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 snakes DNA, can you work out the maximum venom level this snake could have? Your algorithm should run in time O(nlogn)

Hint: Combine binary search with greedy.

2. Paper. Scissors. The rules are simple. The game is contested by two people over N rounds. During each round, you and your opponent simultaneously throw either Rock, Paper or Scissors. Rock beats Scissors, Scissors beats Paper, and Paper beats Rock. If your throw beats your opponents, 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 R_a rounds, throw Paper in the next P_a rounds, then finally throw Scissors in the last S_a rounds, where R_a + P_a + S_a = N. You have

1

to throw Rock in R_b rounds, Paper in P_b rounds, and Scissors in S_b rounds, where R_b + P_b + S_b = 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?

3. You are given a time schedule of arrivals a_i and departures d_i 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.
4. You are given a set of n jobs where each job i has a deadline d_i 1 and profit p_i > 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(n²).
5. You have to produce and deliver N You need to deliver W_i kilograms of chemical C_i. 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