程序代写案例-CSC051002|学霸联盟

程序代写案例-CSC051002

时间：2021-10-15

10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php?attempt=319087&cmid=503452 1/5 My Courses / CSC051002-F21R-3801 / Exams / Sample Midterm (Summer 21 Midterm) Started on Wednesday, October 13, 2021, 1:22 PM State Finished Completed on Wednesday, October 13, 2021, 1:24 PM Time taken 1 min 59 secs Grade 15.00 out of 15.00 (100%) Question 1 Correct 1.50 points out of 1.50 Question 2 Correct 1.50 points out of 1.50 Average Case Sequential Search in Array: Assume that the probability that the item is not in the array is . When the item is in the array, the probability that the item is found in index is , the probability that the item is found in index is , and the probability that the item is found in index is The probabilities of matching any of the remaining items are all equal. Assuming that comparison of an array item where the search key is the basic operation, what is the average case complexity function for sequential search of matching 1st through (n-3) items? Select one: a.  b. c. d. Can't be determined because the probabilities given don't add to one. 1 7 1 2 ( − 1) 1 4 ( − 2) 1 8 53−30 56 12−2 36 43−10 160 The correct answer is: 53−30 56 Select one: True  False () = + ∈ ( ) 2 81 +1log 9 8 +2log 2 The correct answer is 'True'. 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php?attempt=319087&cmid=503452 2/5 Question 3 Correct 1.50 points out of 1.50 Question 4 Correct 1.50 points out of 1.50 Given the following recurrence: Assume for this problem T(1) = 0, and Back Substitution is performed. After k steps we get: Which of the following complexity functions represents this recurrence? Select one: a.  b. c. d. () = 2 ( ) + + 1 3 2 () = ( ) + (1+ )+ (2+ )+ ( + )+ ( + )+. . . +( + )2 3 2 2 2 3 2 2 2 2 2 2 3 4 2 3 2 3 2 3 6 2 −1 2 −1 2 3 2(−1) () = (1 − ) + ( − 1) 9 2 7 2log 3 2 2log 3 () = (1− ) + + 1 3 2 7 2 3 2 () = Θ( )log 2 () = (1− ) 3 2 7 2 2log 3 3 2log 3 The correct answer is: () = (1 − ) + ( − 1)9 2 7 2log 3 2 2log 3 Select one: True False  () = + ∈ Ω( ) 2 81 +1log 9 8 +2log 2 The correct answer is 'False'. 10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php?attempt=319087&cmid=503452 3/5 Question 5 Correct 1.50 points out of 1.50 Question 6 Correct 1.50 points out of 1.50 Select one: True  False () = 10 ( ) + ∈ Θ( ) 5 3 ‾‾ √ 3 2 The correct answer is 'True'. for ( k=0; k

for ( p=1; p<(n-3); p++ ) {

for ( j=2; j print("Algos are fun!")
}
}
}
Assuming that the print statement is the basic operation, What is the Big O time complexity (worst case) of this code?
Select one:
a.
b.
c.
d. 
=
2
( log )
2
( )

3
( )
4
( log(log ))
2
The correct answer is: ( log(log ))2
10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review
https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php?attempt=319087&cmid=503452 4/5
Question 7
Correct
1.50 points out of 1.50
Question 8
Correct
1.50 points out of 1.50
Question 9
Correct
1.50 points out of 1.50
T(n) = 81n + 81log9 n+1 ∈ ω(8log2 n+2)
Select one:
True
False 
The correct answer is 'False'.
When computing the average case complexity of a function, ALL the probabilities within \(P_{out}\) are multiplied by \(n\), and ALL the ones within
\(P_{in}\) are multiplied by \(\frac{1}{n}\)
Select one:
True
False 
The correct answer is 'False'.
\(T(n) = 10T(\frac{n}{5}) + \sqrt{n^3} \in O{(n^{\frac{3}{2}})}\)
Select one:
True 
False
The correct answer is 'True'.
10/13/21, 5:39 PM Sample Midterm (Summer 21 Midterm): Attempt review
https://ilearn.sfsu.edu/ay2122/mod/quiz/review.php?attempt=319087&cmid=503452 5/5
Question 10
Correct
1.50 points out of 1.50
func midterm(n) {
if n <= 1 return 1;
for(i=0; i<(n-3); i++) {
for(j=n; j>1; \(j = \frac{j}{2}\)) {
print("Csc510");
}
}
midterm(\(\frac{n}{2}\))
  midterm(\(\frac{n}{2}\))
  midterm(\(\frac{n}{2}\))
  midterm(\(\frac{n}{2}\))
}
What is the Theta time complexity of this function?
Select one:
a. \(T(n) = \Theta(n\log_2^2 n)\)
b. \(T(n) = \Theta(n^2)\) 
c. \(T(n) =\Theta(n^2\log_2 n)\)
d. \(T(n) = \Theta(n\log_2 \log_2 n)\)
The correct answer is: \(T(n) = \Theta(n^2)\)
◀ Recursive Analysis
Jump to...
San Francisco State University
A California State University Campus
Academic Technology

学霸联盟