Font size
WorksheetsQuiz 1 Introduction to Algorithm
Total questions: 10
Worksheet time: 10mins
Proof that 3^n - 1 is a multiple of 2 for n>=1.
Based on the question, choose the correct answer for induction base case.
3^1 - 1 = 2
3^2 - 1 = 8
3^k - 1 = 2^k
3^k - 1 = 2^n
Based on the following list of preference (from most favor to least favor), define the perfect matching from w to v.
v1: w1 w2 w3
v2: w2 w3w1
v3: w3w2 w1
w1: v1 v2 v3
w2: v2 v1 v3
w3: v2 v1 v3
(v1,w1), (v2,w2), (v3, w3)
(v1, w2), (v2, w3), (v3, w1)
(v1, w3), (v2, w1), (v3, w2)
No answer
A program is having the running time as: 1+2+3+...+n, this means that the f(n) is
n+1
n(n+1)/2
n++
n-1
Which of the following is a part of an algorithm?
input
output
steps to be carried out in order to accomplish the task
All the options
The essential characteristics of algorithm are: finiteness, effectiveness and (a) .
Algorithm must be
programming language dependent
programming language independent
either of the above
none of the above
George obtains offer from company B. He accepts the offer. However, his favorite is actually company A. One week later, company A offers George the opportunity. Since Jimmy prefers company A, so he rejects company B although he has accepted the offer. In the view of stable matching, this is a/an
breaking down
stable matching
unethical rejection
human right
ethical rejection
Suppose we are looking at a matching of men and women returned by the Gale‐Shapely algorithm. The matching contains (m, w) and (m’, w’). A stability occurs in a matching when:
(select all that applicable)
m prefers w’ more than w
w’ prefers m less than m’
m prefers w’ more than w and w prefers m’ less than m
m prefers w’ more than w and w’ prefers m more than m’
m’ prefers w more than w’ and w prefers m less than m’
This equation 2^(2 log n ) is equivalent to
4 log n
2 log n^2
n^2
log n^2
Arrange the following steps into a proper sequence where the purpose is to find the maximum value in an array.
1. Search and compare the other elements in the array
2. Return Max element
3. Given an array of all integer elements
4. Stop when complete visit each element in the array
5. If an element is greater than the Max, replace it
6. Assign a variable Max = first element in the array
The correct sequence is: 3, 1, 6, 5, 4, 2
The correct sequence is: 3, 6, 1, 5, 4, 2
The correct sequence is: 6, 5, 3, 1, 4, 2
The correct sequence is: 1, 3, 5, 6, 4, 2
