Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

I40(0/1/2) Computer Science Bsc > ECM 1414 Workshop Mix > Flashcards

ECM 1414 Workshop Mix Flashcards

1
Q

What does the term ‘Algorithm’ derive from?

A

A Persian mathematician’s name, Al-Khwarizmi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

In computer science, an algorithm is best defined as:

A

A problem-solving and computational method

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Why is the study of algorithms fundamental in computer science?

A

They provide a basis for writing efficient and effective computer programs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Why is the concept of abstraction important in studying algorithms?

A

It is more intuitive for humans than programming language code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What characterizes the Fibonacci sequence?

A

Each number is the sum of the two preceding ones

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the primary focus in designing algorithms?

A

Developing specific instructions for solving problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the first step in the process of designing algorithms?

A

Understanding the problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does the equation ‘Algorithms + Data Structures = Programs’ illustrate?

A

The fundamental relationship between algorithms, data structures, and
programs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How is the basic operation of an algorithm identified?

A

The most time-consuming operation in the innermost loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the RAM model in algorithm design?

A

A hypothetical computer model used for machine-independent algorithm design

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does the O notation fundamentally represent in asymptotic analysis?

A

The upper bound of a function’s growth rate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What best describes the Ω (Omega) notation?

A

It represents the lower bound of a function’s growth rate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

When a function f(n) is said to be in o (little-o) notation with respect to g(n), it
means:

A

f(n) grows strictly slower than g(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What does the statement ‘f(n) = Θ(g(n))’ imply about f(n) and g(n)?

A

f(n) grows at the same rate as g(n)

f(n) and g(n) have equivalent upper and lower bounds

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

How does transitivity apply in the comparison of functions in asymptotic analysis?

A

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))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

In asymptotic analysis, what does the usage of limits indicate when comparing the
growth of functions?

A

A method to compare the relative growth rates of functions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What does it mean if an algorithm has a time complexity of Θ(n2)?

A

The algorithm’s running time is exactly proportional to the square of the input
size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

In the context of asymptotic notation, what does ‘tight bound’ mean?

A

The upper and lower bounds of the algorithm’s running time are equivalent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

How does the Ω (Omega) notation differ from the O (Big O) notation?

A

Ω denotes a lower bound, while O denotes an upper bound

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Consider two functions f(n) = n2 and g(n) = n3. What can be written about the two functions?

A

f(n) = O(g(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

For the functions f(n) = 100n + log n and g(n) = n, what is the relationship between
f(n) and g(n)?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Considering f(n) = n! (n factorial) and g(n) = 2^n, how do these functions compare?

A

g(n) = O(f(n))
f(n) = Ω(g(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

For f(n) = n^0.5 and g(n) = n^2, which statement is correct?

A

f(n) = O(g(n))
g(n) = Ω(f(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

If f(n) = 2^n and g(n) = n^10, how do f(n) and g(n) compare asymptotically?

A

g(n) = O(f(n))
f(n) = Ω(g(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What does the notation f(n) = o(g(n)) indicate about the functions f(n) and g(n)?

A

f(n) grows slower than g(n) and becomes insignificant as n approaches infinity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

If f(n) = o(n), what is true about this equation?

A

f(n) is dominated by n as n approaches infinity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is the primary difference between little o (o) and little omega (ω) notations?

A

o notation signifies a non-tight (strict) upper bound, while ω signifies a non-tight
(strict) lower bound

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

In the context of recurrences, what does ‘solving a recurrence relation’ typically
involve?

A

Finding a non-recursive expression that describes the relationship

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

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.

A

T(n) = T(n-1) + n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

The binary search algorithm is an example of which kind of problem-solving
approach?

A

Divide and conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What does the recurrence relation T(n) = 2T(n-1) + 1 with T(1) = 1 describe?

A

The time complexity of the towers of Hanoi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What represents the closed-form solution for T(n) = 2T(n-1) + 1,
where T(1) = 1?

A

T(n) = 2^n – 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

For the recurrence relation T(n) = 2T(n-1) + 1, what is the value of T(4)?

A

15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Considering the solution to the recurrence T(n) = 2T(n-1) + 1, T(1) = 1, how does
T(n) grow with respect to n?

A

Exponentially with 2^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Considering When analysing the solution to a recurrence, why might we consider
the limit as n approaches infinity (n → ∞)?

A

To understand the asymptotic behaviour

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

In solving recurrence relations, what principle is applied when dealing with a
geometric series?

A

Summation of terms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What is the main goal of utilizing data structures in computer programming?

A

Organizing and managing data effectively

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Identify a key feature of linear data structures.

A

Each element is preceded and followed by another element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What distinguishes direct access from sequential access in the context of data
structures?

A

Immediate accessibility to any data element

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Which advantage is associated with the use of arrays?

A

Direct access to individual elements is provided

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

The Sieve of Eratosthenes algorithm finds application in:

A

Identifying prime numbers within a specified range

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

Which data structure is exemplified by the Sieve of Eratosthenes program?

A

array

55
Q

The “if (Math.random() < 0.5)” condition in the Coin Flipping Simulation’s heads method is significant for:

A

Simulating the flip of a coin yielding heads

56
Q

what is the coin flipping simulation code?

A

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
Q

Which of the following best describes the principle of a stack?

A

Last-In-First-Out (LIFO)

58
Q

In a queue data structure, how are elements removed?

A

In the same order they were added

59
Q

What is the primary characteristic of Bubble Sort?

A

It repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order.

60
Q

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)

A

bubble sort

61
Q

In Insertion Sort, what is true about the initial state of the ‘sorted’ portion of the
array?

A

It contains only the first element of the array

62
Q

Which algorithm performs sorting by repeatedly choosing the minimum element
from the unsorted portion and moving it to the end of the sorted portion?

A

Selection Sort

63
Q

Which of the following is a disadvantage of using a linked list over an array?

A

direct access to elements

64
Q

Which of the following data structures would be most appropriate for
implementing a browser’s back button functionality?

A

stack

65
Q

Which data structure is ideally suited for managing tasks in a printer queue?

A

queue

66
Q

In a circular queue, what happens when the back pointer reaches the end of the
array?

A

It moves to the front of the array.

67
Q

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?

A

merge sort

68
Q

What Java code snippets correctly demonstrates the operation of
pushing an element onto a stack?

A

stack[++top] = element;

69
Q

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.

A

queue[++back] = element;

70
Q

Considering a bubble sort algorithm, what pseudocode snippet
accurately represents a single pass for sorting an array in ascending order?

A

for i from 0 to n-1:
if array[i] > array[i+1]:
swap(array[i], array[i+1])

71
Q

Which algorithmic paradigm does quicksort exemplify?

A

divide and conquer

72
Q

What is the worst-case time complexity of quicksort?

A

O(n^2)

73
Q

How does the choice of pivot affect the performance of quicksort?

A

Choosing the median of a constant number of values as pivot leads to the best
worst-case performance

74
Q

What is the average-case time complexity of Quicksort?

A

O(n log n)

75
Q

The depth of recursion for Quicksort in the best case is:

A

O(log n)

76
Q

Which case does the quicksort algorithm perform poorly in?

A

when the pivot is the smallest or largest element of the array

when the array is already sorted

77
Q

What is a key advantage of MergeSort over QuickSort in certain scenarios?

A

Better worst-case time complexity
Stable sorting

78
Q

What is NOT a characteristic of MergeSort?

A

In-place sorting algorithm

79
Q

RadixSort is particularly efficient when:

A

The range of the input is significantly less than the number of items

80
Q

How does RadixSort handle sorting?

A

By grouping elements based on their individual digits or letters

81
Q

Radix Sort’s time complexity depends on two key factors: the number of elements
(n) and what other factor?

A

The number of digits in the largest number (k)

82
Q

In the context of Radix Sort, what is the significance of using a stable sorting
algorithm as the subroutine for sorting digits?

A

It maintains the relative order of records with equal keys (digits).

83
Q

A tree is a data structure where:

A

Exactly one path exists between any two nodes

84
Q

In a binary tree

A

A node can have at most two children

85
Q

A leaf node in a tree is defined as a node that:

A

Has no children

86
Q

Pre-order traversal in a tree means:

A

Visiting the root before the subtrees

87
Q

An M-ary tree is a tree in which:

A

Each node can have at most M children

88
Q

The main advantage of a binary search tree (BST) is:

A

Efficient search, insert, and delete operations

89
Q

Which traversal is used to get nodes in non-decreasing order in a BST?

A

in-order

90
Q

What is not a direct application of trees?

A

Performing arithmetic operations

91
Q

What does it mean for a tree to be ‘balanced’?

A

The difference in height between any two subtrees is not more than one

92
Q

In post-order traversal, in what order are the nodes processed?

A

Left subtree, right subtree, root

93
Q

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.

A

b, c, e

94
Q

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

A

d

95
Q

What is the main advantage of balanced binary search trees?

A

O(log n) operation time for most actions

96
Q

What defines a balanced tree?

A

No leaf is ‘much farther’ from the root than any other

97
Q

Why isn’t a binary search tree always kept balanced?

A

Rebalancing can be costly

98
Q

Who introduced AVL trees?

A

Georgii Adelson-Velskii and Evgenii Landis

99
Q

How does the AVL tree determine the rotations needed for rebalancing after an
insertion?

A

By using the balance factor of the nodes from the insertion point up to the root

100
Q

Considering a perfectly balanced AVL tree, what is the maximum number of nodes
it can contain at a height of h?

A

2^(h+1) - 1

101
Q

What is a characteristic of AVL trees?

A

Height of subtrees differ by at most one

102
Q

What is the balance factor in AVL trees?

A

Difference between heights of left and right subtrees

103
Q

What rotations are used to maintain balance in AVL trees?

A

single rotation
double rotation

104
Q

When is a single-right rotation applied in AVL trees?

A

When a tree is left-heavy

105
Q

What is the balance factor of all nodes in a perfectly balanced AVL tree?

A

0

106
Q

Can AVL trees guarantee O(log n) search time?

A

Yes, due to their balanced nature

107
Q

What is the purpose of double rotations in AVL trees?

A

To correct imbalances that single rotations cannot

108
Q

How does an AVL tree ensure that operations remain efficient?

A

By maintaining balance through rotations

109
Q

In an AVL tree, after how many consecutive right insertions starting from an empty
tree will the first rebalancing occur?

A

After the third insertion, causing a right-right case.

110
Q

Which operation does not guarantee O(log n) time complexity in an AVL tree,
assuming arbitrary sequences of operations?

A

Level-order traversal

111
Q

What is the balance factor of a node that triggers a double rotation during AVL tree
rebalancing?

A

2
or
-2

112
Q

What is a characteristic feature of a max-heap?

A

No child has a value bigger than the value of its parent

113
Q

In a max-heap, where is the maximum element found?

A

at the root

114
Q

What operations are used to maintain the heap property in a binary heap?

A

sink and swim

115
Q

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?

A

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
Q

What is the result of performing a ‘sink’ operation in a complete tree in reverse
level order?

A

The heap property is restored by moving down elements that are out of place

117
Q

Which of the following best describes heapify operation?

A

Adjusting a binary tree to maintain the heap property

118
Q

What is the time complexity of building a heap from an arbitrary array of
elements?

A

O(n log n)

119
Q

How does HeapSort sort an array in place?

A

By constructing a heap and then performing a series of swap and sink operations

120
Q

What is the primary advantage of HeapSort compared to MergeSort?

A

It sorts in-place, using only a constant amount of extra space

121
Q

Why might job starvation occur in a priority queue implemented with a heap?

A

Without precautions, continuously arriving high-priority jobs may prevent low priority jobs from being processed

122
Q

describe a graph

A

A set of vertices connected by edges

123
Q

What does an undirected edge in a graph represent?

A

A bidirectional relationship between two nodes

124
Q

Which graph representation is most space-efficient for sparse graphs?

A

adjacency-list representation

125
Q

In the context of BFS, what does a ‘white’ node represent?

A

A node that has not been visited

126
Q

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?

A

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
Q

What is a characteristic of BFS?

A

It can be used to find the shortest path in unweighted graphs

128
Q

How does DFS differ from BFS in terms of exploration?

A

DFS explores as far as possible along a branch before backtracking

129
Q

What is a cycle in a graph?

A

A path that starts and ends at the same vertex

130
Q

What is true about directed graphs?

A

Edges have a direction from one vertex to another

131
Q

What is true about dense graphs?

A

They have a number of edges close to the maximal number of edges

132
Q

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.

A

c

133
Q

What does a complete graph mean?

A

A graph where each vertex is connected to every other vertex

I40(0/1/2) Computer Science Bsc (41 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions