CS50 - Computer Science Fundamentals Flashcards

Question 1

What are the four stages of C compilation?

Accepted Answer

1. **Preprocessing**: Expands lines starting with `#` (e.g., `#include`, `#define`) and strips comments.
2. **Compiling**: Translates preprocessed source code into assembly code.
3. **Assembling**: Converts assembly code into machine code / object code (`.o`).
4. **Linking**: Combines object code with external libraries (e.g., `cs50.c` or standard math libraries) into a single executable binary.

Question 2

What is a pointer, and what do `&` and `*` do in C?

Accepted Answer

A **pointer** is a variable that stores the memory address of another variable.
- `&` (**Address-of operator**): Returns the memory address where a variable is stored (e.g., `&x`).
- `*` (**Dereference operator**): Accesses or modifies the value stored at the memory address held by a pointer (e.g., `*p`).

Question 3

What is dynamic memory allocation using `malloc()` and `free()`?

Accepted Answer

`malloc(size)` allocates a contiguous block of memory of `size` bytes on the **heap** and returns a `void*` pointer to the first byte. If allocation fails, it returns `NULL`.

`free(ptr)` releases the memory block back to the system to prevent memory leaks.

Question 4

What is the difference between Stack and Heap memory?

Accepted Answer

- **Stack**: Stores function parameters and local variables. Managed automatically in a Last-In, First-Out (LIFO) order with fixed size. Fast, but limited capacity.
- **Heap**: Used for dynamic memory allocation (`malloc`). Managed manually by the programmer, persists until explicitly freed, but slower and prone to fragmentation.

Question 5

What is a memory leak and how do you prevent and detect it?

Accepted Answer

A **memory leak** occurs when dynamically allocated heap memory is no longer needed but is not released via `free()`, causing available system memory to deplete.

- **Prevention**: Call `free()` for every `malloc()` once done.
- **Detection**: Use memory debugging tools like `valgrind`.

Question 6

What is a buffer overflow?

Accepted Answer

A **buffer overflow** happens when a program writes data beyond the boundary of an allocated buffer in memory. This overwrites adjacent memory, leading to data corruption, program crashes, or security vulnerabilities (e.g., code injection).

Question 7

How do $O$, $\Omega$, and $\Theta$ notations describe algorithmic performance?

Accepted Answer

- **Big-O ($O$)**: Represents the **upper bound** (worst-case scenario) of runtime or space complexity.
- **Big-Omega ($\Omega$)**: Represents the **lower bound** (best-case scenario).
- **Big-Theta ($\Theta$)**: Represents a **tight bound** when upper and lower bounds match ($O = \Omega$).

Question 8

Rank common Big-O complexities from fastest to slowest.

Accepted Answer

1. $O(1)$ - Constant time
2. $O(\log n)$ - Logarithmic time
3. $O(n)$ - Linear time
4. $O(n \log n)$ - Linearithmic time
5. $O(n^2)$ - Quadratic time
6. $O(2^n)$ - Exponential time
7. $O(n!)$ - Factorial time

Question 9

How does Linear Search work and what is its time complexity?

Accepted Answer

**Linear Search** iterates sequentially through an array, comparing each element to the target until found or the end is reached.
- **Worst-case / Big-O**: $O(n)$
- **Best-case / Big-Omega**: $\Omega(1)$
- **Prerequisite**: None (works on unsorted arrays).

Question 10

How does Binary Search work and what is its main prerequisite?

Accepted Answer

**Binary Search** repeatedly cuts the search space in half by comparing the target with the middle element of the array.
- **Prerequisite**: Array **must** be sorted.
- **Worst-case / Big-O**: $O(\log n)$
- **Best-case / Big-Omega**: $\Omega(1)$

Question 11

Compare Selection Sort and Bubble Sort complexities.

Accepted Answer

- **Selection Sort**: Repeatedly selects the minimum unsorted element and places it in position.
  - Worst-case: $O(n^2)$, Best-case: $\Omega(n^2)$
- **Bubble Sort**: Swaps adjacent elements if out of order in repeated passes.
  - Worst-case: $O(n^2)$, Best-case (optimized): $\Omega(n)$

Question 12

How does Merge Sort achieve $O(n \log n)$ efficiency?

Accepted Answer

**Merge Sort** uses a **divide-and-conquer** approach:
1. Divide the array into single-element subarrays ($O(\log n)$ recursive divisions).
2. Merge adjacent sorted subarrays back together ($O(n)$ work per level).

- **Time Complexity**: $\Theta(n \log n)$ in all cases.
- **Space Complexity**: $O(n)$ auxiliary space.

Question 13

Compare Arrays vs Linked Lists.

Accepted Answer

- **Array**: Contiguous memory, fixed size. Access by index is $O(1)$, but insertion/deletion requires shifting elements ($O(n)$).
- **Linked List**: Non-contiguous nodes connected by pointers, dynamic size. Access requires traversal ($O(n)$), but insertion/deletion at a known node is $O(1)$.

Question 14

How is a singly linked list node defined in C?

Accepted Answer

```c
typedef struct node {
    int number;
    struct node *next;
} node;
```
Each node contains data (e.g., `number`) and a pointer (`next`) pointing to the next node in memory, or `NULL` if it is the end.

Question 15

What is a Hash Table and what are its performance characteristics?

Accepted Answer

A **Hash Table** combines an array with a **hash function** that maps keys to array indices.
- **Ideal Time**: $O(1)$ lookup, insertion, and deletion.
- **Worst Case**: $O(n)$ if all keys hash to the same bucket (severe collisions).

Question 16

What is a hash collision and how does Separate Chaining resolve it?

Accepted Answer

A **hash collision** occurs when a hash function maps two distinct keys to the same array index.

**Separate Chaining** resolves collisions by storing a linked list at each array bucket. When a collision occurs, the new item is added as a new node in that index's linked list.

Question 17

What is a Trie and what is its lookup time complexity?

Accepted Answer

A **Trie** (prefix tree) is a tree-like data structure where each node represents a character of a key (e.g., word).
- **Lookup/Insert Time**: $O(k)$, where $k$ is the length of the string, independent of the total number of words stored.
- **Tradeoff**: Very fast search, but high memory footprint.

Question 18

What is a `struct` in C and how do you access its fields?

Accepted Answer

A `struct` is a user-defined data type grouping related variables.

- Direct access: `person.age`
- Pointer access: `ptr->age` (shorthand for `(*ptr).age`)

Question 19

What is recursion and what causes a Stack Overflow?

Accepted Answer

**Recursion** is when a function calls itself. It requires a **base case** to stop execution.

Without a base case, the function calls itself indefinitely, adding stack frames until stack memory is exhausted, causing a **Stack Overflow**.

Question 20

How does Pointer Arithmetic work in C?

Accepted Answer

Incrementing a pointer (e.g., `ptr + 1`) increases its address by `sizeof(type)` bytes, moving to the next element of that type in memory.

Array indexing `arr[i]` is syntax sugar for `*(arr + i)`.

CS50 - Computer Science Fundamentals

Cards in this deck

Related Flashcard Sets

JLPT N4 - Grammar Patterns & Kanji

German B1 - Intermediate Grammar & Vocabulary

Kubernetes Fundamentals & Orchestration

CFA Level I - Ethical and Professional Standards