Algorithms Exam Questions and Answers Fully Solved Graded A+
Definition of an algorithm - Answersa sequence of unambiguous instructions for solving a problem (for
obtaining a required output for any legitimate input in a finite amount of time)
Requirements of an algorithm - Answers- Non-ambiguity (set of steps)
- Carefully specified range of inputs
- Output must be correct for anything in that range
- It has to be completed in a finite amount of time
Misc algorithm stuff - Answers- Same algorithm can be represented in several different ways
- Several algorithms for solving the same problem may exist
- May have dramatically different speeds
GCD (Euclids Alg) - Answersinput: two integers m and n, >= 0 and not both 0
while n != 0 {
r = m mod n
m=n
n=r
}
return m
Steps for algorithm design - Answers1) Understand the problem
2) Figure out what your computer is capable of (sequential vs parallel)
3) Choose exact or approximate
4) Pick a data structure
5) Consider algorithm design techniques
(Prove correctness, analyze algorithm, code it)
Important problem types - Answers1) Sorting
2) Searching
, 3) String processing
4) Graph problems
5) Combinatorial
6) Geometric
7) Numeric
Time Efficiency (Def) - AnswersHow fast an algorithm runs (easier to improve than space efficiency)
Space Efficiency (Def) - AnswersHow much space an algorithm requires
Basic Operation (Def) - AnswersThe most expensive most commonly used operation
Order of Growth (order) - Answersc, log n, log (n^2), (log n) ^2, n^(1/3), n^(1/2), n, n (log n), n^2, n^3,
2^n, n!
Is average case efficiency often (worst case + best case)/2? - AnswersNo
Big Oh, O(g(n)) -meaning - AnswersSet of all functions with the same or smaller growth rates as g(n)
Big Omega, Ω(g(n)) -meaning - AnswersSet of all functions with the same or greater growth rates than
g(n)
Big Theta, Θ(g(n)) -meaning - AnswersSet of all functions with the same order of growth as g(n)
How do you prove big theta? - AnswersProve that big omega and big oh are of equal growth orders
Big Oh, O(g(n)) -definition - Answersthere exists a positive constant (c) and a non-negative integer n0
such that
t(n) <= c*g(n) for all n>= n0
Big Omega, Ω(g(n)) -definition - Answersthere exists a positive constant (c) and a non-negative integer
n0 such that
t(n) >= c*g(n) for all n>= n0
Big Theta, Θ(g(n)) -definition - Answersthere exists a positive constants (c1 and c2) and a non-negative
integer n0 such that
Definition of an algorithm - Answersa sequence of unambiguous instructions for solving a problem (for
obtaining a required output for any legitimate input in a finite amount of time)
Requirements of an algorithm - Answers- Non-ambiguity (set of steps)
- Carefully specified range of inputs
- Output must be correct for anything in that range
- It has to be completed in a finite amount of time
Misc algorithm stuff - Answers- Same algorithm can be represented in several different ways
- Several algorithms for solving the same problem may exist
- May have dramatically different speeds
GCD (Euclids Alg) - Answersinput: two integers m and n, >= 0 and not both 0
while n != 0 {
r = m mod n
m=n
n=r
}
return m
Steps for algorithm design - Answers1) Understand the problem
2) Figure out what your computer is capable of (sequential vs parallel)
3) Choose exact or approximate
4) Pick a data structure
5) Consider algorithm design techniques
(Prove correctness, analyze algorithm, code it)
Important problem types - Answers1) Sorting
2) Searching
, 3) String processing
4) Graph problems
5) Combinatorial
6) Geometric
7) Numeric
Time Efficiency (Def) - AnswersHow fast an algorithm runs (easier to improve than space efficiency)
Space Efficiency (Def) - AnswersHow much space an algorithm requires
Basic Operation (Def) - AnswersThe most expensive most commonly used operation
Order of Growth (order) - Answersc, log n, log (n^2), (log n) ^2, n^(1/3), n^(1/2), n, n (log n), n^2, n^3,
2^n, n!
Is average case efficiency often (worst case + best case)/2? - AnswersNo
Big Oh, O(g(n)) -meaning - AnswersSet of all functions with the same or smaller growth rates as g(n)
Big Omega, Ω(g(n)) -meaning - AnswersSet of all functions with the same or greater growth rates than
g(n)
Big Theta, Θ(g(n)) -meaning - AnswersSet of all functions with the same order of growth as g(n)
How do you prove big theta? - AnswersProve that big omega and big oh are of equal growth orders
Big Oh, O(g(n)) -definition - Answersthere exists a positive constant (c) and a non-negative integer n0
such that
t(n) <= c*g(n) for all n>= n0
Big Omega, Ω(g(n)) -definition - Answersthere exists a positive constant (c) and a non-negative integer
n0 such that
t(n) >= c*g(n) for all n>= n0
Big Theta, Θ(g(n)) -definition - Answersthere exists a positive constants (c1 and c2) and a non-negative
integer n0 such that
