Fundamentals of Algorithms and problem-solving MCQs

Topological sort can be used to find the longest path in a directed acyclic graph (DAG).

"Brute force" in problem-solving means trying all possible solutions without optimization.

"Trial and error" as a problem-solving strategy involves randomly trying different solutions until one succeeds.

"Divide and conquer" is a problem-solving technique that breaks a problem into smaller subproblems and solves them independently.

A heuristic is a rule of thumb or a practical approach used to find a solution in problem-solving.

"Trial division" is a technique in number theory and prime factorization used to verify if a number is prime by dividing it by smaller primes.

The primary purpose of "backtracking" in problem-solving is to explore all possible solutions systematically, typically in a recursive manner.

An algorithm is a sequence of steps or instructions designed to solve a specific problem or perform a task.

The primary goal of algorithm analysis is to compare algorithms and evaluate their efficiency.

A good algorithm is characterized by clarity, simplicity, efficiency, and correctness. Complex data structures may be used if necessary, but simplicity is preferred.

Pseudocode is used to provide a step-by-step implementation guide for an algorithm, making it easier to understand and develop.

The "divide and conquer" algorithm design technique involves breaking a problem into smaller subproblems and solving each subproblem recursively.

Time complexity is the analysis of an algorithm's efficiency in terms of input size.

The Big O notation is used to express the upper bound of an algorithm's time complexity.

O(1) represents constant time complexity, which is the most efficient algorithm in terms of time.

Space complexity is the amount of memory used by the algorithm.

Optimization in the context of algorithms refers to the process of improving an algorithm's efficiency.

Binary search works by repeatedly dividing the search range in half until the target element is found.

Merge sort has an average time complexity of O(n log n) and is efficient for large datasets.

Quicksort has an average time complexity of O(n log n), which is more efficient than the average case time complexity of bubble sort and insertion sort.

Selection sort repeatedly selects the smallest element from the unsorted part and places it at the beginning of the sorted part.

The worst-case time complexity of the bubble sort algorithm is O(n^2).

A graph represents a collection of nodes connected by edges, where edges can have directions.

In a binary tree, each node can have at most two children: a left child and a right child.

The root node in a tree data structure is the topmost node from which all other nodes descend.

Preorder traversal starts from the root node and explores as far as possible along each branch before backtracking.

A common application of breadth-first search (BFS) is finding the shortest path between two nodes in a graph.

Dynamic programming is commonly used for solving problems by breaking them into smaller subproblems and caching their solutions to avoid redundant computation.

Memoization in dynamic programming involves caching and reusing previously computed results to avoid redundant calculations.

Tabulation is a dynamic programming technique that typically uses a table to store and retrieve solutions to subproblems.

Optimal substructure is the property that the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.

The primary advantage of dynamic programming is that it is often faster than brute-force methods because it avoids redundant computations.

A greedy algorithm makes a series of choices, each being the best decision at the moment, with the hope of finding a globally optimal solution.

The greedy choice property states that a locally optimal choice in a greedy algorithm leads to a globally optimal solution.

The coin change algorithm is used to find the minimum number of coins needed to make change for a given amount of money.

The primary drawback of greedy algorithms is that they can sometimes lead to suboptimal solutions because they make locally optimal choices at each step.

In a directed graph, a cycle is a path that visits the same node twice or more, starting and ending at the same node.

Dijkstra's algorithm is commonly used to find the shortest path between nodes in a weighted graph.

A topological sort of a directed acyclic graph (DAG) is a linear ordering of nodes such that for every directed edge (u, v), node u comes before node v.

A spanning tree of a graph is a tree that includes all nodes of the graph.

The "bottom-up" or "tabulation" approach in dynamic programming starts with the smallest subproblems and solves them first, building up to the larger problem.

The "optimal substructure" property in dynamic programming states that the optimal solution can be constructed from optimal solutions of subproblems.

A memoization table in dynamic programming is used to cache and retrieve previously computed results of subproblems to avoid redundant calculations.

The "overlap" property in dynamic programming refers to the property that two or more subproblems share a common solution, leading to the need for memoization.

In dynamic programming, pruning is the process of removing unnecessary branches from a search to reduce computational effort.

The tabulation technique in dynamic programming uses a bottom-up approach and fills a table iteratively to solve problems.

A weighted graph is a graph in which each edge has a numerical weight or cost associated with it.

Kruskal's algorithm is used to find the minimum spanning tree of a weighted, connected graph.

A strongly connected component in a directed graph is a component in which there is a directed path from any node to any other node within the component.

A cycle detection algorithm is used to detect loops or cycles in a graph.