Question

7. Given a set of n activities with start time and finish time F; of an i activity. Find the maximum size set of mutually compatible activities. Implement following string matching algorithms and analyze time complexities: 8. a) Naïve method b) Rabin karp Algorithm c) Finite state Automaton algorithm 9. A hash table is a data structure used to implement an associative array, al structure that can map keys to values. Implement Hashing using Linear and Quadratic Probing.

Answer 1

Answering the First Question i.e. 7.

Solution :

Given a set of n activities with their start time Si and Finish time Fi for the i^th activity, in order to find maximise set for mutually compatible activities, following steps need to be followed: -

Step 1: Sort all the activities given in the activity set based on their finishing time in the ascending time.

Step 2: Pick the first Activity in the activity set after sorting.

Step 3: Note done its finish time as F and execute the activity that has been taken until its finite time.

Step 4: Pick the next activity in the sequence if the start time of the activity say S>=F.

Step 5: Repeat the Step 3 and Step 4 until no activities left in activity set.