CMSC 351 - Homework #8
Due by 11:59pm on Tuesday, May 8th

Write clearly. Write your name and section clearly on the top of the first page. Scan/photograph clearly. If we can't read it, we will grade it as incorrect.

After you finish your answers, scan or carefully photograph your answer sheets and create a single PDF with those images to upload to the ELMS entry.

You cannot e-mail them to me.

We may only grade some subset of these, but you are expected to do them all.

Use the techniques from class as you solve these homework problems.


Question #1 
       Run KMP on the following patterm and block of text.
            Pattern: ABCDABD
            BlockOfText: ABCABCDABABCDABCDABDE


       

Question #2 
       Please provide your answer to each with a drawing showing the set
       of requests with their times in a timeline-like way so the graders
       can easily visualize them (and it's a good idea for figuring out 
       the answer too).  

       For example, if you had three events, rather than listing them as:
            1:10-2:10
            2:10-3:10
            2:25-3:25
       you would show them as
            1:10 ------- 2:10, 2:10 ------- 3:10
                                     2:25 ------- 3:25



   (a) Given the following (incorrect) idea for a greedy algorithm for 
       our problem of scheduling the most activities in a room:

        - sort by length of time interval	
        - pick the request with the shortest time interval that 
          doesn't conflict with already-scheduled requests

       Assume that a request will start and finish either on :10, :25, :40,
         or :55.  Create a set of requests for which the above algorithm 
         will NOT give a correct solution.  Provide that list to us sorted 
         by start time, the solution the above algorithm generates, and
         a BETTER solution given the requests.



   (b) Given the following (incorrect) idea for a greedy algorithm for 
       our problem of scheduling the most activities in a room:

	- sort by number of conflicts with other requests
        - pick the request with the fewest conflicts and doesn't conflict 
          with already-scheduled requests

       Assume that a request will start and finish either on :10, :25, :40,
         or :55.  Create a set of requests for which the above algorithm 
         will NOT give a correct solution.  Provide that list to us sorted 
         by start time, the solution the above algorithm generates, and
         a BETTER solution given the requests.

                Hint #1

                Hint #2
			
                Hint #3
		





Question #3 
   You will color the following graph in several ways:
          V = {A,B,C,D,F,G,H,I,J,K}
          E = {(A,B),(A,D),(B,C),(B,D),(B,K),(C,K),(C,F),(D,K),(K,F), 
                  (A,H),(B,I),(I,J),(K,H)}

   Please user color numbers (1, 2, 3, ...) to make grading easier.

   (a) Using the first greedy algorithm in slide set #19 (Page 3).


   (b) Using the second greedy algorithm in slide set #19 (Page 4).
 	NOTE: This is the algorithm where we sort by degree first.

   
   (c) See whether you can color the graph using fewer colors than
       used by either of the two above algorithms by doing the colors 
       "manually" rather than via either algorithm.





Question #4 
    Use the 2-CNF SAT-solving algorithm to determine whether each of
    the following can be satisfied:

           (~X∨Y)∧(~Y∨Z)∧(~Z∨X)


           (~A∨~B)∧(~A∨~C)∧(A∨~D)∧(~B∨~C)∧(B∨~D)∧(B∨D)

    You should show the full trace of the algorithm, not just give a 
    yes/no answer.