COP 3530 Questions with complete solution 2024

COP 3530 - Quiz #1
Big-oh notation (upper bound) - correct answer ✔- Symbol: O
g(n) <= c * f(n) for all n >= n0


Omega notation (lower bound) - correct answer ✔-Symbol : Ω
0 <= c * f(n) <= g(n) for all n >= n0


Theta notation (tight bound) - correct answer ✔-Symbol: Θ
0 <= c1 * f(n) <= g(n) <= c2 * f(n) for all n >= n0


Little-Oh Notation - correct answer ✔-Symbol: o
0 <= g(n) < c * f(n) for all n >= n0


Little omega Notation - correct answer ✔-Symbol: ω
0 <= c * f(n) < g(n) for all n >= n0


Asymptotic notation uses - correct answer ✔-simplify expressions
-O(1) denotes a constant function
- express running times of algorithms


n∑i (i=0) - correct answer ✔n(n+1)/2 = O(n^2)


n∑i^2 (i=0) - correct answer ✔n(n+1)(2n+1)/6 = O(n^3)


n∑i^3 (i=0) - correct answer ✔[n(n+1)/2]^2 = O(n^4)

, growth rate functions from slowest to fastest - correct answer ✔1, √n, n,
nlogn, nlog^2n, n^2, n^2logn, n^3, 2^n, n!


Algorithm - correct answer ✔intuitive concept: finite collection of steps to
solve a problem in a mechanical way.


formal concept: a model of a computer is defined and an algorithm is simply a
program for that ideal computer.


computability - correct answer ✔existence of algorithms


complexity - correct answer ✔algorithms consuming the least amount of
resources(time, space..)


memory - correct answer ✔each unit is able to store a primitive type value
(integer, real, character..)


Operations - correct answer ✔1. =
2. Arithmetic/math operators (+, -, *, /, %)
3. if- else
4. loops (for, while, do-while)
5.header, call, return
6. i/o statements( FileReader, BufferedReader..)
7. array atomic operations


time/cost of one operation - correct answer ✔1 unit