ECM 1414 Workshop Mix Flashcards
(133 cards)
1
Q
What does the term ‘Algorithm’ derive from?
A
A Persian mathematician’s name, Al-Khwarizmi
2
Q
In computer science, an algorithm is best defined as:
A
A problem-solving and computational method
3
Q
Why is the study of algorithms fundamental in computer science?
A
They provide a basis for writing efficient and effective computer programs
4
Q
example of a simple algorithm discussed in the class for
which we provided several versions?
A
Consecutive integer checking for finding the greatest common divisor (GCD)
5
Q
Which statement best describes a characteristic of Euclid’s algorithm for computing
the greatest common divisor (GCD)?
A
It involves division and finding the remainder repetitively
6
Q
Why is the concept of abstraction important in studying algorithms?
A
It is more intuitive for humans than programming language code
7
Q
What characterizes the Fibonacci sequence?
A
Each number is the sum of the two preceding ones
8
Q
In the context of algorithms, how is the Fibonacci sequence typically generated leading
to a very inefficient solution?
A
Through a recursive algorithm
9
Q
How efficient is Euclid’s algorithm for computing the GCD of large numbers?
A
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
10
Q
In Euclid’s algorithm, what happens when one of the numbers (n) becomes zero?
A
The other number (m) is returned as the GCD
11
Q
What notable aspect of Euclid’s algorithm is highlighted in the text regarding its
historical context?
A
It was developed in the 3rd century B.C. by Euclid and appeared in his book
‘Elements’ (Book 7)
12
Q
How is an algorithm defined in computer science, according to Sedgewick (2011), and
probably definition that is not as precise?
A
A finite sequence of instructions, each with a clear meaning, performed in a finite
amount of time
13
Q
According to Levitin (2003), what characterizes an algorithm (and better definition
than the one above)?
A
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
14
Q
What is the primary focus in designing algorithms?
A
Developing specific instructions for solving problems
15
Q
What is the first step in the process of designing algorithms?
A
Understanding the problem
16
Q
What does the equation ‘Algorithms + Data Structures = Programs’ illustrate?
A
The fundamental relationship between algorithms, data structures, and
programs
17
Q
What is a major consideration in the analysis of algorithms?
A
The efficiency of the algorithm with respect to running time and memory space
18
Q
How is the basic operation of an algorithm identified?
A
The most time-consuming operation in the innermost loop
19
Q
What is the RAM model in algorithm design?
A
A hypothetical computer model used for machine-independent algorithm design
20
Q
What does the ‘worst-case’ scenario of an algorithm refer to?
A
The efficiency of the algorithm for the most challenging input of a given size
21
Q
What does the O notation fundamentally represent in asymptotic analysis?
A
The upper bound of a function’s growth rate
22
Q
In the context of Big O notation, what does the statement ‘f(n) = O(g(n))’ imply?
A
f(n) grows at most as fast as g(n)
23
Q
What best describes the Ω (Omega) notation?
A
It represents the lower bound of a function’s growth rate
24
Q
What is the primary use of Θ (Theta) notation in algorithm analysis?
A
To represent the tight bound of a function’s growth rate
25
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)
26
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
27
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))
28
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
29
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
30
In the context of asymptotic notation, what does 'tight bound' mean?
The upper and lower bounds of the algorithm's running time are equivalent
31
How does the Ω (Omega) notation differ from the O (Big O) notation?
Ω denotes a lower bound, while O denotes an upper bound
32
Consider two functions f(n) = n2 and g(n) = n3. What can be written about the two functions?
f(n) = O(g(n))
33
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
34
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))
35
For f(n) = n^0.5 and g(n) = n^2, which statement is correct?
f(n) = O(g(n))
g(n) = Ω(f(n))
36
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))
37
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
38
If f(n) = o(n), what is true about this equation?
f(n) is dominated by n as n approaches infinity
39
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
40
In the context of recurrences, what does 'solving a recurrence relation' typically
involve?
Finding a non-recursive expression that describes the relationship
41
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
42
The binary search algorithm is an example of which kind of problem-solving
approach?
Divide and conquer
43
What does the recurrence relation T(n) = 2T(n-1) + 1 with T(1) = 1 describe?
The time complexity of the towers of Hanoi
44
What represents the closed-form solution for T(n) = 2T(n-1) + 1,
where T(1) = 1?
T(n) = 2^n – 1
45
For the recurrence relation T(n) = 2T(n-1) + 1, what is the value of T(4)?
15
46
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
47
Considering When analysing the solution to a recurrence, why might we consider
the limit as n approaches infinity (n → ∞)?
To understand the asymptotic behaviour
48
In solving recurrence relations, what principle is applied when dealing with a
geometric series?
Summation of terms
49
What is the main goal of utilizing data structures in computer programming?
Organizing and managing data effectively
50
Identify a key feature of linear data structures.
Each element is preceded and followed by another element
51
What distinguishes direct access from sequential access in the context of data
structures?
Immediate accessibility to any data element
52
Which advantage is associated with the use of arrays?
Direct access to individual elements is provided
53
The Sieve of Eratosthenes algorithm finds application in:
Identifying prime numbers within a specified range
54
Which data structure is exemplified by the Sieve of Eratosthenes program?
array
55
The “if (Math.random() < 0.5)” condition in the Coin Flipping Simulation's heads method is significant for:
Simulating the flip of a coin yielding heads
56
what is the coin flipping simulation code?
import random
def heads ():
return random.random() < 0.5
def main(n, m):
result = [0] * (n+1)
for _ in range(m):
cnt = sum(heads() for _ in range (n))
result[cnt] += 1
for j in range (n+ 1):
if result [j] == 0:
print('.', end='')
else:
print('*' * (result[j] // 10), end='')
print()
57
Which of the following best describes the principle of a stack?
Last-In-First-Out (LIFO)
58
In a queue data structure, how are elements removed?
In the same order they were added
59
What is the primary characteristic of Bubble Sort?
It repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order.
60
Which sorting algorithm is considered the most efficient in the best-case scenario?
(note that the best-case scenario of each may be a different configuration of the
elements)
bubble sort
61
In Insertion Sort, what is true about the initial state of the 'sorted' portion of the
array?
It contains only the first element of the array
62
Which algorithm performs sorting by repeatedly choosing the minimum element
from the unsorted portion and moving it to the end of the sorted portion?
Selection Sort
63
Which of the following is a disadvantage of using a linked list over an array?
direct access to elements
64
Which of the following data structures would be most appropriate for
implementing a browser's back button functionality?
stack
65
Which data structure is ideally suited for managing tasks in a printer queue?
queue
66
In a circular queue, what happens when the back pointer reaches the end of the
array?
It moves to the front of the array.
67
Which sorting algorithm conceptually works by dividing the unsorted list into two
halves, sorts each with recursion, and then merges them into a complete sorted
list?
merge sort
68
What Java code snippets correctly demonstrates the operation of
pushing an element onto a stack?
stack[++top] = element;
69
How would you correctly implement the enqueue operation for a queue in Java?
Assume front tracks the first element of the queue and back tracks the last
element of the queue.
queue[++back] = element;
70
Considering a bubble sort algorithm, what pseudocode snippet
accurately represents a single pass for sorting an array in ascending order?
for i from 0 to n-1:
if array[i] > array[i+1]:
swap(array[i], array[i+1])
71
Which algorithmic paradigm does quicksort exemplify?
divide and conquer
72
What is the worst-case time complexity of quicksort?
O(n^2)
73
How does the choice of pivot affect the performance of quicksort?
Choosing the median of a constant number of values as pivot leads to the best
worst-case performance
74
What is the average-case time complexity of Quicksort?
O(n log n)
75
The depth of recursion for Quicksort in the best case is:
O(log n)
76
Which case does the quicksort algorithm perform poorly in?
when the pivot is the smallest or largest element of the array
when the array is already sorted
77
What is a key advantage of MergeSort over QuickSort in certain scenarios?
Better worst-case time complexity
Stable sorting
78
What is NOT a characteristic of MergeSort?
In-place sorting algorithm
79
RadixSort is particularly efficient when:
The range of the input is significantly less than the number of items
80
How does RadixSort handle sorting?
By grouping elements based on their individual digits or letters
81
Radix Sort's time complexity depends on two key factors: the number of elements
(n) and what other factor?
The number of digits in the largest number (k)
82
In the context of Radix Sort, what is the significance of using a stable sorting
algorithm as the subroutine for sorting digits?
It maintains the relative order of records with equal keys (digits).
83
A tree is a data structure where:
Exactly one path exists between any two nodes
84
In a binary tree
A node can have at most two children
85
A leaf node in a tree is defined as a node that:
Has no children
86
Pre-order traversal in a tree means:
Visiting the root before the subtrees
87
An M-ary tree is a tree in which:
Each node can have at most M children
88
The main advantage of a binary search tree (BST) is:
Efficient search, insert, and delete operations
89
Which traversal is used to get nodes in non-decreasing order in a BST?
in-order
90
What is not a direct application of trees?
Performing arithmetic operations
91
What does it mean for a tree to be 'balanced'?
The difference in height between any two subtrees is not more than one
92
In post-order traversal, in what order are the nodes processed?
Left subtree, right subtree, root
93
What statements below are true?
a) There is not binary tree that has the same in-order, pre-order, post-order, and
level order traversals.
b) In a full binary tree, every node other than the leaves has two children.
c) A balanced binary tree guarantees an O(log n) time complexity for insertion.
d) Every binary tree can be considered a binary search tree.
e) A binary tree can be traversed in O(n) time complexity.
b, c, e
94
What statements below are true?
a) You can uniquely reconstruct a binary tree from a given inorder traversal
b) You can uniquely reconstruct a binary tree from a given pre-order traversal
c) You can uniquely reconstruct a binary tree from a given post-order traversal
d) You can uniquely reconstruct a binary tree from a given inorder traversal and
either the postorder or pre-order
e) You can uniquely reconstruct a binary tree from a given pre-order and the
postorder traversals
d
95
What is the main advantage of balanced binary search trees?
O(log n) operation time for most actions
96
What defines a balanced tree?
No leaf is ‘much farther’ from the root than any other
97
Why isn't a binary search tree always kept balanced?
Rebalancing can be costly
98
Who introduced AVL trees?
Georgii Adelson-Velskii and Evgenii Landis
99
How does the AVL tree determine the rotations needed for rebalancing after an
insertion?
By using the balance factor of the nodes from the insertion point up to the root
100
Considering a perfectly balanced AVL tree, what is the maximum number of nodes
it can contain at a height of h?
2^(h+1) - 1
101
What is a characteristic of AVL trees?
Height of subtrees differ by at most one
102
What is the balance factor in AVL trees?
Difference between heights of left and right subtrees
103
What rotations are used to maintain balance in AVL trees?
single rotation
double rotation
104
When is a single-right rotation applied in AVL trees?
When a tree is left-heavy
105
What is the balance factor of all nodes in a perfectly balanced AVL tree?
0
106
Can AVL trees guarantee O(log n) search time?
Yes, due to their balanced nature
107
What is the purpose of double rotations in AVL trees?
To correct imbalances that single rotations cannot
108
How does an AVL tree ensure that operations remain efficient?
By maintaining balance through rotations
109
In an AVL tree, after how many consecutive right insertions starting from an empty
tree will the first rebalancing occur?
After the third insertion, causing a right-right case.
110
Which operation does not guarantee O(log n) time complexity in an AVL tree,
assuming arbitrary sequences of operations?
Level-order traversal
111
What is the balance factor of a node that triggers a double rotation during AVL tree
rebalancing?
2
or
-2
112
What is a characteristic feature of a max-heap?
No child has a value bigger than the value of its parent
113
In a max-heap, where is the maximum element found?
at the root
114
What operations are used to maintain the heap property in a binary heap?
sink and swim
115
Given a binary max-heap implemented as an array, where the array indices start at
1, what conditions must always be true for any valid index i
(where i > 1) in the heap?
The parent of the node at index i is at index i/2.
The left child of the node at index i is at index 2i.
The right child of the node at index i is at index 2i + 1.
116
What is the result of performing a 'sink' operation in a complete tree in reverse
level order?
The heap property is restored by moving down elements that are out of place
117
Which of the following best describes heapify operation?
Adjusting a binary tree to maintain the heap property
118
What is the time complexity of building a heap from an arbitrary array of
elements?
O(n log n)
119
How does HeapSort sort an array in place?
By constructing a heap and then performing a series of swap and sink operations
120
What is the primary advantage of HeapSort compared to MergeSort?
It sorts in-place, using only a constant amount of extra space
121
Why might job starvation occur in a priority queue implemented with a heap?
Without precautions, continuously arriving high-priority jobs may prevent low priority jobs from being processed
122
describe a graph
A set of vertices connected by edges
123
What does an undirected edge in a graph represent?
A bidirectional relationship between two nodes
124
Which graph representation is most space-efficient for sparse graphs?
adjacency-list representation
125
In the context of BFS, what does a 'white' node represent?
A node that has not been visited
126
Given a directed graph G with V vertices and E edges, and assuming that the graph
may contain cycles, which of the following statements correctly compares the
complexities of DFS and BFS?
BFS can discover the shortest path to all nodes from the start node in O(V + E)
time for unweighted graphs, while DFS cannot guarantee the shortest path.
127
What is a characteristic of BFS?
It can be used to find the shortest path in unweighted graphs
128
How does DFS differ from BFS in terms of exploration?
DFS explores as far as possible along a branch before backtracking
129
What is a cycle in a graph?
A path that starts and ends at the same vertex
130
What is true about directed graphs?
Edges have a direction from one vertex to another
131
What is true about dense graphs?
They have a number of edges close to the maximal number of edges
132
Consider a graph G that is a tree (i.e., a connected, acyclic, undirected graph). If
you perform DFS and BFS starting from the same node in G, which of the following
statements is true?
a) DFS will always finish before BFS.
b) BFS will visit the nodes in the exact opposite order of DFS.
c) The order in which leaf nodes are visited is the same in both DFS and BFS.
d) DFS will visit exactly half the number of nodes that BFS visits.
e) The BFS and DFS traversals will produce identical sequences of visited nodes.
c
133
What does a complete graph mean?
A graph where each vertex is connected to every other vertex
