Introduction to Computation and Programming Using Python

1. Computation is fundamentally about calculation and memory.

A computer does two things, and two things only: it performs calculations and it remembers the results of those calculations.

Core capabilities. At its heart, a computer is a machine designed for two tasks: performing arithmetic and logical operations at incredible speed and storing the results. This simple foundation, executed billions of times per second with vast memory capacity, enables the complex tasks computers perform today. Understanding these fundamental limits and powers is the first step in computational thinking.

Beyond human scale. While humans are limited by the speed of thought and hand, computers overcome these barriers. Problems previously intractable due to the sheer volume of calculations or data storage required become amenable to computational solutions. This shift allows us to tackle challenges like climate modeling or analyzing massive datasets.

Imperative knowledge. Computation relies on imperative knowledge – the "how-to" recipes or algorithms. Unlike declarative knowledge (statements of fact), imperative knowledge provides the step-by-step instructions needed to achieve a result, such as Heron's method for finding a square root.

2. Algorithms provide imperative recipes for problem-solving.

An algorithm is a finite list of instructions describing a set of computations that when executed on a set of inputs will proceed through a sequence of well-defined states and eventually produce an output.

Structured instructions. Algorithms are precise, step-by-step procedures for solving a problem or performing a computation. They are like recipes, detailing the sequence of operations and the flow of control, including tests to decide when steps are executed or repeated. This structured approach ensures a predictable process from input to output.

Foundation of programming. Programming languages are the tools we use to describe algorithms so computers can execute them. Early computers were fixed-program machines, designed for one task, but modern computers are stored-program machines, capable of executing any algorithm described in their instruction set. This flexibility, rooted in the concept of a Universal Turing Machine, makes computers general-purpose problem solvers.

Literal execution. The power and frustration of programming stem from the computer executing algorithms exactly as written. This literalness means computers can perform complex tasks flawlessly if the algorithm is correct, but will also faithfully execute errors, leading to unexpected or incorrect results. Careful algorithm design is paramount.

3. Python offers essential tools for expressing computation.

Fortunately, we need only one more programming language construct, iteration, to allow us write programs of arbitrary complexity.

Basic building blocks. Python provides fundamental constructs necessary for imperative programming: scalar types (int, float, bool, None), variables and assignment, operators, and input/output. These allow us to represent data, store values, perform calculations, and interact with the user. Understanding these basics is the starting point for writing any program.

Controlling flow. Programs gain power through control flow mechanisms that dictate the order of execution. Conditional statements (if, elif, else) allow branching based on tests, enabling programs to respond differently to varying inputs. Iteration (while, for loops) allows repeating blocks of code, essential for tasks that require processing sequences or performing actions multiple times.

Readability matters. Beyond just working, programs should be easy for humans to read and understand. Python emphasizes readability through clear syntax, meaningful variable names, comments, and consistent indentation. This is crucial because programmers spend significant time reading code, especially during debugging.

4. Abstraction is key to managing program complexity.

Functions are a way of creating computational elements that we can think of as primitives.

Hiding details. Abstraction allows us to use complex pieces of code as "black boxes," focusing on what they do (their specification) rather than how they do it (their implementation). Functions are the primary mechanism for this, bundling code into reusable units that can be called with different inputs (parameters). This simplifies program design and maintenance.

Decomposition and reuse. Functions enable decomposition, breaking large problems into smaller, manageable subproblems. Once defined, functions can be reused multiple times within a program or across different programs, reducing redundancy and making code easier to update. Higher-order functions, which take functions as arguments or return them, further enhance flexibility and generalization.

Scoping rules. Functions introduce scopes, creating local namespaces for variables. This prevents unintended interactions between different parts of a program, ensuring that changes within a function don't affect variables outside it, unless explicitly intended (like with global variables, used sparingly). Understanding scope is vital for predicting program behavior.

5. Structured data types organize information effectively.

Lists differ from tuples in one hugely important way: lists are mutable.

Collections of data. Beyond simple scalar values, programs need to handle collections of data. Python provides powerful built-in structured types like tuples (immutable ordered sequences), lists (mutable ordered sequences), sets (mutable unordered collections of unique elements), and dictionaries (mutable mappings from keys to values). Each type is suited for different tasks.

Accessing elements. Sequence types (strings, tuples, lists) support indexing and slicing to access individual elements or subsequences. Dictionaries use hashable keys for efficient lookup, providing a flexible way to associate information. Understanding the properties of these types is crucial for choosing the right tool for data manipulation.

Mutability and aliasing. A key distinction is mutability: whether an object can be changed after creation. Lists, sets, and dictionaries are mutable, while strings, tuples, and numbers are not. Mutability, combined with aliasing (multiple names referring to the same object), can lead to powerful but sometimes tricky side effects that require careful handling, such as cloning when iteration or independent modification is needed.

6. Efficiency matters, especially for large problems.

As a proxy for “very large,” asymptotic notation describes the complexity of an algorithm as the size of its inputs approaches infinity.

Beyond correctness. While correctness is paramount, the performance of an algorithm becomes critical when dealing with large inputs or real-time constraints. Measuring performance in abstract steps relative to input size allows comparison independent of specific hardware or implementation details. This focuses on how running time grows.

Worst-case focus. We typically analyze worst-case running time to guarantee performance under the most challenging conditions. Asymptotic notation, like Big O (O) and Big Theta (θ), provides a formal way to describe this growth as input size approaches infinity, ignoring constant factors and lower-order terms. Common complexity classes include constant, logarithmic, linear, log-linear, polynomial, and exponential.

Algorithm choice. The order of growth dramatically impacts feasibility for large inputs. An O(n log n) sorting algorithm is vastly superior to an O(n²) one for large lists. Choosing an efficient algorithm, like binary search (O(log n)) over linear search (O(n)) on sorted data, is often more impactful than low-level coding optimizations. However, simple algorithms are often preferred if they are "fast enough" and easier to understand and debug.

7. Optimization problems seek the best solution under constraints.

The notion of an optimization problem provides a structured way to think about solving lots of computational problems.

Maximizing or minimizing. Many real-world problems involve finding the best possible outcome, whether maximizing value (like profit) or minimizing cost (like time or distance), subject to certain limitations or rules. These are formalized as optimization problems with an objective function and constraints.

Knapsack problems. A classic example is the knapsack problem, where the goal is to select items with maximum total value that fit within a weight capacity. The 0/1 knapsack problem (take or leave each item) is computationally hard in the worst case, requiring exponential time to find the guaranteed optimal solution by brute-force enumeration of all subsets.

Greedy approximations. While optimal solutions can be elusive, greedy algorithms offer a practical alternative. They make the locally best choice at each step (e.g., taking the item with the highest value-to-weight ratio). Though not guaranteed to find the global optimum, greedy algorithms are often much faster (e.g., O(n log n) for knapsack variants) and provide reasonably good solutions in practice.

8. Dynamic programming efficiently solves problems with overlapping subproblems.

Dynamic programming is a method for efficiently solving problems that exhibit the characteristics of overlapping subproblems and optimal substructure.

Avoiding redundant work. Some problems, like the naive recursive calculation of Fibonacci numbers, repeatedly solve the same subproblems. Dynamic programming tackles this inefficiency by storing the results of subproblems in a table or "memo" so they can be looked up rather than recomputed. This transforms exponential complexity into polynomial (often linear) complexity for such problems.

Two approaches. Dynamic programming can be implemented top-down using memoization, where recursive calls check the memo before computing, or bottom-up using a tabular method, which iteratively solves subproblems from smallest to largest, filling the table. The tabular method is often simpler and more efficient if all subproblems must be solved.

Knapsack revisited. The 0/1 knapsack problem, while inherently exponential in the number of items, can often be solved efficiently using dynamic programming if the knapsack capacity or item weights are within a reasonable range. By memoizing solutions based on the remaining items and available weight, the algorithm avoids recomputing the optimal choice for identical subproblems, leading to a pseudo-polynomial time complexity that is practical for many instances.

9. Randomness and simulation model uncertainty in the world.

Many aspects of the world in which we live can be accurately modeled only as stochastic processes.

Beyond deterministic. Not all phenomena are predictable with certainty. Stochastic processes, whose outcomes involve randomness, require different computational approaches. Simulation models mimic real systems by incorporating random elements, allowing us to explore a range of possible behaviors rather than predicting a single outcome.

Random walks. A random walk, like the drunkard's walk, is a simple stochastic process where movement direction is random at each step. Simulating many such walks can reveal aggregate properties, such as the expected distance from the origin, which may not be intuitively obvious. Different types of random walks (e.g., biased) can be modeled by changing the probabilities of different movements.

Modeling complex systems. Simulations are invaluable when real-world experiments are too costly, dangerous, or time-consuming, or when analytical models are intractable. They allow "what if" scenarios, like the spread of infectious diseases or the behavior of financial markets. However, simulations are models, approximations of reality, and their results must be interpreted with caution and skepticism.

10. Statistics allows inference from samples and understanding distributions.

The guiding principle of inferential statistics is that a random sample tends to exhibit the same properties as the population from which it is drawn.

Learning from data. Statistics provides tools to analyze data, summarize its properties, and make inferences about larger populations based on samples. Descriptive statistics (mean, variance, standard deviation) quantify data characteristics, while inferential statistics uses probability to draw conclusions about populations from which samples are drawn.

Sampling and confidence. Since examining entire populations is often impossible, we rely on samples. The Law of Large Numbers suggests that sample properties converge to population properties as sample size increases. The Central Limit Theorem is crucial, stating that sample means are normally distributed, allowing us to estimate confidence intervals and levels (e.g., 95% confidence) around sample means, even if the underlying population isn't normal.

Visualizing data. Histograms show the distribution of values in a dataset, while plots with error bars visualize confidence intervals, indicating the reliability of estimates. Understanding probability distributions (normal, uniform, exponential, etc.) helps interpret data and choose appropriate statistical tests. However, statistical significance (low p-value) indicates unlikeliness under a null hypothesis, not necessarily a large or important effect.

11. Machine learning finds patterns and makes predictions from data.

When computer scientists speak about machine learning, they most often mean the discipline of writing programs that automatically learn to make useful inferences from implicit patterns in data.

Learning from examples. Machine learning algorithms build models from observed data (training data) to make predictions or find structure in new, unseen data. This involves choosing a model representation, defining an objective function to evaluate model quality, and using optimization to find the best model. It's about generalization from examples.

Supervised vs. unsupervised. Supervised learning uses labeled examples (feature vectors paired with values or labels) to learn predictive rules (regression for values, classification for labels). Unsupervised learning uses unlabeled feature vectors to discover hidden structure, such as grouping similar examples into clusters.

Features and distance. Effective machine learning relies on good feature engineering to extract relevant information from raw data. Features are converted into numerical vectors, and distance metrics (like Euclidean or Manhattan distance, variants of Minkowski distance) are used to quantify the similarity or dissimilarity between examples. Scaling features appropriately is important to prevent some features from dominating distance calculations.

12. Be critical: Statistics can easily mislead if not understood.

It's just as easy to lie with numbers as it is to lie with words.

Data quality is paramount. Statistical analysis is only as good as the data it uses; "Garbage In, Garbage Out" is a fundamental principle. Flawed or biased data will inevitably lead to misleading conclusions, regardless of the sophistication of the statistical methods applied. Always question the source and collection method of data.

Correlation is not causation. Observing that two variables move together (correlation) does not imply that one causes the other. A lurking variable might be the true cause, or the correlation could be purely coincidental. Assuming causation from correlation is a common and dangerous fallacy.

Context and presentation matter. Statistics and plots can be manipulated to convey a desired impression by selectively choosing data, truncating axes, using misleading scales (like logarithmic axes without clear labeling), or comparing incomparable quantities. Always seek context, look at the raw data if possible, and be wary of conclusions drawn from small samples or multiple hypothesis tests without appropriate correction.

Last updated: May 7, 2025