01. Introduction to Programming and Algorithmic Problem Solving

From Problems to Programs

Programming begins with a distinction between what must be achieved and how it will be achieved. A problem describes a desired result, such as determining the largest value in a list. An algorithm gives a precise method for producing that result, while a program expresses the method in a particular language.

A well-specified algorithm identifies:

• the inputs supplied to the procedure;

• the processing steps performed;

• the output produced;

• a reason the procedure eventually stops; and

• why the output satisfies the problem requirements.

For example, to find the largest value, begin by treating the first value as the current largest. Examine each remaining value and replace the current largest whenever a larger value appears. After all values have been examined, return the current largest.

The algorithm is the general idea. The program is one concrete implementation of that idea.

Takeaway: Separate the problem, the algorithm, and the program. This makes it easier to reason about a solution before worrying about language-specific details.

Reading Code: Structure and Meaning

Source code is the human-readable text written in a programming language. It contains names, values, expressions, statements, and comments. For source code to be accepted, it must follow the language’s syntax, including required punctuation, indentation, and structural rules.

Syntax and meaning are different. A condition followed by its required block marker may be syntactically valid, while omitting that marker creates a syntax error. Conversely, two statements can both be syntactically valid while producing different results: adding two values and multiplying those same values have different semantics.

An expression produces a value. A statement performs an action, such as assigning a value or calling a function. For example, a calculation such as $2 + 3$ is an expression, while assigning its result to a variable is an action performed by a statement.

A correct program must satisfy both requirements:

• its structure must be valid according to the language’s syntax; and

• its meaning must match the intended solution according to its semantics.

Takeaway: Code can fail because it is malformed, because it means the wrong thing, or because both problems occur at once.

Execution and Control Flow

Execution is the process of carrying out a program’s instructions. Depending on the language and environment, source code may be interpreted directly, compiled into another form, or handled through a combination of compilation and interpretation.

A simplified execution process is:

1. The programmer writes source code.

2. A language processor reads the code.

3. The processor checks its structure and may translate it into a suitable executable form.

4. The runtime carries out the instructions.

5. The program produces output, changes data, or interacts with its environment.

Execution follows control flow. In a simple sequence, statements run from top to bottom. A conditional chooses one path from alternatives. A loop repeats a block. A function call transfers control temporarily to another block and later returns to the calling code.

For example, a conditional that compares a score with a passing boundary executes a pass branch when the condition is true and a fail branch otherwise. A loop that repeats for a fixed range executes its body once for each value in that range.

Takeaway: To predict a program’s behavior, trace not only the values it computes but also the path and order through which its statements execute.

Values, Types, and Expressions

Variables give names to values, and data types describe what those values represent. Common types include integers such as $-3$, floating-point numbers such as $3.14$, strings such as text, Boolean values, and ordered collections such as lists or arrays.

Types affect which operations are meaningful. Adding two numbers performs arithmetic, while joining two strings creates a longer string. A language may require types to be declared explicitly, infer them, or check them during execution.

Expressions combine values, variables, and operators to produce results. Important operator categories include:

• arithmetic operators for calculations;

• comparison operators for testing relationships between values;

• logical operators for combining or inverting conditions; and

• assignment operators for storing or updating values.

Parentheses make grouping explicit. For example, $(a + b) \times c$ indicates that the addition is performed before the multiplication.

A Boolean expression evaluates to either true or false. The logical operation $p \mathbin{\text{and}} q$ is true only when both conditions are true; $p \mathbin{\text{or}} q$ is true when at least one is true; and $\mathbin{\text{not}}\ p$ reverses the truth value.

Takeaway: Variables, types, expressions, and operators provide the basic vocabulary for representing and transforming information.

Repetition, Functions, and Collections

Iteration repeats a group of instructions. A loop may traverse every element in a collection, repeat a known sequence of values, or continue while a condition remains true. A loop must make progress toward stopping; otherwise, it may run indefinitely.

When examining a loop, ask four questions:

1. What is the starting state?

2. What condition keeps the loop running?

3. What changes after each iteration?

4. What must be true when the loop stops?

Functions support decomposition by packaging a focused operation under a meaningful name. A function may receive parameters and return a result. Breaking a large task into functions reduces repetition, clarifies responsibilities, and makes testing and debugging easier.

Lists and arrays store multiple values in an ordered structure. Elements are accessed by an index, and many languages begin indexing at zero. Common operations include traversal, insertion, deletion, and searching. The choice of data structure can affect both clarity and efficiency.

A useful design is to have each function perform one coherent task, use clearly named parameters, and return a result that callers can use without needing to know every implementation detail.

Takeaway: Loops handle repetition, functions organize behavior, and collections organize related values. Together, they let a solution scale beyond a single straight-line sequence.

A Workflow for Reliable Solutions

A reliable workflow turns an unclear requirement into a tested solution.

1. Understand the problem. Restate the task, identify inputs and required outputs, record constraints and assumptions, and consider valid, invalid, and unusual cases.

2. Decompose the task. Divide the problem into smaller operations. For a grade calculator, these might be reading scores, computing an average, comparing the average with boundaries, and displaying a result.

3. Design the algorithm. Write pseudocode or draw a flowchart before writing full code. Trace a small example and record how important values change.

4. Implement the design. Translate the method into source code using meaningful names, consistent formatting, and focused functions.

5. Test the program. Use normal cases, boundary cases, special cases, and invalid cases. Compare actual behavior with expected behavior.

6. Debug and refine. Reproduce a failure, record the expected result, inspect the error and control flow, isolate a likely cause, make one small change, and retest. Add a regression test when appropriate.

Testing can reveal failures, but passing a limited set of tests does not prove correctness for every possible input. Stronger confidence comes from reasoning about why the algorithm works, including the properties that must remain true during execution.

Takeaway: Treat problem solving as a cycle of understanding, design, implementation, testing, and refinement rather than as typing code immediately.

Binary Search as a Structured Example

Binary search illustrates how an algorithm can use the structure of its input to reduce work. It applies to sorted data. Instead of checking every element from the beginning, it examines the middle of the current search range.

The method maintains a search range from a lower index to a higher index. If the middle value equals the target, the search succeeds. If the middle value is smaller than the target, values at or below the middle can be eliminated. If the middle value is larger, values at or above the middle can be eliminated. The process continues until the target is found or the range becomes empty.

The key invariant is: if the target exists, it remains somewhere between the current lower and higher bounds. Each iteration preserves that invariant while reducing the search space.

For an input of size $n$, binary search has worst-case running time $O(\log n)$, because the remaining range is approximately halved each time. A linear search may require $O(n)$ comparisons. Binary search is therefore faster for sufficiently large inputs, but only when the sorted-order requirement is satisfied.

This example demonstrates a reusable pattern:

1. define the current search space;

2. inspect a strategically chosen element;

3. eliminate impossible cases; and

4. repeat until the answer is found or no candidates remain.

Takeaway: Correctness depends on maintaining the invariant, while efficiency comes from eliminating many impossible cases at each step.

Efficiency and the Limits of Computation

Algorithm analysis studies how resource use grows as the input size increases. The two main resources are time complexity, which concerns the growth in operations, and space complexity, which concerns additional memory.

Common growth classifications include:

• $O(1)$: constant work, such as accessing one array element;

• $O(\log n)$: repeated reduction by a factor, as in binary search;

• $O(n)$: work proportional to the input size, as in scanning a list;

• $O(n \log n)$: a common bound for efficient sorting methods; and

• $O(n^2)$: work associated with many pairs or nested scans.

These notations describe growth rather than exact elapsed time. Constants, implementation choices, and machine details can matter for small inputs, but growth rates become increasingly important as inputs become large.

Correctness comes before efficiency. A fast algorithm that produces the wrong answer is not a solution. Once correctness is established, complexity analysis helps determine whether the solution is practical and whether a different design would use fewer resources.

Decidability asks a more fundamental question than complexity: does any algorithm exist that always gives the correct answer and halts for every valid input? A decidable problem has such an algorithm. An undecidable problem has no algorithm that succeeds on every instance while always halting. The halting problem is a classic example of an undecidable problem.

Thus, two separate questions must be kept apart:

1. Can the problem be solved algorithmically at all?

2. If it can, how much time and memory does a solution require?

Takeaway: Complexity evaluates the resources required by a solution; decidability determines whether a universally terminating solution exists in the first place.

• Algorithmic problem solving

• Data type