operating system and algorithm

Prof. Pitts CS315/557A: Algorithms Spring 2018

Assignment 3

Answer the questions below. You may submit scanned or photo'd copies of handwritten submissions, but use the PDF format. You may also submit your answers using Microsoft Word or other electronic word processors, but convert to

PDF format before submission.

1. For the recursive algorithm below, do the first four steps: ▪ Indicate the parameter describing the size of the problem ▪ Indicate the basic operation ▪ Indicate whether the number of times the basic operation is executed depends on something other than theproblem

size. ▪ Set up a recurrence relation with approximate initial conditions that describes the number of times the basic

operation is executed. ▪ Solve the recurrence or obtain an order of growth

Consider the following algorithm RecAllEvens(A[1..n], l) :

// A[1..n] is an array of integer // l is an integer indexing A; initially called with l == 1 if l == n

return A[l] mod 2 == 1 if A[l] mod 2 == 1

return false return RecAllEvens(A[1..n], l+1)

2. You have the following list of integers: 50, 40, 30, 1, 2, 3. Show the operations of selection sort and bubble sort on

these lists. The information you need to show is described below

Selection Sort Bubble Sort • Outer loop index i • Outer loop index i • Outer loop changer to variable min • • Inner loop index j • Inner loop index j • Inner loop comparison result • Inner loop comparison result • Inner loop changer to variable min • Inner loop swap of A[j+1] and A[j] • Outer loop swap of A[i] and A[min] •

Count the total number of comparisons done by each algorithm and the total number of swaps. Do these total conform to the asymptotic bounds we established in class for the algorithms? What is the smallest number of

element swaps that are required to put the list in sorted order (you can swap any two elements, but only one swap at a time)? How does this compare with the number of swaps actually performed by the two algorithms?

3. Consider the text T[0 .. 8] = a,d,v,i,s,i,n,g and a pattern P[0 .. 1] = i, t. Show the operations of the brute force pattern matching algorithm. How many comparisons are performed by this algorithm and how does this compare

to the asymptotic bound we discussed in class. 4. A school has an electron microscope in its biology department. There are n faculty members who want to use the

microscope during particular times of the day: faculty member i wants to use the microscope from time si to time fi (that is, si is the start time and fi is the finish time for the faculty member's request). The requests of a set of

faculty members is compatible if their request intervals do not overlap. The biology department wants to schedule as many compatible requests for the microscope as possible. Give a brute force algorithm that finds the maximum

number of compatible requests. What is the asymptotic order for your algorithm? (See section 3.4 of your textbook for guidance with this problem.)

1/2

Prof. Pitts CS315/557A: Algorithms Spring 2018

5. Consider the graph shown below.

For each vertex, show the order in which the vertex is encountered by the DFS and BFS algorithms. Assume that

when checking neighbors of a vertex, the neighbors are looked at in alphabetic order. How many times do each of the algorithms check whether a vertex is marked with a zero (include both successful and successful checks)?

How does this compare to the total number of vertices?

2/2