Computer Science And Engineering CSE 232 Lecture Notes - Lecture 6: Pseudocode, Binary Search Algorithm, Linked List
30 Apr 2018
School
Department
Professor
CSE 247 Data Structures and Algorithms Spring 2017
Exam I
Given: 1 March 2017 Due: End of session
This exam is closed-book, closed-notes. No electronic devices or resources of any kind are
allowed. The exception is the “cheat sheet” as described on our course web pages on which you
may have notes to consult during the exam.
Your wo rk mus t b e legible. Work that is difficult to read will receive no credit. Do not dwell over
punctuation or exact syntax in code; however, be sure to indent your code to show its structure.
You mu st sign the pledge b elow for you r exam to count. Any ch eating will cause the students
involved to receive an F for this course. Other action may be taken.
Your work must b e completed on these pages. Th ere is blank space on some pages of the exam
if you need it. Don’t spend too much time staying stuck on a question: move on and return to the
question later.
You mu st fill in your identifying information correctly. Whenyoureachthispointinthe
instructions, please give the professor or TA a meaningful glance.
Print clearly the following information:
Name (print clearly):
Student 6-digit ID (print really clearly):
Problem Possible Received
Number Points Points
120
210
320
410
520
620
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!)
CSE 247 (Exam I) –2– Due by End of session
1. (20 points)
(a) (5 points) log n=O(g(n)) for which of the following definitions of g(n)?
Circle all that apply:
•g(n)=1
•g(n) = log n+247
•g(n)=n
•g(n)=nlog n
•g(n)=n2log n
•None of the above
(b) (5 points) log n=Ω(g(n)) for which of the following definitions of g(n)?
Circle all that apply:
•g(n)=1
•g(n) = log n+247
•g(n)=n
•g(n)=nlog n
•g(n)=n2log n
•None of the above
Read the following questions carefully: they are phrased different from
the above.
(c) (5 points) f(n)=Θ(n) for which of the following definitions of f(n)?
Circle all that apply:
•f(n)=0
•f(n)=247
•f(n)= n
247
•f(n)=247n
•f(n)=247n+131
•None of the above
(d) (5 points) f(n)=Θ(0) for which of the following definitions of f(n)?
Circle all that apply:
•f(n)=0
•f(n)=247
•f(n)= n
247
•f(n)=247n
•f(n)=247n+131
•None of the above
CSE 247 (Exam I) –3– Due by End of session
2. (10 points) Recall that f(n)=O(g(n)) if
∃c>0∃n0>0|∀n≥n0f(n)≤c·g(n)
Prove that 2n=O(n!).
•To attempt full credit, you do this by induction on n, starting at n=0. You
must use the induction hypothesis
P(n):2
n=O(n!)
You must explicitly show P(0) and then show P(k)→P(k+1)
•Or, for attempt at most half credit, you do a direct proof based on analysis of 2n
and n!.
(a) Circle only one of the above two methods, indicating which proof technique you
are going to use.
(b) Using the notation above, write your proof below. Where needed, state appropri-
ate values for cand n0.
Document Summary
No electronic devices or resources of any kind are allowed. The exception is the cheat sheet as described on our course web pages on which you may have notes to consult during the exam. Work that is di cult to read will receive no credit. Do not dwell over punctuation or exact syntax in code; however, be sure to indent your code to show its structure. You must sign the pledge below for your exam to count. Any cheating will cause the students involved to receive an f for this course. Your work must be completed on these pages. There is blank space on some pages of the exam if you need it. Don"t spend too much time staying stuck on a question: move on and return to the question later. You must ll in your identifying information correctly. When you reach this point in the instructions, please give the professor or ta a meaningful glance.
