Summer 2022 Exam

MA214

Algorithms and Data Structures

Question 1

The longest increasing subsequence problem is defined as follows. Input: A sequence x0 , x1 , . . . , xn-1 of integers.

Output: A longest increasing subsequence: that is, a sequence of the form. xi0  < xi1  < · · · < xiL-1 , where 0 ≤ i0  < i1  < · · · < iL-1  ≤ n — 1 and L is as large as possible.

The following Python code claims to output the length of a longest increasing subsequence for the given input list. You will prove its correctness in this question.

1       de f   L IS(lst):

2                  if   len (lst)==0:

3                          return   0 4

5                  L  =   [0   for   i  in   range (0,   len (lst))]

6                  L[0]   =   1

7                  for   i  in   range (1,  len (lst)):

8                          for   j  in   range (0, i):

9                                      if  lst[j]   <  lst[i]   and  L[j]   >  L[i]:

10                                                L[i]   =  L[j]

11                       L[i]   +=   1 12

13               return   max (L)

(a)     Show that the inner for loop in lines 8–10 satisfies the following loop invariant:

At the start of an iteration, L[i] = max{ L[k]  j 0<=k<j,  lst[k]<lst[i] }.

Use this to draw a conclusion about L after the execution of the last iteration of the inner for loop for a fixed value of i. Here, you can assume that max ; = 0.

(b)     Formulate a loop invariant for the outer for loop in lines 7–11 and use your loop invariant, to- gether with part (a), to draw a conclusion about L at the termination of the loop.

(c)     Argue that the length of a longest increasing subsequence of the input sequence is computed correctly by the code above. What is the worst-case running time of the algorithm for a list of length n?

Question 2

(a)     We define a Search Algorithm as an algorithm that, given an integer value y and a sorted list lst of integers as input, determines an index i such that lst[i]  equals y, if such an i exists.  A Comparison Search is a Search Algorithm that does not have direct access to lst, but can only send queries of the form ‘y<lst[i]?’ or ‘y==lst[i]?’ to an oracle which answers (truthfully) in constant time.

Hence, each Comparison Search on a list of length n can be represented by a binary tree such that each non-leaf of this tree represents a query of the form described, and each leaf represents a possible output of the algorithm: either of the form ‘y==lst[i] ’ or ‘y is not present in lst’.

Show that any Comparison Search has running time Ω(log n), where n is the length of the input list lst.

(b)     A binary search tree is organised in the form of a binary tree, where each node stores a value attribute (say, an integer) and two pointers, to the left and the right child of the current node. Both children of a leaf node are None.  In addition, a binary search tree satisfies the following property:  Let x be a node in a binary search tree.  If y is a node in the left subtree of x, then y.value≤x .value. If y is a node in the right subtree of x, theny .value>x .value. Below is a partial Python implementation of a binary search tree data structure.

1         c la s s   Node:

2                     def   _ _in it_ _ ( self , val):

3                                self . left  =  None

4                                self . right  =  None

5                                self . value  =  val 6

7        c la s s   BinarySearchTree:

8                     def   _ _in it_ _ ( self ):

9                                self . root=None 10

11                     de f   m in ( self ): 12                                #  Part   (i)

13

14                     def   find( self , x): 15                                #  Part   (ii)

(i)    Implement a Python function min() that returns the minimum value that is stored in the binary search tree.

(ii)   Implement a Python function find(x) that finds a node in the tree that contains the value x and returns a pointer to that node (if it exists). The function should return None if x does not appear in the tree.

(iii)  What is the best- and worst-case running time of your find(x) function for a binary search tree with n nodes?  Discuss briefly what property of a binary search tree needs to hold so that finding a value in it is as efficient as possible?

Question 3

In this question, you will implement a version of the Merge Sort algorithm for linked lists, where each node in the list contains an integer. Below are some parts of a Python implementation of a linked list, along with additional functions that you will need to implement.

1         c la s s   Node:

2                     def   _ _in it_ _ ( self , val , next ):

3                                self . value  =  val

4                                self . next   =  next 5

6          c la s s   LinkedList:

7                     def   _ _in it_ _ ( self ):

8                                self . head  =  None 9

10                     def   mid( self ): 11                     #  Part   (a)

12

13                     def  merge( self ,  left ,  right):

14                     #  Part   (b) 15

16                     def   mergesort( self ):

17                     #  Part   (c)

(a)     Implement a mid() function that returns a pointer to the middle node of the list.  For a linked list with n nodes, the middle node is defined as the kth node from the beginning of the linked list, fork =「n/21. So, for example, if a linked list has five nodes, mid() should return a pointer to the third node from the beginning of the list. You should not alter the representation of the linked list by adding new variables. Your algorithm should make only one scan of the list.

(b)     Implement a merge(left,right)  function that takes two pointers to the beginning of two sorted lists, merges them, and returns a pointer to the first element of the sorted list.  Your function should not create any list nodes; it should only alter the pointer structure while merging the two lists.

(c)     Implement a mergesort() function that sorts the current list using the strategy of Merge Sort from the lectures.

(d)     What is the running time of your Merge Sort implementation for a linked list of length n? Discuss briefly.

Question 4

(a)     Consider the flow network below with the indicated edge capacities.

Apply the Edmonds–Karp algorithm to find a maximum flow from sto t in this network, showing the flow on each edge and the value of the flow.  State the augmenting paths found by the algorithm, listing the nodes on each path and the value augmented along the path.  Show a minimum s–t cut in the network.

(b)    You are helping the medical consulting firm Doctors Without Weekends set up the worksched- ules of doctors in a large hospital during the vacation days throughout the year. They need to make sure that they have at least one doctor covering each vacation day.

There are k vacation periods (e.g., the week of Christmas, the Easter weekend, the bank holidays, etc.), each spanning several contiguous days.  Let Dj  be the set of days included in the jth vacation period; we will refer to the union of all these days, [jDj, as the set of all vacation days. There are n doctors at the hospital, and doctor i has a set Si of vacation days when he or she is available to work. (This may include certain days from a given vacation period but not others; so, for example, a doctor maybe able to work the Friday, Saturday, or Sunday of the Easter weekend, but not the Monday.)

(i)    Describe a polynomial-time algorithm that takes this information and determines whether it is possible to select a single doctor to work on each vacation day, subject to the constraint that, for a given parameter c, each doctor should be assigned to work at most c vacation days in total,and only days when he or she is available.

Your algorithm should either return an assignment of doctors satisfying these constraints or report (correctly) that no such assignment exists. Argue that your algorithm is correct. State the running time of your algorithm in terms of the number n of doctors and the total number d of vacation days.

(ii)   In addition to the previous constraints, a further requirement is imposed that, for each va- cation period j, each doctor should be assigned to work at most one of the days in the set Dj .  How would you modify your algorithm from part (i), to accommodate this additional constraint?