Consider a problem of finding a secret message hidden inside a long string. For example, you are looking for the message “swordfish” inside the meaningless string “pqsoiwoqcrldfweiqwsh”, and it turns out that it is there: pqsoiwoqcrldfweiqwsh. But, if you’re looking for the message “ball” in the string “lallaby”, it is not there.
Basically, you are given two strings and (in the first example, = “swordfish” and = “pqsoiwoqcrldfweiqwsh”), and you’re asked whether all the characters of can be found in the same order as they appear in , yes or no.
0 of 5 questions completed
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 5 questions answered correctly
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)
What do you think is a safe greedy choice for this problem?
In the problem “Largest number”, after you make the safe move to put the maximum digit first, you reduce it to a subproblem. Why is this problem simpler and smaller than the initial one?
You have a knapsack of capacity 10kg and three items. First item has weight 20kg and value 20, second item has weight 5kg and value 10. Third item has weight 4 kg and value 20. You want to maximize the total value of the fractions of items that fit into your knapsack. What is the safe move?
What is the next safe move in the previous problem?
What is the last move?