COMP 2080 Summer 2021 Midterm Practice Problems
代做oop – 这是利用oop进行训练的代写, 对oop的流程进行训练解析, 是比较有代表性的oop等代写方向
Here are some extra practice questions you can use to study for the midterm. Some of these questions are more complex than I would necessarily consider reasonable for a midterm. Also, this is not guaranteed to be an exhaustive list of every possible question or technique that might be tested.
GLOBAL ASSUMPTION. All variables used in code are integers, and remain integers for the entire run of the program. If the/symbol is used, it represents integer division.
Short Answer
- Which of the statements below is true about the following code?
1 //pre: n >= 1
2 j 1
3 k 1
4 while (j < n)
5 kj*k
6 jj+
7 //post: k == n!
(a) This code is partially correct but does not terminate.
(b) This code terminates but is not partially correct.
(c) This code terminates and is partially correct.
(d) This code does not terminate and is not partially correct.
- Consider the following code.
1 //pre: n >= 1
2 an+
3 b2*n-
4 cb-a
5 //assert1: (c >= 0)(n >= 1)
6 d2*n-c
7 //post: d >= 0
The proof of partial correctness of this code is structured in two parts:
(i) (preis true)(line 5 is reached)(assert1is true when line 5 is reached)
(ii) (assert1is true)(line 7 is reached)(postis true when line 7 is reached)
where the proof of part (ii) does not refer to any lines before line 5.
Which of the following is a true statement about the proof of partial correctness of this code?
(a) Parts (i) and (ii) can both be proved
(b) Part (i) can be proved, but part (ii) cannot
(c) Part (ii) can be proved, but part (i) cannot
(d) Neither of parts (i) and (ii) can be proved
- Consider the following code.
1 //pre: n >= 1
2 an
3 b4*n
4 k 0
5 //LoopInv:
6 while (a < b)
7 aa+
8 bb-
9 kk+
10 //post: (a == b)(k == n)
Which of the following candidates forLoopInvis a l oop invariant? Select all that apply.
(a) a = k+n
(b)2*a+b = 6*n
(c) a+b = 5*n
(d)k < n
(e) b % 2 == 0
- Consider the following code.
1 //pre: k >= 1m >= 1
2 while [(k > 10)(m > 20)]
3 if(k is even)
4 kk-
5 mm+
6 else
7 kk+
8 mm-
LetEndenote the value ofEimmediately before thenth check of the loop condition in line
2, for anyn1. Which of the following expressionsEhas the property that for alln1,
En+1En1? Select all that apply.
(a)E=k+m
(b)E=k+m 30
(c) E= 4k+m
(d)E= 4k+m 50
(e) E= 10k+m
(f)E= 10k+m 200
- Consider the following code.
1 //pre: k >= 1m >= 1
2 while [(k > 10)(m > 20)]
3 if(k is even)
4 kk-
5 mm+
6 else
7 kk+
8 mm-
Which of the following expressionsE has the property thatE 0 implies that the loop
terminates? Select all that apply.
(a)E=k+m
(b)E=k+m 30
(c) E= 4k+m
(d)E= 4k+m 50
(e) E= 10k+m
(f)E= 10k+m 200
- Consider the following code.
1 //pre: (n >= 2)(n is even)
2 kn
3 a 1
4 while (k > 0)
5 aa*k
6 kk-
Letf(n) represent the number of STEPS carried out by this code as a function of the inputn.
One step is defined to be one line of code that contains a fixed number of primitive operations.
Which of the following is an expression forf(n)?
(a) f(n) = 3 +
n/ 2 1
m=
(3)
(b)f(n) = 3 +
n/^2
m=
(3)
(c) f(n) = 3 +
n 1
m=
(3)
(d)f(n) = 3 +
n
m=
(3)
- Consider the following code.
1 //pre: A.length >= 1
2 nA.length
3 a 0
4 k 0
5 while (k < n)
6 jn
7 while (j >= k)
8 aa + A[j]
9 jj-
10 kk+
Letf(n) represent the number of STEPS carried out by this code as a function of the input
sizen. A step is defined to be one line of code that contains a fixed number of primitive
operations.
Which of the following is an expression forf(n)?
(a) f(n) = 4 +
n 1
k=
(
4 +
nk 1
m=
(3)
)
(b)f(n) = 4 +
n
k=
(
4 +
nk 1
m=
(3)
)
(c) f(n) = 4 +
n 1
k=
(
4 +
nk
m=
(3)
)
(d)f(n) = 4 +
n 1
k=
(
4 +
nk 1
m=
(3)
)
- Consider the following code.
1 //pre: A.length >= 2
2 nA.length
3 a 0
4 k 0
5 while (k < n-1)
6 if (A[k] < A[k+1])
7 aa + A[k]
8 else if (A[k] > A[k+1])
9 j 0
10 while (j < k)
11 aa + A[j]
12 jj+
13 else
14 j 0
15 while (j < n)
16 aa + A[j]
17 jj+
Which of the following candidates for the arrayAresults in the worst case whenn= 4?
(a) A={ 1 , 2 , 3 , 4 }
(b)A={ 1 , 1 , 3 , 3 }
(c) A={ 4 , 3 , 2 , 1 }
(d)A={ 2 , 2 , 2 , 2 }
- Each statement (a) (d) proves exactly one of the statements (i) (iv). Match the statement with its implication. For example, if the statement (a) proves thatf(n)O(n), match (a) with (i).
(a) Letn 0 >0 be arbitrary, and letn= 2n 0. Thenf(n)< 5 n.
(b) LetM >0 be arbitrary. For alln > M^2 ,f(n)< Mn.
(c) For alln >5,f(n)< 10 n.
(d) LetM >0 andn 0 >0 be arbitrary, and letn=M+n 0. Thenf(n)< Mn.
(i)f(n)O(n)
(ii)f(n)o(n)
(iii)f(n)/(n)
(iv) f(n)/(n)
- Letf(n) =n^2 +nandg(n) =^13 n^2. Which of the following statements are true? Select all that apply.
(a) f(n)O(g(n))
(b)f(n)o(g(n))
(c) f(n)(g(n))
(d)f(n)(g(n))
(e) f(n)(g(n))
(f) There isM >0 such that for alln >1,f(n)Mg(n)
(g) There isn 0 >0 such that for alln > n 0 ,f(n) 2 g(n)
(h) There isM >0 such that for alln >1,g(n)Mf(n)
(i) There isn 0 >0 such that for alln > n 0 ,g(n)^14 f(n)
- Consider the following recurrence relation.
T(n) =
{
1 , n 2
2 T
(n
3
)
+n^2 , n > 2
In the THIRD ROW of the recursion tree corresponding to this recurrence relation, there are
four nodes. Which of the following statements is true about these nodes?
(a) Each node is labeled by
n
3
(b) Each node is labeled by
n
32
(c) Each node is labeled by
n
33
(d) Each node is labeled by
n
34
(e) Each node is labeled by
n^2
3
(f) Each node is labeled by
n^2
32
(g) Each node is labeled by
n^2
33
(h) Each node is labeled by
n^2
34
- Which case of the Master Theorem applies to the following recurrence relation?
T(n) =
{
1 , n < 5
3 T
(n
5
)
+
n n 5
(a) Case 1
(b) Case 2
(c) Case 3
(d) None of the cases apply
- Consider the following recurrence relation.
T(n) =
{
1 , n= 1
2 T
(n
2
)
+n^2 , n 2
Which of the following are true statements aboutT(n)? Select all that apply.
(a) T(n)(n)
(b)T(n)(nlog(n))
(c) T(n)(n^2 )
(d)T(n)(n^2 log(n))
(e) T(n) = 2n1 ifnis a power of 2
(f)T(n) = 2nnifnis a power of 2
(g) T(n) = 2n^2 1 ifnis a power of 2
(h)T(n) = 2n^2 nifnis a power of 2
- In the following recurrence relation,aandbare constants.
T(n) =
{
1 , n < b
aT
(n
b
)
+n, nb
For which values ofaandbcan we conclude thatT(n)(nlog(n))? Select all that apply.
(a)a= 2,b= 2
(b)a= 4,b= 2
(c) a= 2,b= 4
(d)a= 4,b= 4
Full Solution
- Consider the following code.
1 //pre: n >= 1
2 an+
3 b2*n-
4 cb-a
5 //assert1:
6 d2*n-c
7 //post: d >= 7
The proof of partial correctness of this code is structured in two parts:
(i) (preis true)(line 5 is reached)(assert1is true when line 5 is reached)
(ii) (assert1is true)(line 7 is reached)(postis true when line 7 is reached)
where the proof of part (ii) does not refer to any lines before line 5.
Fill in the assert statement in line 5. It should include exactly enough information to complete
the two parts of the proof of partial correctness, and no more. Then prove partial correctness
for this code, using the structure given above.
- Consider the following code.
1 //pre: x is an integer
2 yx
3 if (x is odd)
4 y2*y
5 //assert1:
6 zy*y
7 //post: z % 4 == 0
The proof of partial correctness of this code is structured in two parts:
(i) (preis true)(line 5 is reached)(assert1is true when line 5 is reached)
(ii) (assert1is true)(line 7 is reached)(postis true when line 7 is reached)
where the proof of part (ii) does not refer to any lines before line 5.
Fill in the assert statement in line 5. It should include exactly enough information to complete
the two parts of the proof of partial correctness, and no more. Then prove partial correctness
for this code, using the structure given above.
- Use a proof by induction to prove that the following recursively defined function is fully correct.
//pre: (n >= 1)(a >= 2)
int mySum(int n, int a)
if (n == 1)
return 1
return a*mySum(n-1, a) + 1
//post: returns (an-1)/(a-1)
- Consider the following code.
1 //pre: n >= 1
2 k 0
3 a 0
4 //LoopInv:
5 while (k < n)
6 aa + 2*k + 1
7 kk+
8 //post: a == n*n
The proof of partial correctness of this code is structured in two parts:
(i) (preis true)(LoopInvis a loop invariant)
(ii) (LoopInvis a loop invariant)(line 8 is reached)(postis true when line 8 is reached)
where the proof of part (ii) does not refer to any lines before line 5.
Fill in an expression forLoopInvthat can be used to prove parts (i) and (ii) above. Then
complete the proof of partial correctness according to the given structure.
- Consider the following code.
1 //LoopInv: (j >= 9)(k >= 5)
2 while [(j > 10)(k > 5)]
3 if (j > 10)
4 jj-
5 kk+
6 else
7 kk-
Prove that this code terminates by stating and proving a loop measureE. You can use the
given loop invariant without proof.
- Find an expression forf(n), the number of STEPS carried out by the following code as a function of the inputn. A step is defined to be one line of code that contains a fixed number of primitive operations. Assume thatn= 2rfor somer0. Simplify your answer until it only depends onn, notr. Assume that integer division is used. You can use the loop invariants without proof.
1 //pre: n == 2rfor some r >= 0
2 kn
3 m 0
4 //LoopInv1: (k == 0)(k == n/2m)
5 while (k > 1)
6 j 0
7 q 0
8 //LoopInv2: j == 2*q
9 while (j < k)
10 jj+
11 qq+
12 kk/
13 mm+
- Find an expression forf(n), the number of STEPS carried out by the following code as a function of the inputn, in the worst case. A step is defined to be one line of code that contains a fixed number of primitive operations. Give an example of an array A of length 4 that results in the worst case.
1 //pre: A.length >= 2
2 nA.length
3 k 0
4 while (k < n)
5 if (A[k] == k)
6 j 0
7 while (j < k)
8 A[j]A[j] + k
9 jj+
10 else
11 A[k]A[k] + k
12 kk+
- Prove each of the following, using ONLY the definitions of asymptotic notation and properties of inequalities and real numbers. Do NOT use limits, and do NOT use the hierarchy of functions.
(a)^14 n^4 n^3 (n^3 )
(b) 5n+ 4no(10n)
(c)
n^2 + 1(n)
(d)
n 2 n/O(2n)
(e) n^5 +n^2 /(n^5 )
- Solve the following recurrence relation using the substitution method, then prove your solution by mathematical induction.
T(n) =
{
1 , n= 1
3 T(n1) + 1, n > 1
- Below is one way to represent the mergesort algorithm.
1 //pre: A.length >= 1, 0 <= j,k <= A.length
2 int [] mergeSort(int [] A, int j, int k)
3 if (j < k)
4 A1 = mergeSort(A, j, (j+k)/2)
5 A2 = mergeSort(A, (j+k)/2+1, k)
6 return merge(A1, A2)
7 else
8 return A
The functionmerge()receives two sorted integer arraysA1 andA2 of lengthsn 1 andn 2 , and
returns the sorted list of lengthn=n 1 +n 2 that results from mergingA1 andA2. You can
assume that the cost of this function is of ordern.
(a) LetT(n) be the cost ofmergeSort()as a function ofn=kj+ 1. Write down a
recurrence relation satisfied byT(n) in the special case wheren= 2rfor somer0.
Approximate a constant number of steps by 1, and approximate a sum of terms by the
highest order term.
(b) Solve this recurrence relation using the substitution method, then prove your solution
using mathematical induction. You can assume thatn= 2rfor somer0.
(c) Apply the Master Theorem to your recurrence relation and confirm that your solution
is of the correct order.
- For each of the following recurrence relations, draw the recursion tree, calculate the sum of each row, and use the result to conjecture a functiong(n) such thatT(n)(g(n)). Then use the Master Theorem to confirm your conjecture.
(a)
T(n) =
{
1 , n 2
3 T
(n
3
)
+n^2 , n > 2
(b) Hint: if the row sums form a geometric series of the form
M
k=
qkwhereq >1, then you
cannot estimate an upper bound on the sum by considering the corresponding infinite
geometric series. You have to estimate where the series ends.
T(n) =
{
1 , n 3
8 T
(n
4
)
+n, n > 3
(c)
T(n) =
{
1 , n 3
2 T
(n
4
)
+
n, n > 3
Short Answers
- (b)
- (d)
- (a), (b), (e)
- (c), (d)
- (a), (b), (c), (d), (e)
- (a)
- (c)
- (d)
- (a) (iv), (b) (ii), (c) (i), (d) (iii)
- (a), (c), (d), (f), (h)
- (h)
- (a)
- (c), (h)
- (a), (d)
Full Solution Remarks and Hints
- One option is//assert1: (c == n-6)(n >= 1).
- One option is//assert1: y is even. In the proof of (i), proceed by cases on whetherxis even or odd.
- Leta 2 be arbitrary, and proceed by induction onn. The induction step amounts to showing that a
an 1
a 1
+ 1 =
an+1 1
a 1
.
- One option is//LoopInv: (a == k*k)(k <= n).
- One option isE= 2j+k23. Note that the loop invariant implies that 2j+k23. If E 0, then 2k+j= 23, which only occurs ifj = 9 andk= 5, in which case the loop condition is false.
- Outer loop:mstarts at 0 and counts up by 1s tor1. Inner loop:qstarts at 0 and counts up by 1s to k 2 1. Sincek= 2 nm, we can rewrite the upper limit for the sum overqas k 2 1 =
n
2 m+11. The number of steps is then
f(n) = 1 + 1
lines 2 , 3
+
r^1
m=
1 + 1 + 1
lines 5 , 6 , 7
+
n/ (^2) m+1 1 q=
1 + 1 + 1
lines 9 , 10 , 11
+ 1 + 1 + 1
last 9 ,lines 12 , 13
+ 1
last 4
This eventually simplifies tof(n) = 3n+ 6 log 2 (n).
- The worst case occurs ifA[k] =kfor allk. For example,A={ 0 , 1 , 2 , 3 }results in the worst case forn= 4. Outer loop:kstarts at 0 and counts up by 1s ton1. Inner loop:jstarts at 0 and counts up by 1s tok1. The number of steps is
f(n) = 1 + 1
lines 2 , 3
+
n 1
k=
1 + 1 + 1
lines 4 , 5 , 6
+
k 1
j=
1 + 1 + 1
lines 7 , 8 , 9
+ 1 + 1
last 7 ,line 12
+ 1
last 4
which simplifies tof(n) = 3 + 5n+ 3
n(n1)
2
.
- Techniques/hints:
(a) Factor out/cancel offn^3.
(b) Note that 5n+ 4n< 2 5 n, and
2 5 n
10 n
=
2
2 n
= 2^1 n.
(c)
n^2 + 1nfor anyn >0. To show that
n^2 + 1< Mnfor someM, round 1 up ton^2.
(d) The factors of 2ncancel. You need to findnso that
nis larger than some arbitrarily
chosenM.
(e) Roundn^2 up ton^5.
- T(n) = 3jT(nj) +
j 1
k=0^3
k forj = 0, 1 ,... , n1. Whenj =n1, this simplifies to
T(n) =
3 n 1
2
.
- Comments/answers
(a)
T(n) =
{
1 , n= 1
2 T
(n
2
)
+n, n > 1
(b)T(n) = 2jT
(n
2 j
)
+jnforj= 1, 2 ,... , r. Whenj=r, this reduces toT(n) =n+nlog 2 (n),
noting thatr= log 2 (n).
(c) Case 2 of the Master Theorem applies. The conclusion is thatT(n)(nlog(n)), which
is consistent with the result in part (b).
- Comments/answers
(a) Case 3 applies; concludeT(n)(n^2 )
(b) Case 1 applies; concludeT(n)(n^3 /^2 )
(c) Case 2 applies; concludeT(n)(
nlog(n))