ECM 1414 Workshop Mix Flashcards
What does the term ‘Algorithm’ derive from?
A Persian mathematician’s name, Al-Khwarizmi
In computer science, an algorithm is best defined as:
A problem-solving and computational method
Why is the study of algorithms fundamental in computer science?
They provide a basis for writing efficient and effective computer programs
example of a simple algorithm discussed in the class for
which we provided several versions?
Consecutive integer checking for finding the greatest common divisor (GCD)
Which statement best describes a characteristic of Euclid’s algorithm for computing
the greatest common divisor (GCD)?
It involves division and finding the remainder repetitively
Why is the concept of abstraction important in studying algorithms?
It is more intuitive for humans than programming language code
What characterizes the Fibonacci sequence?
Each number is the sum of the two preceding ones
In the context of algorithms, how is the Fibonacci sequence typically generated leading
to a very inefficient solution?
Through a recursive algorithm
How efficient is Euclid’s algorithm for computing the GCD of large numbers?
It is efficient and converges quickly, taking about O(k) steps where k is the number
of digits in the minimum of m and n
In Euclid’s algorithm, what happens when one of the numbers (n) becomes zero?
The other number (m) is returned as the GCD
What notable aspect of Euclid’s algorithm is highlighted in the text regarding its
historical context?
It was developed in the 3rd century B.C. by Euclid and appeared in his book
‘Elements’ (Book 7)
How is an algorithm defined in computer science, according to Sedgewick (2011), and
probably definition that is not as precise?
A finite sequence of instructions, each with a clear meaning, performed in a finite
amount of time
According to Levitin (2003), what characterizes an algorithm (and better definition
than the one above)?
It is a finite sequence of unambiguous instructions for solving a problem, obtaining
the required output for any legitimate input in a finite amount of time
What is the primary focus in designing algorithms?
Developing specific instructions for solving problems
What is the first step in the process of designing algorithms?
Understanding the problem
What does the equation ‘Algorithms + Data Structures = Programs’ illustrate?
The fundamental relationship between algorithms, data structures, and
programs
What is a major consideration in the analysis of algorithms?
The efficiency of the algorithm with respect to running time and memory space
How is the basic operation of an algorithm identified?
The most time-consuming operation in the innermost loop
What is the RAM model in algorithm design?
A hypothetical computer model used for machine-independent algorithm design
What does the ‘worst-case’ scenario of an algorithm refer to?
The efficiency of the algorithm for the most challenging input of a given size
What does the O notation fundamentally represent in asymptotic analysis?
The upper bound of a function’s growth rate
In the context of Big O notation, what does the statement ‘f(n) = O(g(n))’ imply?
f(n) grows at most as fast as g(n)
What best describes the Ω (Omega) notation?
It represents the lower bound of a function’s growth rate
What is the primary use of Θ (Theta) notation in algorithm analysis?
To represent the tight bound of a function’s growth rate
When a function f(n) is said to be in o (little-o) notation with respect to g(n), it
means:
f(n) grows strictly slower than g(n)
What does the statement ‘f(n) = Θ(g(n))’ imply about f(n) and g(n)?
f(n) grows at the same rate as g(n)
f(n) and g(n) have equivalent upper and lower bounds
How does transitivity apply in the comparison of functions in asymptotic analysis?
If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))
If f(n) = Ω(g(n)) and (n) = Ω(h(n)), then f(n) = Ω(h(n))
If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n))
In asymptotic analysis, what does the usage of limits indicate when comparing the
growth of functions?
A method to compare the relative growth rates of functions
What does it mean if an algorithm has a time complexity of Θ(n2)?
The algorithm’s running time is exactly proportional to the square of the input
size
In the context of asymptotic notation, what does ‘tight bound’ mean?
The upper and lower bounds of the algorithm’s running time are equivalent
How does the Ω (Omega) notation differ from the O (Big O) notation?
Ω denotes a lower bound, while O denotes an upper bound
Consider two functions f(n) = n2 and g(n) = n3. What can be written about the two functions?
f(n) = O(g(n))
For the functions f(n) = 100n + log n and g(n) = n, what is the relationship between
f(n) and g(n)?
f(n) = O(g(n))
g(n) = O(f(n))
f(n) = Ω(g(n))
f(n) = Θ(g(n))
g(n) = Θ(f(n))
all here apply
Considering f(n) = n! (n factorial) and g(n) = 2^n, how do these functions compare?
g(n) = O(f(n))
f(n) = Ω(g(n))
For f(n) = n^0.5 and g(n) = n^2, which statement is correct?
f(n) = O(g(n))
g(n) = Ω(f(n))
If f(n) = 2^n and g(n) = n^10, how do f(n) and g(n) compare asymptotically?
g(n) = O(f(n))
f(n) = Ω(g(n))
What does the notation f(n) = o(g(n)) indicate about the functions f(n) and g(n)?
f(n) grows slower than g(n) and becomes insignificant as n approaches infinity
If f(n) = o(n), what is true about this equation?
f(n) is dominated by n as n approaches infinity
What is the primary difference between little o (o) and little omega (ω) notations?
o notation signifies a non-tight (strict) upper bound, while ω signifies a non-tight
(strict) lower bound
In the context of recurrences, what does ‘solving a recurrence relation’ typically
involve?
Finding a non-recursive expression that describes the relationship
How is the recurrence relation for the ‘Two-Flips Method’ in pancake flipping
problem defined? Assume the cost is measured as a function of the number of
pancakes.
T(n) = T(n-1) + n
The binary search algorithm is an example of which kind of problem-solving
approach?
Divide and conquer
What does the recurrence relation T(n) = 2T(n-1) + 1 with T(1) = 1 describe?
The time complexity of the towers of Hanoi
What represents the closed-form solution for T(n) = 2T(n-1) + 1,
where T(1) = 1?
T(n) = 2^n – 1
For the recurrence relation T(n) = 2T(n-1) + 1, what is the value of T(4)?
15
Considering the solution to the recurrence T(n) = 2T(n-1) + 1, T(1) = 1, how does
T(n) grow with respect to n?
Exponentially with 2^n
Considering When analysing the solution to a recurrence, why might we consider
the limit as n approaches infinity (n → ∞)?
To understand the asymptotic behaviour
In solving recurrence relations, what principle is applied when dealing with a
geometric series?
Summation of terms
What is the main goal of utilizing data structures in computer programming?
Organizing and managing data effectively
Identify a key feature of linear data structures.
Each element is preceded and followed by another element
What distinguishes direct access from sequential access in the context of data
structures?
Immediate accessibility to any data element
Which advantage is associated with the use of arrays?
Direct access to individual elements is provided
The Sieve of Eratosthenes algorithm finds application in:
Identifying prime numbers within a specified range