1. Implement the Boyer-Moore algorithm using any programming language you prefer. Your program should ask the user to enter a text and a pattern, then output the following: (a) bad-symbol table (b) good suffix table (c) the searching result (whether the pattern is in the text or not) Please make sure that the good suffix table is generated correctly. Use the following examples to test your program before submitting your assignment.
Examples:
Good suffix table for the pattern BAOBAB
k = 1 d2 = 2; k = 2, d2 = 5; k = 3 d2 = 5; k = 4 d2 = 5; k = 5 d2 = 5
Good suffix table for the pattern AACCAC
k = 1 d2 = 2; k = 2, d2 = 3; k = 3 d2 = 6; k = 4 d2 = 6; k = 5 d2 = 6
Good suffix table for the pattern AACCAA
k = 1 d2 = 1; k = 2, d2 = 4; k = 3 d2 = 4; k = 4 d2 = 4; k = 5 d2 = 4
Good suffix table for the pattern 10000
k = 1 d2 = 3; k = 2, d2 = 2; k = 3 d2 = 1; k = 4 d2 = 5
Good suffix table for the pattern 01010
k = 1 d2 = 4; k = 2, d2 = 4; k = 3 d2 = 2; k = 4 d2 = 2
2. Design a greedy algorithm to solve the activity selection problem. Suppose there are a set of activities: a1, a2, ... an that wish to use a lecture hall. Each activity ai has a start time siand a finish time fi. A lecture hall can be used by only one activity at a time. Two activities can be scheduled in the same lecture hall if they are non-conflicting (fi<= sj or fj<= si) Your algorithm should find out the minimum number of lecture halls needed to hold all the activities. Write a program to implement your algorithm. For example: if the activities you need to schedule have the following start times and finish times,
4 7
6 9
7 8
1 3
1 4
2 5
3 7
then the output of your program is "the minimum number of lecture halls required is 3". Also indicate which activity will be scheduled in which lecture hall.
3. Write a program to solve the Longest Common Subsequence problem using dynamic programming as discussed in class. For example, if the input is X = ABCBDAB and Y = BDCABA, then the output of your program should be BCBA.
4. Suppose you need to create a work plan, and each week you have to choose a job to undertake. The set of possible jobs is divided into low-stress and high-stress jobs.
If you select a low-stress job in week i, then you get a revenue of li dollars; if you select a high-stress job, you get a revenue of hi dollars. The catch, however, is that in order for you to take on a high-stress job in week i, it's required that you rest in weeki - 1 because you need a full week of prep time to get ready for the stress level (It's okay to choose a high-stress job in week 1.) On the other hand, you can take a low-stress job in weeki even if you have done a job (of either type) in week i-1.
So, given a sequence of n weeks, a plan is speci?ed by a choice of "low-stress", "high-stress" or "none" for each of the n weeks, with the constraint that if "high-stress" is chosen for week i> 1, then "none" must be chosen for week i - 1. The value of the plan is determined in the natural way; for each i, you add li to the value if you choose "low-stress" in week i, and you add hi to the value if you choose "high-stress" in week i. (You add 0 if you choose "none" in week i.)
Example: Suppose n=4, and the values of li and hiare given by the following table. Then the plan of the maximum value would be to choose "none" in week 1, a high stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0+50+10+10=70.
i Week 1 Week 2 Week 3 Week 4
l 10 1 10 10
h 5 50 5 1
Design a dynamic programming algorithm to find the value of the optimal plan. Implement your algorithm using any programming language you prefer. Describe the recurrence relation used by your algorithm at the top of your program or in a separate file.