Algorithms and programs Flashcards
(128 cards)
1
Q
What is the purpose of sorting data?
A
To organize data in a specific order to improve readability or to make searching more efficient.
2
Q
What does the bubble sort algorithm do?
A
It repeatedly compares and swaps adjacent items if they are in the wrong order until the list is sorted.
3
Q
Why is it called ““bubble sort””?
A
Because higher values “bubble up” to the top of the list, similar to bubbles in a fizzy drink.
4
Q
What is a ““pass”” in bubble sort?
A
A single complete iteration through the list.
5
Q
What is a ““comparison”” in bubble sort?
A
Checking whether two adjacent items are in the correct order.
6
Q
What types of data can bubble sort work on?
A
Numbers, characters, and strings.
7
Q
What is the best-case scenario for bubble sort?
A
When the list is already sorted — requires only one pass and n-1 comparisons.
8
Q
What is the worst-case scenario for bubble sort?
A
When the list is in reverse order — maximum number of comparisons and swaps.
9
Q
What is the time complexity of bubble sort in the worst case?
A
O(n²)
10
Q
What is the best-case time complexity of bubble sort when using the best bubble sort algorithm?
A
O(n)
11
Q
What is the average-case time complexity of bubble sort?
A
O(n²)
12
Q
What is the space complexity of bubble sort?
A
O(1), because it only uses a temporary variable for swapping.
13
Q
Why is bubble sort considered inefficient for large datasets?
A
Because of its O(n²) time complexity in average and worst cases.
14
Q
What does the insertion sort algorithm do?
A
It builds a sorted sublist one item at a time by inserting each item into its correct position.
15
Q
What is the initial state of the sorted sublist in insertion sort?
A
It contains just the first item of the list.
16
Q
What is a ‘pass’ in insertion sort?
A
A single operation of inserting one unsorted item into the correct position in the sorted sublist.
17
Q
What is a ‘comparison’ in insertion sort?
A
Comparing an unsorted item with items in the sorted sublist to find its correct position.
18
Q
Why is insertion sort usually faster than bubble sort?
A
Because it often performs fewer comparisons per pass.
19
Q
What is the best-case scenario for insertion sort?
A
When the list is already sorted — only one comparison per pass is needed.
20
Q
What is the worst-case scenario for insertion sort?
A
When the list is in reverse order — maximum comparisons and shifts per pass are needed.
21
Q
What is the time complexity of insertion sort in the worst case?
A
O(n²)
22
Q
What is the best-case time complexity of insertion sort?
A
O(n), when the list is already sorted.
23
Q
What is the average-case time complexity of insertion sort?
A
O(n²)
24
Q
What is the space complexity of insertion sort?
A
O(1), as sorting is done in-place using only one extra variable.
25
Why does insertion sort need to move other items during sorting?
To create space for inserting the current item into the correct position.
26
What approach does the quick sort algorithm use?
It uses the divide and conquer approach.
27
What is the key value used in each partition of quick sort?
The pivot value.
28
What does the pivot value do in quick sort?
It partitions the list into items less than and greater than itself.
29
What is a partition in quick sort?
An unsorted section of the list that is being sorted around a pivot.
30
What do the low and high markers do in quick sort?
They help rearrange items around the pivot by identifying values to be swapped.
31
How is the list rearranged in quick sort?
Values less than the pivot are placed before it, and values greater are placed after it.
32
When does the base case occur in quick sort?
When a partition has only one item (start >= end).
33
What is the role of recursion in quick sort?
It continues sorting smaller partitions until the base case is reached.
34
What determines the performance of quick sort?
The choice of the pivot value.
35
Why is choosing the median as a pivot ideal?
It evenly splits the list into two balanced partitions, improving performance.
36
Why isn’t the median value usually chosen as the pivot?
Because finding the median would require scanning the entire list, which is inefficient.
37
What is a common simple choice for the pivot?
The first item in the partition.
38
Why might choosing the first item as a pivot be a bad idea?
If the list is already sorted or nearly sorted, it can lead to unbalanced partitions.
39
What is an alternative to the first-item pivot strategy?
Choosing the last item or a random item as the pivot.
40
What is the time complexity of quick sort in the best case?
O(n log n)
41
What is the time complexity of quick sort in the average case?
O(n log n)
42
What is the time complexity of quick sort in the worst case?
O(n²)
43
When does quick sort perform at its worst?
When the pivot always results in one empty and one full partition (e.g., sorted list with first/last pivot).
44
What is the space complexity of quick sort?
O(log n), due to the recursive call stack.
45
Is quick sort an in-place sorting algorithm?
Yes, it sorts the list in its original memory space.
46
What additional memory does quick sort use?
Memory for the pivot value, low and high markers, and a temporary variable for swapping.
47
Why is quick sort preferred for large datasets?
Because it combines good performance and low memory requirements.
48
What are two main factors in choosing a sorting algorithm?
Time efficiency and memory usage.
49
How do you measure the time efficiency of a sorting algorithm?
By the number of passes and comparisons needed to sort the list.
50
Do all sorting algorithms sort only in ascending order?
No, they can sort in ascending or descending order.
51
Which sorting algorithm usually requires fewer comparisons per pass: insertion sort or bubble sort?
Insertion sort.
52
Why is insertion sort generally faster than bubble sort?
Because it performs fewer comparisons per pass.
53
How much extra memory do insertion sort and bubble sort use?
Very little – only enough to temporarily store single values.
54
Which sorting algorithm is faster for large or unordered lists: merge sort or bubble sort?
Merge sort.
55
Which sorting algorithm is faster for small or nearly sorted lists: merge sort or bubble sort?
Bubble sort.
56
Why does merge sort require more memory than bubble sort?
Because it creates new lists during splitting and merging.
57
What makes merge sort a good choice for big data applications?
It can be parallelised across multiple processors.
58
What is a major downside of merge sort?
It has poor space complexity due to extra memory use.
59
Why is quick sort often chosen over merge sort?
It has good average performance and better space efficiency.
60
Does quick sort use less memory than merge sort?
Yes, but more than bubble or insertion sort.
61
Why might bubble sort be a good choice for beginners?
It has fewer lines of code and is easier to implement.
62
Which algorithm performs best on a mostly sorted list: bubble or insertion sort?
Insertion sort.
63
Why isn't there a 'one size fits all' sorting algorithm?
Because the best choice depends on the data and the task requirements.
64
What is the space complexity comparison between bubble/insertion sort and quick/merge sort?
Bubble and insertion sort use less space than quick or merge sort.
65
What makes merge sort ideal in terms of time complexity?
It has the best overall time complexity (O(n log n)).
66
What is a disadvantage of quick sort in terms of space?
It uses more memory than bubble or insertion sort due to recursion.
67
Why should the structure of the data be considered when choosing a sort algorithm?
Because certain algorithms perform better or worse depending on how ordered the data is.
68
What is the purpose of search algorithms in computing?
To find a specific item in a list or dataset, such as locating a file or matching keywords in a search engine.
69
What is a linear search?
An algorithm that checks each item in an unordered list one by one until the target is found or the list ends.
70
What type of list is required for binary search to work?
An ordered list (sorted in ascending or descending order).
71
How does a binary search work?
It repeatedly checks the middle item of the current list segment and eliminates half the list until the target is found or the segment is empty.
72
What is the time complexity of a linear search in the worst case?
O(n)
73
What is the time complexity of a binary search in the worst case?
O(log n)
74
What is the best-case time complexity of a linear search?
O(1), when the item is found at the beginning.
75
What is the best-case time complexity of a binary search?
O(1), when the item is found at the first comparison.
76
What is the average-case time complexity of a linear search?
O(n)
77
What formula is used to find the midpoint in binary search?
midpoint = (first + last) DIV 2
78
In binary search, what happens if the item at midpoint is less than the search item?
Search continues in the right half of the list.
79
In binary search, what happens if the item at midpoint is greater than the search item?
Search continues in the left half of the list.
80
What is a binary search tree?
A data structure that allows efficient searching, inserting, and deleting of data in logarithmic time.
81
What is a hash table?
A data structure that uses hash functions to provide fast data retrieval by directly accessing the memory location.
82
What is a disadvantage of binary search?
It only works on ordered lists and maintaining order can be computationally expensive.
83
Why is linear search used with unordered data?
Because it's the only methodical way to search without ordering.
84
What are static arrays?
Arrays with a fixed size
85
What advantage does binary search have over linear search?
It significantly reduces the number of items to check by halving the list each time.
86
What type of problems does Dijkstra's algorithm solve?
It solves shortest path problems in weighted graphs, finding the minimum cost path between nodes.
87
Who created Dijkstra’s algorithm and why?
Edsger Dijkstra created it in 1956 to calculate the shortest route from Rotterdam to Groningen.
88
What are the components of a weighted graph used in Dijkstra’s algorithm?
Nodes (vertices) and edges (arcs) with associated weights (costs).
89
What is the main goal of Dijkstra's algorithm?
To find the shortest paths from a start node to all other nodes in the graph.
90
How is the cost of a path calculated in Dijkstra’s algorithm?
By summing the weights of all the edges that make up the path.
91
What key data does Dijkstra’s algorithm output for each node?
Node label, cost of the shortest path, and the label of the previous node.
92
What are the main steps in Dijkstra’s algorithm (in structured English)?
Initialize visited/unvisited lists, set start node distance to 0, update neighbor costs, and repeat until all nodes are visited.
93
What data structure is commonly used to improve the efficiency of Dijkstra’s algorithm?
A priority queue, which helps retrieve the node with the lowest cost efficiently.
94
How is a graph typically stored for use in Dijkstra’s algorithm?
As an adjacency matrix or an adjacency list.
95
Why might Dijkstra’s algorithm be inefficient for finding a path to a single target node?
It continues processing all nodes until all paths are found, not just to the target.
96
Which algorithm is generally more efficient for finding a path to a single target node?
The A* (A-star) algorithm.
97
What must happen after the dijkstra algorithm finishes to determine the shortest path from start to any node?
Backtrack to reconstruct the path.
98
What problem does the A* algorithm aim to solve more efficiently than Dijkstra's algorithm?
It aims to find the shortest path between a start node and a target node faster by using a heuristic to guide the search.
99
What is the key difference between Dijkstra’s algorithm and the A* algorithm?
Dijkstra's finds the shortest path to all nodes, while A* focuses only on the shortest path to a target node using a heuristic.
100
What is a heuristic in the context of A*?
A heuristic is an estimate of the cost to reach the target from a given node, helping the algorithm choose more promising paths.
101
What is the role of the heuristic function h(n) in A*?
It estimates the cost from node n to the target node.
102
How does A* combine actual and estimated costs when choosing the next node?
It uses f(n) = g(n) + h(n), where g(n) is the cost from the start to n, and h(n) is the estimated cost from n to the target.
103
What requirement must the heuristic function meet to ensure optimality in A*?
It must never overestimate the cost to reach the target (i.e., it must be admissible).
104
Give examples of heuristic functions used in A*.
Euclidean distance, Manhattan distance, Great-circle distance.
105
Why is using a heuristic in A* potentially faster than Dijkstra's algorithm?
It reduces unnecessary exploration by prioritizing paths that are more likely to lead to the target.
106
What data structure is typically used in A* to efficiently manage unvisited nodes?
A priority queue, which always retrieves the node with the lowest f-score next.
107
What does the g-score represent in the A* algorithm?
The exact cost from the start node to the current node.
108
What does the f-score represent in the A* algorithm?
The total estimated cost of the cheapest solution through the current node: f(n) = g(n) + h(n).
109
How are graph edges and costs typically stored for A*?
As an adjacency matrix or adjacency list.
110
Why might pre-calculating h(n) be beneficial?
It avoids repeated computation of heuristic values, improving efficiency.
111
Why is choosing a good heuristic critical in A*?
A poor heuristic can negate performance gains or even make the algorithm incorrect if it overestimates costs.
112
What happens when A* reaches the target node?
The algorithm stops, and the shortest path is reconstructed using the previous nodes.
113
In what scenarios is A* preferred over Dijkstra’s algorithm?
When only the shortest path to a specific target is needed, especially in large or complex graphs.
114
What happens if the heuristic overestimates the cost in A*?
The algorithm may fail to find the shortest path, compromising its optimality.
115
What is graph traversal?
The process of systematically visiting each node in a graph.
116
Why is graph traversal tricky?
Because graphs can have cycles (loops), making it easy to revisit nodes without proper tracking.
117
What are the three states for each node in graph traversal?
Unvisited, Discovered, Visited
118
What is the goal of a graph traversal using BFS (Breadth-First Search)?
To find the path with the least number of nodes in an unweighted graph.
119
How does BFS graph traversal work?
It starts at the start node, explores all neighbors first, then their neighbors, like layers or waves.
120
What does BFS graph traversal ensure in terms of node visits?
It ensures all nodes at the current depth level are visited before moving deeper.
121
What is the main use of DFS graph traversal (Depth-First Search)?
To determine whether there is a path between two nodes in a graph.
122
What data structure does DFS use?
A stack
123
How does DFS work?
It explores as far as possible along each branch before backtracking.
124
What is the key difference between BFS and DFS?
BFS explores neighbors level by level; DFS explores deeply along one path before backtracking.
125
What structure is commonly used to represent a graph in code?
A dictionary with node keys and list of neighbors as values.
126
In BFS/DFS, what is the purpose of the discovered list?
To keep track of nodes that have been seen to avoid revisiting.
127
How does BFS prevent infinite loops in graphs with cycles?
By marking discovered nodes and avoiding reprocessing them.
128
What kind of path does BFS find in an unweighted graph?
The path with the fewest number of nodes between start and target.
