READ THE FOLLOWING INSTRUCTIONS CAREFULLY
BEFORE STARTING THE TEST
WHEN YOU ARE FINISHED, UPLOAD THIS EXAM TO CANVAS
WITH YOUR ANSWERS MARKED
COMP
... [Show More] 3270 — Introduction to Algorithms
Spring 2020
Final Exam
EXAM IS OPEN TEXT AND NOTES
ALL ELECTRONIC DEVICES, INCLUDING CALCULATOR, SMARTPHONE,
LAPTOP, TABLET OR SMARTPHONE ARE ALLOWED.
50 multiple choice questions
Each carries 2 points
20% course credit
Mark answers in this PDF file using “Highlight Text” feature of Adobe Acrobat Reader.
Upload the PDF file to Canvas before the due date and time to submit the exam.
Each question has exactly ONE correct answer
Different questions have different difficulty levels
Do not get stuck on any one question!
This test requires 150 minutes to complete.
But you have an extended duration of 300 minutes to complete this test.
You should do your own work.
Any evidence of cheating will result in a zero grade and additional penalties/actions.
Submission deadline will be strictly enforced.
Late submissions will NOT be accepted.
Available at 2:00 PM Tuesday April 28
Due before 7:00 PM Tuesday April 28
Page 2 of 11
Consider the problem of determining whether or not there exists at least one integer i such that A[i]=i in a nonempty array A[first,…,last] of distinct (no-duplicates) integers that is already sorted in the increasing order.
Strategy I: This problem of determining whether there exists an integer i such that A[i]=i in a non-empty sorted
array A[first,…,last] of distinct integers can be solved by scanning the array from cell “first” to cell “last”
checking if any cell contains an integer equal to that cell’s index; if so return true else return false.
Strategy II:
1. If the array has only one cell, return true if the integer in it is the same as that cell’s index; otherwise return
false.
2. Otherwise determine the middle cell of A and return true if the integer in this cell is the same as that cell’s
index; otherwise:
2.1 If the value in that cell is less than that cell’s index, recursively solve the same problem for the left
half of the array and return the resulting Boolean value.
2.1 If the value in that cell is more than that cell’s index, recursively solve the same problem for the
right half of the array and return the resulting Boolean value. [Show Less]