Computer Science And Engineering CSE 232 Lecture Notes - Lecture 2: Cheat Sheet, Selection Sort, Merge Sort
30 Apr 2018
School
Department
Professor
CSE 247 Data Structures
and Algorithms
Fall 2017
Given:
Oct. 2nd, 2017
Exam 1
Start time: 6:30 PM
Due: 8:30 PM
This exam is closed-book, closed-notes except for the single 8.5x11in “crib sheet” mentioned in
class. No electronic devices or resources of any kind are allowed. Your work must be legible. Work that
is difficult to read will receive no credit.
You must sign the pledge below for your exam to be counted. Any cheating will cause the
student(s) involved to at the very least receive a 0 on the exam and incur academic integrity procedures.
Other action may be taken.
Your work must be completed on these pages. There are blank pages at the end of the exam if
you need them. Remember not to spend too much time staying stuck on any one question: if you’re stuck,
move on and return to the question later.
You must fill in your identifying information correctly below. PLEASE PRINT.
Name:
Student ID (Print VERY clearly):
Problem
Number:
Possible
Points:
Received
Points
1
30
2
20
3
15
4
10
5
15
6
10
Total
100
Pledge: On my honor, I have neither given nor received any unauthorized aid on this exam.
Signed: _________________________________________________________________
(Be sure you filled in your information in the box above!)
1
1. (30 points) Asymptotic complexity:
a. (5 points) f(n) = Θ(n
2
)
for which of the following definitions of f(n)
?
Circle all that apply:
■ f(n) = 1
■ f(n) = n
2
log n
■ f(n) = n
2
/
247
■ f(n) =
131n
3
-
500
■ f(n) = n ( n -
2)·
■ None of the above
b. (5 points) f(n) = Θ(n)
for which of the following definitions of f(n)
?
Circle all that apply:
■ f(n) =
247n
+ 19
■ f(n) = log n
■ f(n) = 5n / (n - 1)
■ f(n) =
131n
2
-
500
■ f(n) = n ( n -
2)·
■ None of the above
Read the following questions carefully, as they are phrased differently from the
above.
c. (5 points) n
log n + n = O(g(n))
for which of the following definitions of g(n)
?
Circle all that apply:
■ g(n) = n
■ g(n) = n log n + 10
■ g(n) = n
5
■ g(n) = n
log(n/2)
■ g(n) = n
3
■ None of the above
d. (5 points) n
log n + n = Ω(g(n))
for which of the following definitions of g(n)
?
Circle all that apply:
■ g(n) = n
■ g(n) = n log n + 10
■ g(n) = n
5
■ g(n) = n
log(n/2)
■ g(n) = n
3
■None of the above
2
e. (5 points) Provide a detailed proof without using ratios and limits of the
following:
3n
+ 7 = O
(n2).
f. (5 points) Provide a detailed proof without using ratios and limits of the
following:
If f(n)
= O(g(n))
, then g(n) + f(n) = O(g(n)).
2. (20 points) We will soon study an algorithm called merge sort.
Merge sort may be generalized
to break the sorting task into any fixed number of subproblems per recursive call; in this
problem, we will consider 3-way
merge sort, which solves 3 subproblems per recursive call.
The runtime of 3-way merge sort may be expressed as
T(n) = 3T(n/3) + n
with base case T(1) = 1.
a. (3 points) Sketch a recursion tree representing the recurrence above. Please sketch at
least 3 levels of the recursion tree plus the base level. You may assume n
is a power
of 3.
3
Document Summary
This exam is closed-book, closed-notes except for the single 8. 5x11in crib sheet mentioned in class. No electronic devices or resources of any kind are allowed. Your work must be legible. work that is difficult to read will receive no credit. You must sign the pledge below for your exam to be counted. Any cheating will cause the student(s) involved to at the very least receive a 0 on the exam and incur academic integrity procedures. Your work must be completed on these pages. There are blank pages at the end of the exam if you need them. Remember not to spend too much time staying stuck on any one question: if you"re stuck, move on and return to the question later. You must fill in your identifying information correctly below . Pledge: on my honor, i have neither given nor received any unauthorized aid on this exam. Signed: _________________________________________________________________ (be sure you filled in your information in the box above!)
