Problem 2 (20 points) Each day Sullivan goes to break the world record for scaring and Mikes job is to help

him do that. He loves his job, but he hates handing out daily reports to his boss Rose. There is a

cabinet for each employee to keep their files in chronological order with yesterdays file in front

and the oldest file in the back.

Mike knows that he has missed some days and Rose will soon find out about it. Rose plans to take

some number of the most recent files from anyones cabinet and check whether any day is missing.

Mike and Sulli know about this so during lunch break they try to break into her office and add a

fake file to Mikes cabinet.

They want to insert this file to the place of the most recent day that Mike has forgotten to hand in

his daily report. Afterwards, they fill out the date on the sheet and quickly leave!

They could complete this task by simply flipping through the files until they find the first missing

day, but this would require looking at () files in the worst case. Help them design an algorithm

which looks at only (log) files as they are in a rush!

Your algorithm can access the file deck as follows: for any given , you can find, in unit time, the

date of the th most recent file directly, without looking at any other files (where 1 ). You

can also calculate, in (1) time, how many days ago a particular date was, say using Julian dates1

.

Assume that no two files are labeled with the same date.

2.1 Write (in pseudocode) an algorithm that solves this problem while accessing (log) files.

Provide a few sentences describing your approach. Note that your algorithm should output

the most recent date (in number of days ago), which is missing a file.

2.2 Write a recurrence for the worst-case number of files your algorithm looks at, and solve it.

You may use any method for solving the recurrence that we have discussed in class.

blem 2 (20 points) Each day Sullivan goes to break the world record for scaring and Mike's job is to help him do that. He loves his job, but he hates handing out daily reports to his boss Rose. There is a cabinet for each employee to keep their files in chronological order with yesterday's file in front and the oldest file in the back. Mike knows that he has missed some days and Rose will soon find out about it. Rose plans to take some number of the most recent files from anyone's cabinet and check whether any day is missing. Mike and Sulli know about this so during lunch break they try to break into her office and add a fake file to Mike's cabinet. They want to insert this file to the place of the most recent day that Mike has forgotten to hand in his daily report. Afterwards, they fill out the date on the sheet and quickly leave! They could complete this task by simply flipping through the files until they find the first missing day, but this would require looking at (n) files in the worst case. Help them design an algorithm which looks at only O(logn) files as they are in a rush! Your algorithm can access the file deck as follows: for any given i, you can find, in unit time, the date of the ith most recent file directly, without looking at any other files (where 1in ). You can also calculate, in O (1) time, how many days ago a particular date was, say using Julian dates 1. Assume that no two files are labeled with the same date. 2.1 Write (in pseudocode) an algorithm that solves this problem while accessing O(logn ) files. Provide a few sentences describing your approach. Note that your algorithm should output the most recent date (in number of days ago), which is missing a file. 2.2 Write a recurrence for the worst-case number of files your algorithm looks at, and solve it. You may use any method for solving the recurrence that we have discussed in class