CS161 Exam Questions and Answers Fully Solved Graded A+
Asymptotic Notation - Answers the classification of runtime complexity that uses functions that indicate
only the growth rate of a bounding function
Big-Oh Notation - Answers Represents the upper bound of the run-time of an algorithm, aka worst-case
complexity
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
Little-Oh Notation (o) - Answers The not asymptotically tight upper bound of an algorithm (removes
equality in Big-Oh)
o(g(n)) = { f(n): for any positive constant c, there exists a positive contact n0 such that 0 ≤ f(n) < cg(n) for
all n ≥ n0 }
Theta Notation (Θ) - Answers Encloses the function/run-time from above and below, and is used to for
analyzing the average-case complexity of an algorithm
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that Θ (g(n)) = {f(n): there exist positive
constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set
Omega-Notation (Ω) - Answers The lower bound of run-time of an algorithm, aka Best Case complexity
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
Permutation - Answers The number of ways objects can be ordered that can be created from a
particular set.
Permutation Formula - Answers nPr = n!/(n-r)!
P = # of possible different arrangements
n = total number of objects
,r = the number of objects selected
Combinations - Answers The number of different ways in which objects can be arranged without regard
to order, usually in smaller sets than a particular set. (Smaller than permutations)
Combination Formula - Answers nCr = n!/r!(n-r)!
C = number of combinations
n = total number of objects
r = number of objects selected
Factorials - Answers all possible outcomes for an event
Example of the difference b/w Permutations & Combinations: - Answers Suppose there are 11 runners in
a race.
Most of the time, all 11 runners aren't given places, just the first 3. There are 11 possibilities for first
place, 10 possibilities for second place, and 9 possibilities for third place, or 990 permutations in the first
3 places. If all runners were given places, that would lead to 11! places, or 39,916,800 possible
combinations.
probability range - Answers 0 ≤ P(A) ≤ 1
Rule of Addition - Answers P(A∪B) = P(A) + P(B) - P(A∩B)
Probability of event A OR event B occurring:
Where the union of event A and event b is the sum of the probabilities of A and B while subtracting any
overlapping probability between the two events that would be double counted (the instance in which
both events occur)
Rule of Complementary Events - Answers P(A') + P(A) = 1
The compliment A' = 1 - P(A)
P(A) is the probability of event A occurring
, Disjoint Events - Answers P(A∩B) = 0
Events that cannot occur simultaneously (mutually exclusive)
independent events - Answers P(A∩B) = P(A) ⋅ P(B)
The outcome of one event does not affect the outcome of the second event
The probability of event a AND event b occurring is the product of the probability of the individual
events
Conditional Probability - Answers P(A | B) = P(A∩B) / P(B)
The probability of event A occurring given event B has already occurred is equal to the probability that
event A AND event B occur divided by the probability of event B
Bayes Formula - Answers P(A | B) = P(B | A) ⋅ P(A) / P(B)
The probability of event A occurring given event B has already occurred is the product of the probability
of event B given event A and the probability of event A divided by the probability of event B
When to use Bayes Formula? - Answers Bayes theorem is used to find the reverse probabilities if we
know the conditional probability of an event. Hence why the reverse conditional probability is in the
function.
nth Harmonic Number - Answers The sum of reciprocals of the first n natural numbers:
Hn = Sum from k=1 to n of 1/k
Array Data Structure - Answers Arrays are defined as the collection of similar types of data items stored
at contiguous memory locations. It is one of the simplest data structures where each data element can
be randomly accessed by using its index number.
Linked Lists Data structure - Answers A linked list is a linear data structure, in which the elements are
not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
Asymptotic Notation - Answers the classification of runtime complexity that uses functions that indicate
only the growth rate of a bounding function
Big-Oh Notation - Answers Represents the upper bound of the run-time of an algorithm, aka worst-case
complexity
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
Little-Oh Notation (o) - Answers The not asymptotically tight upper bound of an algorithm (removes
equality in Big-Oh)
o(g(n)) = { f(n): for any positive constant c, there exists a positive contact n0 such that 0 ≤ f(n) < cg(n) for
all n ≥ n0 }
Theta Notation (Θ) - Answers Encloses the function/run-time from above and below, and is used to for
analyzing the average-case complexity of an algorithm
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that Θ (g(n)) = {f(n): there exist positive
constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Note: Θ(g) is a set
Omega-Notation (Ω) - Answers The lower bound of run-time of an algorithm, aka Best Case complexity
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
Permutation - Answers The number of ways objects can be ordered that can be created from a
particular set.
Permutation Formula - Answers nPr = n!/(n-r)!
P = # of possible different arrangements
n = total number of objects
,r = the number of objects selected
Combinations - Answers The number of different ways in which objects can be arranged without regard
to order, usually in smaller sets than a particular set. (Smaller than permutations)
Combination Formula - Answers nCr = n!/r!(n-r)!
C = number of combinations
n = total number of objects
r = number of objects selected
Factorials - Answers all possible outcomes for an event
Example of the difference b/w Permutations & Combinations: - Answers Suppose there are 11 runners in
a race.
Most of the time, all 11 runners aren't given places, just the first 3. There are 11 possibilities for first
place, 10 possibilities for second place, and 9 possibilities for third place, or 990 permutations in the first
3 places. If all runners were given places, that would lead to 11! places, or 39,916,800 possible
combinations.
probability range - Answers 0 ≤ P(A) ≤ 1
Rule of Addition - Answers P(A∪B) = P(A) + P(B) - P(A∩B)
Probability of event A OR event B occurring:
Where the union of event A and event b is the sum of the probabilities of A and B while subtracting any
overlapping probability between the two events that would be double counted (the instance in which
both events occur)
Rule of Complementary Events - Answers P(A') + P(A) = 1
The compliment A' = 1 - P(A)
P(A) is the probability of event A occurring
, Disjoint Events - Answers P(A∩B) = 0
Events that cannot occur simultaneously (mutually exclusive)
independent events - Answers P(A∩B) = P(A) ⋅ P(B)
The outcome of one event does not affect the outcome of the second event
The probability of event a AND event b occurring is the product of the probability of the individual
events
Conditional Probability - Answers P(A | B) = P(A∩B) / P(B)
The probability of event A occurring given event B has already occurred is equal to the probability that
event A AND event B occur divided by the probability of event B
Bayes Formula - Answers P(A | B) = P(B | A) ⋅ P(A) / P(B)
The probability of event A occurring given event B has already occurred is the product of the probability
of event B given event A and the probability of event A divided by the probability of event B
When to use Bayes Formula? - Answers Bayes theorem is used to find the reverse probabilities if we
know the conditional probability of an event. Hence why the reverse conditional probability is in the
function.
nth Harmonic Number - Answers The sum of reciprocals of the first n natural numbers:
Hn = Sum from k=1 to n of 1/k
Array Data Structure - Answers Arrays are defined as the collection of similar types of data items stored
at contiguous memory locations. It is one of the simplest data structures where each data element can
be randomly accessed by using its index number.
Linked Lists Data structure - Answers A linked list is a linear data structure, in which the elements are
not stored at contiguous memory locations. The elements in a linked list are linked using pointers.
