MIT 6.0001 - Introduction to Computer Science and Programming in Python Flashcards

Question 1

Functions and Scope Environments

Accepted Answer

Calling a function creates a new **local frame/environment**. Variables declared inside a function exist only within its local scope and are destroyed upon returning, preventing unintentional side effects in the global scope.

Question 2

Tuples vs. Lists

Accepted Answer

* **Tuple**: An ordered, **immutable** sequence of elements enclosed in parentheses `()`. Cannot be modified after creation.
* **List**: An ordered, **mutable** sequence of elements enclosed in brackets `[]`. Supports insertion, deletion, and reassignment.

Question 3

Scalar vs. Non-Scalar Data Types

Accepted Answer

**Scalar** data types represent indivisible, atomic values in Python (e.g., `int`, `float`, `bool`, `None`). **Non-scalar** data types have internal structure and can be indexed or iterated over (e.g., `str`, `list`, `tuple`, `dict`).

Question 4

Variable Assignment and Binding

Accepted Answer

In Python, variable assignment (e.g., `x = 5`) does not store a value inside a variable. Instead, it **binds** the variable name `x` to an object in memory containing the value `5`.

Question 5

Conditional Control Flow (`if`, `elif`, `else`)

Accepted Answer

Executes specific blocks of code based on boolean evaluation:
```python
if x > 0:
    print("Positive")
elif x < 0:
    print("Negative")
else:
    print("Zero")
```
Evaluation stops at the first branch whose condition evaluates to `True`.

Question 6

`while` Loop vs. `for` Loop

Accepted Answer

* **`while` loop**: Unbounded iteration. Continues executing code as long as a specified boolean expression remains `True`.
* **`for` loop**: Bounded iteration. Iterates over a predefined sequence or range (e.g., `for i in range(n):`).

Question 7

Floating-Point Imprecision

Accepted Answer

Computers represent `float` values using binary fractions. Many base-10 decimals (like `0.1`) cannot be stored exactly in binary, leading to minor rounding errors: `0.1 + 0.2 == 0.3` evaluates to `False` in Python.

Question 8

Bisection Search (Binary Search)

Accepted Answer

An efficient algorithm for finding a target value within a sorted list by repeatedly halving the search space. Its time complexity is $\mathcal{O}(\log n)$, making it vastly superior to linear search $\mathcal{O}(n)$ for large datasets.

Question 9

Newton-Raphson Method

Accepted Answer

An iterative numerical algorithm for finding roots of a differentiable function $f(x) = 0$. For finding the square root of $k$ where $f(x) = x^2 - k$, the update rule is:
$$x_{n+1} = x_n - \frac{x_n^2 - k}{2x_n}$$

Question 10

Aliasing and Mutability

Accepted Answer

**Aliasing** occurs when two variable names refer to the exact same mutable object in memory (e.g., `L2 = L1`). Modifying `L2` via `L2.append(3)` directly modifies `L1` because both point to the same list memory address.

Question 11

Python Dictionaries (`dict`)

Accepted Answer

A hash table-based collection of key-value pairs (`{key: value}`). Keys must be **immutable** types (like `int`, `str`, `tuple`). Dictionary key lookups run in $\mathcal{O}(1)$ average time complexity.

Question 12

Recursion

Accepted Answer

A programming methodology where a function calls itself to solve smaller instances of the same problem. Requires two main components:
1. **Base Case**: Halts the recursive calls.
2. **Recursive Step**: Reduces problem size and calls the function again.

Question 13

Recursive Implementation: Factorial

Accepted Answer

Computing $n! = n 	imes (n-1)!$ recursively in Python:
```python
def factorial(n):
    if n <= 1:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive step
```

Question 14

Object-Oriented Programming: Class vs. Instance

Accepted Answer

* **Class**: A user-defined blueprint or template that defines attributes (data) and methods (behavior).
* **Instance (Object)**: A specific realization of a class created in memory with concrete attribute values.

Question 15

Class Constructor (`__init__`) and `self`

Accepted Answer

The `__init__` method is automatically called when a class instance is created. `self` parameter explicitly refers to the instance object being created or manipulated:
```python
class Coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y
```

Question 16

Encapsulation and Data Hiding

Accepted Answer

**Encapsulation** combines data and functions into a single class entity. Data hiding restricts direct outside access to attributes (by convention in Python using a leading underscore, e.g., `self._secret`) to enforce access through getter/setter methods.

Question 17

Big O Notation (Order of Growth)

Accepted Answer

A mathematical notation used to describe the **upper bound** of an algorithm's asymptotic runtime complexity as input size $n$ approaches infinity, focusing on the dominant term and ignoring constants.

Question 18

Common Complexity Classes (Fastest to Slowest)

Accepted Answer

1. $\mathcal{O}(1)$: Constant
2. $\mathcal{O}(\log n)$: Logarithmic
3. $\mathcal{O}(n)$: Linear
4. $\mathcal{O}(n \log n)$: Log-linear
5. $\mathcal{O}(n^2)$: Quadratic
6. $\mathcal{O}(2^n)$: Exponential

Question 19

Selection Sort Algorithm

Accepted Answer

Iteratively finds the minimum element from the unsorted portion of a list and swaps it into the sorted portion. Time complexity is $\mathcal{O}(n^2)$ in all cases, making it inefficient for large datasets.

Question 20

Merge Sort Algorithm

Accepted Answer

A divide-and-conquer algorithm that recursively splits a list into halves until single elements remain, then merges the sorted halves. Time complexity is $\mathcal{O}(n \log n)$, but requires extra space $\mathcal{O}(n)$.

MIT 6.0001 - Introduction to Computer Science and Programming in Python

Cards in this deck

Related Flashcard Sets

TypeScript - Modern JavaScript Development & Type Safety

Monash FIT9132 - Data Mining & Machine Learning Fundamentals

Biochemistry - Metabolic Pathways & Regulation

JLPT N2 - Advanced Japanese Grammar, Vocabulary & Kanji