Algorithm exam questions and answers

Algorithm exam questions and answers

Here are 25 algorithm exam questions along with their answers:

Question: What is an algorithm?

Answer: An algorithm is a step-by-step procedure or a set of rules for solving a specific problem or accomplishing a task.

Question: Define the time complexity of an algorithm.

Answer: Time complexity refers to the amount of time an algorithm takes to run, usually measured in terms of the number of operations performed.

Question: What is the difference between a stable and an unstable algorithm?

Answer: A stable algorithm maintains the relative order of elements with equal keys, while an unstable algorithm does not guarantee the same order.

Question: What is the difference between a breadth-first search (BFS) and a depth-first search (DFS)?

Answer: BFS explores all the vertices of a graph layer by layer, while DFS explores as far as possible along each branch before backtracking.

Question: Explain the concept of recursion in algorithms.

Answer: Recursion is a technique in which a function calls itself to solve a smaller subproblem of the original problem until a base case is reached.

Question: What is the Big-O notation used for in algorithm analysis?

Answer: Big-O notation is used to describe the upper bound or worst-case scenario of the time complexity of an algorithm.

Question: Define dynamic programming.

Answer: Dynamic programming is a technique used to solve complex problems by breaking them down into overlapping subproblems and storing the results of these subproblems for reuse.

Question: What is the purpose of memoization in dynamic programming?

Answer: Memoization is a technique used to store the results of expensive function calls and retrieve them later when the same inputs occur again, thus reducing redundant computations.

Question: What is the difference between a linked list and an array?

Answer: A linked list is a data structure where elements are connected through pointers, while an array is a fixed-size collection of elements stored in contiguous memory locations.

Question: Explain the concept of a greedy algorithm.

Answer: A greedy algorithm makes locally optimal choices at each step with the hope of finding a global optimum, without considering the overall future consequences.

Question: What is the significance of a hash table in algorithmic efficiency?

Answer: Hash tables provide constant-time average-case performance for basic operations like insertion, deletion, and search, making them efficient for storing and retrieving data.

Question: What is the difference between a binary tree and a binary search tree?

Answer: A binary tree is a tree-like data structure where each node can have at most two children, while a binary search tree maintains a specific order of the nodes such that the left child is smaller and the right child is larger.

Question: Explain the concept of backtracking in algorithms.

Answer: Backtracking is a systematic method to find all possible solutions to a problem by incrementally building candidates and abandoning a candidate as soon as it is determined to be infeasible.

Question: What is the difference between a stack and a queue?

Answer: A stack is a Last-In-First-Out (LIFO) data structure, while a queue is a First-In-First-Out (FIFO) data structure.

Question: Define the term "sorting algorithm."

Answer: A sorting algorithm is an algorithm that arranges a collection of elements into a specific order, typically non-decreasing or non-increasing.

Question: What is the time complexity of the Quicksort algorithm in the average case?

Answer: The average case time complexity of Quicksort is O(n log n), where n is the number of elements to be sorted.

Question: What is the purpose of using a priority queue in algorithms?

Answer: A priority queue is a data structure that stores elements along with their associated priorities. It allows insertion of elements in any order and retrieves the element with the highest priority first.

Question: Explain the concept of graph traversal.

Answer: Graph traversal refers to the process of visiting or exploring all the vertices or nodes of a graph in a systematic manner. It can be done using algorithms like breadth-first search (BFS) or depth-first search (DFS).

Question: What is the difference between a linear search and a binary search algorithm?

Answer: A linear search algorithm sequentially checks each element in a list until a match is found or the end of the list is reached. In contrast, a binary search algorithm repeatedly divides the search space in half by comparing the target value with the middle element.

Question: What is the significance of Dijkstra's algorithm?

Answer: Dijkstra's algorithm is used to find the shortest path between a source node and all other nodes in a weighted graph. It guarantees the shortest path as long as the edge weights are non-negative.

Question: Explain the concept of memoization in dynamic programming.

Answer: Memoization is a technique that involves storing the results of expensive function calls and retrieving them later when the same inputs occur again. It helps avoid redundant computations and can significantly improve the efficiency of recursive algorithms.

Question: What is the purpose of the Bellman-Ford algorithm?

Answer: The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted directed graph, even in the presence of negative edge weights.

Question: Define the term "graph representation."

Answer: Graph representation refers to the way in which a graph is stored or represented in a computer's memory. Common representations include adjacency matrix and adjacency list.

Question: What is the difference between an undirected graph and a directed graph?

Answer: In an undirected graph, the edges have no specific direction and can be traversed in both directions. In a directed graph, the edges have a specific direction and can only be traversed in that direction.

Question: Explain the concept of memoization in dynamic programming.

Answer: Memoization is a technique that involves storing the results of expensive function calls and retrieving them later when the same inputs occur again. It helps avoid redundant computations and can significantly improve the efficiency of recursive algorithms.