STANFORD CS106B - Programming Abstractions & Recursive Problem Solving Flashcards

Question 1

What is the primary focus of Stanford CS106B?

Accepted Answer

CS106B focuses on teaching advanced programming techniques, data structures, and algorithms using C++. It emphasizes recursive problem-solving, memory management, and algorithmic analysis to build robust and efficient software.

Question 2

Differentiate between recursion and iteration.

Accepted Answer

Recursion solves a problem by calling itself with smaller inputs until a base case is reached. Iteration solves a problem by repeatedly executing a block of code using loops (e.g., `for`, `while`) until a condition is met. Recursion often leads to more elegant code for certain problems but can incur higher memory overhead due to function call stack.

Question 3

Why is a base case essential for recursive functions?

Accepted Answer

A base case is a non-recursive condition that provides a direct solution to the smallest instance of the problem. Without a base case, a recursive function would call itself indefinitely, leading to an infinite recursion and ultimately a stack overflow error.

Question 4

Define recursive backtracking and its typical application.

Accepted Answer

Recursive backtracking is an algorithmic technique for solving problems by trying to build a solution incrementally. It explores all possible paths to a solution, and if a path leads to a dead end, it "backtracks" (undoes its last choice) and tries another path. It's typically used for combinatorial problems like permutations, combinations, solving mazes, or N-Queens.

Question 5

Outline the general template for a recursive backtracking function.

Accepted Answer

```cpp
void solve(State current_state, Solution& result) {
    if (is_base_case(current_state)) {
        // Process/record solution
        return;
    }

for (Choice choice : possible_choices(current_state)) {
        // 1. Choose: Make a choice
        make_choice(current_state, choice);

// 2. Explore: Recurse with the new state
        solve(current_state, result);

// 3. Unchoose: Backtrack (undo the choice)
        unmake_choice(current_state, choice);
    }
}
```

Question 6

Explain the `choose/explore/unchoose` pattern in backtracking.

Accepted Answer

This pattern describes the three core steps in a recursive backtracking algorithm:
1.  **Choose:** Make a decision or add an element to the current partial solution.
2.  **Explore:** Recursively call the function to find solutions based on the current choice.
3.  **Unchoose:** Undo the decision made in the "choose" step, restoring the state to what it was before the choice. This allows the algorithm to explore other possibilities.

Question 7

How would you structure a recursive backtracking function to find all permutations of a string?

Accepted Answer

The function would typically take the string and a current prefix/result. In each recursive call, it would iterate through the remaining characters:
1.  **Choose:** Select a character from the remaining ones.
2.  **Explore:** Add it to the prefix and recurse with the remaining string.
3.  **Unchoose:** Remove the character from the prefix (implicitly done by passing copies or by explicit removal if modifying a shared structure). The base case is when no characters remain, and the prefix is a complete permutation.

Question 8

List some advanced data structures covered in CS106B.

Accepted Answer

CS106B covers fundamental and advanced data structures including: `Vector` (dynamic array), `Stack`, `Queue`, `Grid`, `Map` (hash table/BST), `Set`, `LinkedList`, `Binary Search Trees` (BSTs), and potentially `Graphs`.

Question 9

What are the core components you'd need to implement a dynamic array like `Vector` from scratch?

Accepted Answer

To implement a `Vector` (dynamic array), you'd typically need:
*   A pointer to a dynamically allocated array (e.g., `T* elements`).
*   An integer to track the current number of elements (`int count`).
*   An integer to track the current capacity of the underlying array (`int capacity`).
*   Methods for `add`, `get`, `set`, `remove`, and a `grow` function to reallocate a larger array when capacity is exceeded.

Question 10

Describe the fundamental structure of a singly linked list and its key operations.

Accepted Answer

A singly linked list is a sequence of `Node` objects, where each `Node` contains a data element and a pointer (`next`) to the subsequent `Node`. The list itself typically stores a pointer to the `head` (first node) and sometimes the `tail` (last node). Key operations include `addFront`, `addBack`, `removeFront`, `removeBack`, `insertAt`, and `removeAt`.

Question 11

Briefly explain how a `Map` (hash table or balanced BST) stores key-value pairs.

Accepted Answer

A `Map` stores associations between unique keys and their corresponding values.
*   **Hash Table based `Map`:** Uses a hash function to convert keys into array indices (buckets). Collisions are handled using techniques like chaining (linked lists in buckets) or open addressing.
*   **Balanced BST based `Map`:** Stores key-value pairs in a tree structure where keys are ordered. Operations like insertion, deletion, and lookup take $O(\log N)$ time on average due to the balanced nature.

Question 12

What is Big-O notation used for?

Accepted Answer

Big-O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms by how their running time or space requirements grow as the input size grows, focusing on the upper bound (worst-case scenario).

Question 13

Give an example of an algorithm with $O(N)$ time complexity.

Accepted Answer

An algorithm with $O(N)$ (linear) time complexity means its execution time grows proportionally to the size of the input $N$. Examples include:
*   Iterating through all elements of an array to find the maximum value.
*   Printing every element in a `Vector`.
*   Searching for an element in an unsorted linked list.

Question 14

Explain what $O(N \log N)$ complexity signifies and name an algorithm that exhibits it.

Accepted Answer

$O(N \log N)$ complexity indicates that the algorithm's execution time grows roughly as $N$ multiplied by the logarithm of $N$. This is often seen in "divide and conquer" algorithms. Examples include efficient sorting algorithms like `Merge Sort` and `Heap Sort`. It's generally considered very efficient for large datasets.

Question 15

Give an example of an algorithm with $O(N^2)$ time complexity.

Accepted Answer

An algorithm with $O(N^2)$ (quadratic) time complexity means its execution time grows proportionally to the square of the input size $N$. Examples include:
*   Nested loops where each loop iterates $N$ times (e.g., `Bubble Sort`, `Selection Sort`, `Insertion Sort`).
*   Finding all pairs of elements in a single list.

Question 16

What is space complexity and how is it expressed using Big-O?

Accepted Answer

Space complexity measures the amount of memory an algorithm uses relative to the size of its input. It includes both auxiliary space (temporary space used by the algorithm) and input space. Like time complexity, it's expressed using Big-O notation, e.g., $O(1)$ for constant space, $O(N)$ for linear space.

Question 17

What is a pointer in C++ and how is it declared?

Accepted Answer

A pointer is a variable that stores the memory address of another variable. It "points" to a location in memory.
*   Declaration: `type* pointer_name;`
*   Example: `int* ptr;` declares `ptr` as a pointer to an integer.
*   Example: `double* dblPtr;` declares `dblPtr` as a pointer to a double.

Question 18

How do you access the value stored at the memory address pointed to by a pointer?

Accepted Answer

You use the dereference operator (`*`) to access the value at the memory address stored in a pointer.
Example:
```cpp
int x = 10;
int* ptr = &x; // ptr stores the address of x
int value = *ptr; // value will be 10 (dereferencing ptr)
```

Question 19

What is dynamic memory allocation and why is it used?

Accepted Answer

Dynamic memory allocation is the process of allocating memory during program execution (runtime) rather than at compile time. It's used when:
*   The exact memory requirements are not known until runtime (e.g., user input determines array size).
*   Large data structures need to persist beyond the scope of the function they were created in.
*   Creating flexible data structures like linked lists or trees.

Question 20

How do you allocate memory dynamically for a single integer using `new`?

Accepted Answer

You use the `new` operator, which returns a pointer to the newly allocated memory.
Example:
```cpp
int* myIntPtr = new int; // Allocates memory for one int
*myIntPtr = 42;          // Assigns a value to the allocated memory
```

Question 21

Why is the `delete` operator crucial when using `new`?

Accepted Answer

The `delete` operator is used to deallocate memory that was previously allocated with `new`. It returns the memory to the system, preventing memory leaks. Failing to `delete` dynamically allocated memory when it's no longer needed leads to memory leaks, where the program holds onto memory it doesn't use, potentially exhausting system resources.

Question 22

What is a memory leak and how can it occur in C++?

Accepted Answer

A memory leak occurs when a program allocates memory dynamically but fails to deallocate it when it's no longer needed. This memory remains reserved by the program, becoming unusable by other parts of the system, eventually leading to reduced performance or program crashes due to memory exhaustion. It commonly occurs when `new` is used without a corresponding `delete`.

Question 23

When would you use `new[]` and `delete[]`?

Accepted Answer

`new[]` is used to dynamically allocate an array of objects or primitive types. It returns a pointer to the first element of the array.
`delete[]` must be used to deallocate memory allocated with `new[]`. Using `delete` instead of `delete[]` for an array can lead to undefined behavior and memory leaks, as it might only deallocate the first element.
Example: `int* arr = new int[10];` and `delete[] arr;`

Question 24

How do pointers enable "pass by reference" behavior in C++ functions?

Accepted Answer

When you pass a pointer to a function, you are passing the memory address of a variable. The function can then use the dereference operator (`*`) to access and modify the original variable's value directly at that memory address. This simulates pass-by-reference, allowing changes made within the function to affect the original variable outside the function's scope, without copying the entire object.

Question 25

What is a recursion tree and how does it help analyze recursive functions?

Accepted Answer

A recursion tree is a diagram that visually represents the sequence of recursive calls made by a function. Each node in the tree represents a function call, and its children represent the recursive calls it makes. It helps in:
*   Visualizing the flow of execution.
*   Determining the total number of operations (time complexity) by summing work at each level.
*   Understanding the depth of recursion (space complexity).
*   Identifying overlapping subproblems for dynamic programming.

STANFORD CS106B - Programming Abstractions & Recursive Problem Solving

Cards in this deck

Related Flashcard Sets

MONASH MTH2010 - Multivariable Calculus & Vector Calculus

SYDNEY CHEM1111 - Chemical Bonding, Thermochemistry & Chemical Equilibrium

GCP Associate Cloud Engineer - Cloud IAM, Compute Engine & Networking

JLPT N4 - Intermediate Japanese Grammar, Particles & High-Frequency Kanji