All relevance

Question 1

*Asymptotic Notation

Answer 1

Mathematical notation used to describe the limiting behavior of a function; includes Big O, Big Theta (Θ), and Big Omega (Ω).

Question 2

*Big O Notation

Answer 2

Describes the upper bound of an algorithm’s running time, used for worst-case analysis.

Question 3

*Big Omega Notation

Answer 3

Describes the lower bound of an algorithm’s running time, used for best-case analysis.

Question 4

*Big Theta Notation

Answer 4

Describes a tight bound on the running time, i.e., both upper and lower bounds.

Question 5

*Time Complexity

Answer 5

Measure of the amount of time an algorithm takes to complete as a function of the length of the input.

Question 6

*Space Complexity

Answer 6

Amount of memory space required by an algorithm as a function of input size.

Question 7

*Greedy Algorithm

Answer 7

Algorithm that makes locally optimal choices at each step with the hope of finding a global optimum.

Question 8

*Divide and Conquer

Answer 8

Design paradigm that divides a problem into subproblems, solves them recursively, and combines their solutions.

Question 9

*Dynamic Programming

Answer 9

Solving complex problems by breaking them down into simpler subproblems and storing the results.

Question 10

*Backtracking

Answer 10

Algorithmic technique for solving recursive problems by trying to build a solution incrementally and removing solutions that fail.

Question 11

Heap

Answer 11

A special tree-based data structure that satisfies the heap property. Used for priority queues.

Question 12

*Priority Queue

Answer 12

Abstract data type where each element has a priority; elements with higher priorities are dequeued before lower ones.

Question 13

Disjoint Set

Answer 13

Data structure that keeps track of a partition of a set into disjoint subsets. Often used in Kruskal’s algorithm.

Question 14

Union-Find

Answer 14

A disjoint-set data structure with operations to find which set an element is in and to unite two sets.

Question 15

*Dijkstra’s Algorithm

Answer 15

Greedy algorithm that finds the shortest paths from a source vertex to all other vertices in a weighted graph.

Question 16

*Bellman-Ford Algorithm

Answer 16

Algorithm that computes shortest paths from a source vertex to all vertices in a weighted digraph, handles negative weights.

Question 17

*Floyd-Warshall Algorithm

Answer 17

Dynamic programming algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.

Question 18

*Kruskal’s Algorithm

Answer 18

Greedy algorithm for finding a minimum spanning tree in a graph.

Question 19

*Prim’s Algorithm

Answer 19

Greedy algorithm that builds the minimum spanning tree by adding the cheapest edge from the tree to a vertex not yet in the tree.

Question 20

*Topological Sort

Answer 20

Linear ordering of vertices in a DAG such that for every directed edge uv, vertex u comes before v.

Question 21

*P vs NP

Answer 21

P is the class of problems solvable in polynomial time. NP is the class for which solutions can be verified in polynomial time.

Question 22

*NP-Complete

Answer 22

Problems that are both in NP and as hard as any problem in NP. If any NP-complete problem is in P, then P = NP.

Question 23

*NP-Hard

Answer 23

At least as hard as the hardest problems in NP; not necessarily in NP (no requirement of polynomial-time verifiability).

Question 24

*Reduction

Answer 24

Transforming one problem into another to prove hardness.

Question 25

Cook-Levin Theorem

Answer 25

Establishes that the Boolean satisfiability problem (SAT) is NP-complete.

Question 26

*Polynomial Time

Answer 26

Class of problems that can be solved in time O(n^k) for some constant k.

Question 27

*Exponential Time

Answer 27

Problems that require time O(2^n) or more.

Question 28

Logarithmic Time

Answer 28

Problems solvable in O(log n) time, typically through divide-and-conquer strategies.

Question 29

*Greedy vs Dynamic Programming

Answer 29

Greedy chooses locally optimal solutions; DP solves all subproblems and combines solutions.

Question 30

*Divide & Conquer vs Dynamic Programming

Answer 30

Both divide the problem, but DP stores subproblem solutions to avoid recomputation.

Question 31

*P ⊆ NP

Answer 31

Every problem solvable in polynomial time can have its solution verified in polynomial time.

Question 32

*NP-Complete ⊆ NP-Hard

Answer 32

All NP-Complete problems are NP-Hard, but not all NP-Hard problems are NP-Complete.

Question 33

*Dijkstra vs Bellman-Ford

Answer 33

Dijkstra is faster but can't handle negative weights; Bellman-Ford can handle negative weights but is slower.

Question 34

Why is Dijkstra’s algorithm faster than Bellman-Ford?

Answer 34

Dijkstra’s uses a greedy approach with a priority queue, achieving O((V + E) log V), while Bellman-Ford does not use this structure and runs in O(VE).

Question 35

When would you use Bellman-Ford over Dijkstra?

Answer 35

When the graph contains negative weight edges; Dijkstra’s algorithm cannot handle those correctly.

Question 36

How does dynamic programming differ from divide and conquer?

Answer 36

Both divide problems into subproblems, but dynamic programming stores results to avoid recomputation, while divide and conquer recomputes them.

Question 37

What makes a problem NP-Complete?

Answer 37

It must be in NP and as hard as any problem in NP, meaning any NP problem can be reduced to it in polynomial time.

Question 38

Why are greedy algorithms not always optimal?

Answer 38

They make locally optimal choices without considering the global structure, which can lead to suboptimal solutions in complex problems.

Question 39

How are Kruskal’s and Prim’s algorithms different in building MSTs?

Answer 39

Kruskal’s grows a forest and adds the smallest edge between any two trees, while Prim’s grows a single tree by adding the smallest edge from the tree.

Question 40

How does topological sort relate to DAGs?

Answer 40

Topological sort is only defined for Directed Acyclic Graphs (DAGs), providing a linear ordering respecting edge directions.

Question 41

What is the significance of P ⊆ NP?

Answer 41

Every problem that can be solved in polynomial time can also have its solution verified in polynomial time.

Question 42

Why is NP-Hard not necessarily in NP?

Answer 42

NP-Hard problems might not have solutions that can be verified in polynomial time or even be decision problems.

Question 43

How does the Union-Find structure optimize Kruskal’s algorithm?

Answer 43

It efficiently tracks disjoint sets to avoid cycles when adding edges, using union by rank and path compression.