MIT 6.006 - Introduction to Algorithms Flashcards

Question 1

What is an Algorithm?

Accepted Answer

A well-defined computational procedure that takes some value(s) as input and produces some value(s) as output. It's a sequence of unambiguous instructions for solving a problem.

Question 2

What is Time Complexity?

Accepted Answer

A measure of the amount of time an algorithm takes to run as a function of the length of its input. It's typically expressed using asymptotic notation (e.g., Big-O) and counts elementary operations.

Question 3

What is Space Complexity?

Accepted Answer

A measure of the amount of memory an algorithm uses as a function of the length of its input. It includes both auxiliary space (temporary space used by the algorithm) and the space used for input storage.

Question 4

Explain Big-O Notation ($\mathcal{O}$).

Accepted Answer

$\mathcal{O}(g(n))$ represents the **upper bound** of an algorithm's running time. A function $f(n)$ is in $\mathcal{O}(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$. It describes the worst-case or maximum growth rate.

Question 5

Explain Omega Notation ($\Omega$).

Accepted Answer

$\Omega(g(n))$ represents the **lower bound** of an algorithm's running time. A function $f(n)$ is in $\Omega(g(n))$ if there exist positive constants $c$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$. It describes the best-case or minimum growth rate.

Question 6

Explain Theta Notation ($\Theta$).

Accepted Answer

$\Theta(g(n))$ represents the **tight bound** of an algorithm's running time. A function $f(n)$ is in $\Theta(g(n))$ if it is both an upper bound ($\mathcal{O}$) and a lower bound ($\Omega$). Formally, there exist positive constants $c_1, c_2,$ and $n_0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$. It describes the average-case growth rate.

Question 7

What is Amortized Analysis?

Accepted Answer

A method for analyzing the time complexity of a sequence of operations, where the average cost of an operation is considered over a worst-case sequence of operations. It often applies to data structures like dynamic arrays (e.g., `list.append()` in Python), where occasional expensive operations are offset by many cheap ones.

Question 8

Describe the Divide and Conquer algorithmic paradigm.

Accepted Answer

A problem-solving strategy that involves three steps:
1.  **Divide**: Break the problem into smaller subproblems of the same type.
2.  **Conquer**: Recursively solve these subproblems. If subproblems are small enough, solve them directly.
3.  **Combine**: Combine the solutions to the subproblems to get the solution to the original problem.

Question 9

Explain Mergesort and its complexity.

Accepted Answer

A stable, comparison-based sorting algorithm that follows the Divide and Conquer paradigm. It divides the array into halves, recursively sorts them, and then merges the two sorted halves.
*   Time Complexity: $\Theta(n \log n)$ in all cases (best, average, worst).
*   Space Complexity: $\Theta(n)$ due to the temporary array used for merging.

Question 10

Explain Quicksort and its complexity.

Accepted Answer

An in-place, comparison-based sorting algorithm that uses Divide and Conquer. It picks an element as a pivot, partitions the array around the pivot (elements smaller than pivot go left, larger go right), and recursively sorts the two partitions.
*   Average Time Complexity: $\Theta(n \log n)$.
*   Worst-case Time Complexity: $\mathcal{O}(n^2)$ (occurs with poor pivot choices, e.g., already sorted array).
*   Space Complexity: $\mathcal{O}(\log n)$ on average (for recursion stack), $\mathcal{O}(n)$ in worst-case.

Question 11

What is the Master Theorem used for?

Accepted Answer

The Master Theorem provides a "cookbook" method for solving recurrence relations of the form $T(n) = aT(n/b) + f(n)$, where $a \ge 1$, $b > 1$ are constants, and $f(n)$ is an asymptotically positive function. It helps determine the time complexity of many Divide and Conquer algorithms.

Question 12

What is Dynamic Programming (DP) and its key characteristics?

Accepted Answer

An optimization technique for solving complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid recomputing them. Key characteristics:
1.  **Optimal Substructure**: An optimal solution to the problem contains optimal solutions to its subproblems.
2.  **Overlapping Subproblems**: The same subproblems are encountered multiple times.

Question 13

How does Dynamic Programming improve computing the Fibonacci sequence?

Accepted Answer

A naive recursive approach for $F(n)$ recomputes $F(n-1)$ and $F(n-2)$ multiple times. DP (either memoization or tabulation) stores previously computed Fibonacci numbers (e.g., $F(0), F(1), \dots, F(n-1)$) in an array or hash map, allowing $F(n)$ to be computed in $\mathcal{O}(1)$ time after its subproblems are solved. This reduces time complexity from exponential to $\mathcal{O}(n)$.

Question 14

Explain the Longest Common Subsequence (LCS) problem as a DP application.

Accepted Answer

Given two sequences, find the longest subsequence common to both. A subsequence doesn't require consecutive elements. It exhibits optimal substructure and overlapping subproblems, making it suitable for DP. A 2D table `dp[i][j]` stores the length of LCS for prefixes of length `i` and `j` of the two sequences, with a time complexity of $\mathcal{O}(mn)$ for sequences of length $m$ and $n$.

Question 15

Describe Heaps (Min-Heap/Max-Heap) and their basic operations' complexity.

Accepted Answer

A heap is a complete binary tree that satisfies the heap property:
*   **Min-Heap**: Parent node value is less than or equal to its children's values.
*   **Max-Heap**: Parent node value is greater than or equal to its children's values.
*   Operations (`insert`, `extract-min/max`, `decrease/increase-key`): All typically take $\mathcal{O}(\log n)$ time. `build-heap` takes $\mathcal{O}(n)$.

Question 16

Explain Hash Tables, their operations, and collision resolution.

Accepted Answer

A data structure that maps keys to values using a hash function to compute an index into an array of buckets or slots.
*   Operations (`insert`, `search`, `delete`): Average-case $\mathcal{O}(1)$. Worst-case $\mathcal{O}(n)$ if all keys hash to the same bucket.
*   Collision Resolution:
    *   **Chaining**: Each bucket stores a linked list of elements that hash to it.
    *   **Open Addressing**: If a slot is occupied, probe for another slot (e.g., linear probing, quadratic probing, double hashing).

Question 17

What is the purpose of Balanced Binary Search Trees (BBSTs) and their typical operation complexity?

Accepted Answer

BBSTs (e.g., AVL trees, Red-Black trees) are BSTs that automatically maintain their height to be logarithmic, preventing worst-case $\mathcal{O}(n)$ performance for operations like `search`, `insert`, and `delete` that can occur in skewed standard BSTs.
*   Operations (`search`, `insert`, `delete`, `min`, `max`): All take $\mathcal{O}(\log n)$ time.

Question 18

Compare Adjacency List and Adjacency Matrix for graph representation.

Accepted Answer

*   **Adjacency List**: An array of lists where `adj[i]` contains a list of all vertices adjacent to vertex `i`.
    *   Space: $\mathcal{O}(V+E)$ (where $V$ is vertices, $E$ is edges).
    *   Good for sparse graphs.
    *   Finding all neighbors of a vertex is efficient ($\mathcal{O}(	ext{degree})$).
*   **Adjacency Matrix**: A $V 	imes V$ matrix `adj[i][j]` is 1 if an edge exists from `i` to `j`, 0 otherwise (or weight for weighted graphs).
    *   Space: $\mathcal{O}(V^2)$.
    *   Good for dense graphs.
    *   Checking if an edge exists between two vertices is $\mathcal{O}(1)$.

Question 19

Explain Breadth-First Search (BFS) and its complexity.

Accepted Answer

A graph traversal algorithm that explores all the neighbor nodes at the present depth level before moving on to nodes at the next depth level. It uses a queue.
*   Time Complexity: $\mathcal{O}(V+E)$ for adjacency list, $\mathcal{O}(V^2)$ for adjacency matrix.
*   Space Complexity: $\mathcal{O}(V)$ for the queue.
*   Use Cases: Finding the shortest path in an unweighted graph, network broadcasting.

Question 20

Explain Depth-First Search (DFS) and its complexity.

Accepted Answer

A graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion).
*   Time Complexity: $\mathcal{O}(V+E)$ for adjacency list, $\mathcal{O}(V^2)$ for adjacency matrix.
*   Space Complexity: $\mathcal{O}(V)$ for the recursion stack.
*   Use Cases: Topological sorting, finding connected components, cycle detection.

Question 21

Explain Dijkstra's Algorithm, its complexity, and limitations.

Accepted Answer

An algorithm for finding the shortest paths between nodes in a graph, from a single source node to all other nodes, where edge weights are non-negative. It uses a priority queue.
*   Time Complexity: $\mathcal{O}(E \log V)$ with a binary heap, or $\mathcal{O}(E + V \log V)$ with a Fibonacci heap.
*   Limitations: Does not work correctly with negative edge weights.

Question 22

Explain Bellman-Ford Algorithm, its complexity, and advantages over Dijkstra's.

Accepted Answer

An algorithm that computes shortest paths from a single source vertex to all other vertices in a weighted digraph. It can handle graphs with negative edge weights and detect negative cycles.
*   Time Complexity: $\mathcal{O}(VE)$.
*   Advantages: Can handle negative edge weights and detect negative cycles, unlike Dijkstra's.

Question 23

What is a Minimum Spanning Tree (MST)?

Accepted Answer

For a connected, undirected, weighted graph, an MST is a subgraph that is a tree, connects all the vertices together, and has the minimum possible total edge weight. Common algorithms to find an MST include Prim's Algorithm and Kruskal's Algorithm, both typically running in $\mathcal{O}(E \log V)$ or $\mathcal{O}(E + V \log V)$ time.

Question 24

Briefly explain the P vs NP problem.

Accepted Answer

A major unsolved problem in theoretical computer science.
*   **P (Polynomial time)**: The class of decision problems solvable by a deterministic Turing machine in polynomial time.
*   **NP (Nondeterministic Polynomial time)**: The class of decision problems for which a given solution can be *verified* in polynomial time by a deterministic Turing machine.
*   The question is whether every problem whose solution can be quickly verified (NP) can also be quickly solved (P). Most computer scientists believe P $
e$ NP.

MIT 6.006 - Introduction to Algorithms

Cards in this deck

Related Flashcard Sets

JLPT N5 - Essential Grammar & Kanji

Kubernetes Fundamentals & Container Orchestration

Pharmacology - Drug Classes & Mechanisms of Action

CompTIA Security+ (SY0-601) - Threats, Attacks & Vulnerabilities