Problem Solving, Algorithms, and Python Programming Notes

Problem Solving Aspects & Algorithmic Thinking

• Problem Definition Phase

  • The success of solving any problem depends on a thorough understanding of the problem requirements, focusing on what must be done rather than how to do it.
  • A problem statement must be decomposed into a set of precisely defined tasks to naturally lead to effective algorithm designs.
  • Key analytical questions to ask during general problem definition:
  • What are you asked to find or show?
  • Can you restate the problem in your own words?
  • Can you think of a picture or diagram that might help you understand the problem?
  • Is there enough information to enable you to find a solution?
  • Do you understand all the words used in stating the problem?
  • Do you need to ask a question to get the answer?
  • Key analytical questions to ask in a programming context:
  • Can I restate the problem in my own words? (e.g., "Write a function that adds two numbers" or "Implement addition").
  • What are the inputs that go into the problem? (Analyze data types and structures: are inputs integers, floating-point numbers, or strings representing numbers? String inputs allow arbitrarily large numbers but require handling beyond native primitive types).
  • What are the outputs that should come from the solution to the problem? (Determine the expected data type, such as a number or string).
  • Can the outputs be determined from the inputs? (Check for edge cases, such as missing arguments or empty inputs).
  • How should I label the important pieces of data that are part of the problem? (Assign descriptive labels to the function, inputs, and outputs, e.g., add, num1, num2, and sum).

• Problem Solving Strategies & Heuristics

  • Getting Started on a Problem: Programmers often encounter blocks by worrying about implementation details before working out an implementation-independent solution. The best approach is to avoid getting bogged down in low-level coding details early; premature coding increases overall development time.
  • Use of Specific Examples: When stuck, test concrete examples as props or heuristics. For instance, to find the maximum or minimum element in a set, construct a specific numeric array to observe and define the comparison mechanism.
  • Similarities Among Problems: Leverage past experience by identifying structural overlaps between current and previously solved problems. However, avoid cognitive bias: over-studying an existing solution can force reasoning down a sub-optimal path or dead end. View problems from multiple angles—metaphorically turning them upside down, inside out, sideways, backwards, and forwards.
  • Working Backwards from the Solution: When the starting point is unclear, assume the solution is known and work backwards to establish the initial conditions or required inputs. Even guessing a solution can provide a foothold. Reflecting on the solution discovery process reinforces learning ("We learn most when we have to invent"). For example, solving $3 \times x = 24$ by testing candidate solutions ($6$, $7$, $8$, $9$) yields $x = 8$ because $3 \times 8 = 24$.

• Classic Problem Riddles and Solutions

  • The Goat, Wolf, and Cabbage Riddle:
  • Problem: A farmer must transport a wolf, a goat, and a cabbage across a river using a boat that holds only himself and one item. If left unattended, the wolf eats the goat, or the goat eats the cabbage.
  • Step-by-Step Solution:
    1. Farmer takes Goat across the river (leaving Wolf and Cabbage on the starting bank).
    2. Farmer returns alone to the starting bank.
    3. Farmer takes Wolf across the river.
    4. Farmer returns with Goat to the starting bank.
    5. Farmer takes Cabbage across the river.
    6. Farmer returns alone to the starting bank.
    7. Farmer takes Goat across the river.
  • 4 Men and the Bridge Riddle:
  • Problem: 4 men must cross a narrow bridge at night with 1 flashlight within $17$\,$\text{minutes}$. A maximum of 2 people can cross simultaneously, moving at the speed of the slower person. The flashlight must be walked back and forth. Crossing times: Man 1 ($1$\,$\text{minute}$), Man 2 ($2$\,$\text{minutes}$), Man 3 ($5$\,$\text{minutes}$), Man 4 ($10$\,$\text{minutes}$).
  • Step-by-Step Solution:
    1. Step 1: Men 1 and 2 cross together ($2$\,$\text{minutes}$ elapsed; $15$\,$\text{minutes}$ remaining).
    2. Step 2: Man 2 returns with the flashlight ($2$\,$\text{minutes}$ elapsed; total elapsed $4$\,$\text{minutes}$; $13$\,$\text{minutes}$ remaining).
    3. Step 3: Men 3 and 4 cross together ($10$\,$\text{minutes}$ elapsed; total elapsed $14$\,$\text{minutes}$; $3$\,$\text{minutes}$ remaining).
    4. Step 4: Man 1 returns with the flashlight ($1$\,$\text{minute}$ elapsed; total elapsed $15$\,$\text{minutes}$; $2$\,$\text{minutes}$ remaining).
    5. Step 5: Men 1 and 2 cross together ($2$\,$\text{minutes}$ elapsed; total elapsed $17$\,$\text{minutes}$; $0$\,$\text{minutes}$ remaining).
  • 0-1 Knapsack Problem:
  • Given values $\text{value} = \{60, 100, 120\}$, weights $\text{weight} = \{10, 20, 30\}$, and capacity $W = 50$.
  • Evaluate combination weight and value bounds:
    • Weight $10 \implies \text{Value } 60$
    • Weight $20 \implies \text{Value } 100$
    • Weight $30 \implies \text{Value } 120$
    • Weight $20 + 10 = 30 \implies \text{Value } 100 + 60 = 160$
    • Weight $30 + 10 = 40 \implies \text{Value } 120 + 60 = 180$
    • Weight $30 + 20 = 50 \implies \text{Value } 120 + 100 = 220$
    • Weight $30 + 20 + 10 = 60 > 50$ (Exceeds capacity $W$).
  • Optimal Solution: Total value of $220$ at weight $50$
  • Towers of Hanoi:
  • Problem: Move $n$ rings of varying sizes stacked in ascending order from a source peg to a destination peg using an auxiliary peg.
  • Rules: Only 1 disk moved at a time; only the top disk can be moved; no larger disk may sit on a smaller disk.
  • Algorithm: text Procedure Hanoi (disk, source, dest, aux) IF disk == 1 THEN move disk from source to dest ELSE Hanoi (disk - 1, source, aux, dest) move disk from source to dest Hanoi (disk - 1, aux, dest, source) END IF END Procedure       

Top-Down Design & Problem Solving Paradigms

• Aspects of Top-Down Design

  • Decomposition: Break complex problems into independent, manageable sub-problems (illustrated by breaking individual sticks from a bundle or the "Lion vs. Cows" analogy where cows graze individually and become vulnerable).
  • Choice of Suitable Data Structure: Select structures (Arrays, Strings, Sets, Dictionaries) that minimize search and update time, optimize computation, and streamline storage (illustrated by a librarian organizing books into classified racks).
  • Construction of Loops: Establish clear initialization, execution conditions, and termination steps. Prevent infinite loop trapping (illustrated by navigating a 6-circuit labyrinth).
  • Establishing Initial Conditions: Declare and initialize loop control variables properly before loop entry (e.g., maintaining a item/currency count when buying items iteratively).
  • Finding Iterative Constructs: Map output solutions of prior steps to input conditions of subsequent steps.
  • Termination of Loops: Guarantee that loop continuation conditions eventually evaluate to false based on state changes.

• Algorithmic Problem-Solving Paradigms

  1. Brute-Force / Exhaustive Search: Straightforward evaluation of every possible candidate solution (e.g., systematically trying every 4-digit code combination on a padlock).
  2. Divide and Conquer: Divide a problem into sub-problems, solve sub-problems independently, and combine their solutions (e.g., counting coins by grouping them by denomination).
  3. Greedy Algorithms: Make locally optimal decisions at each step without reconsidering past choices (e.g., selecting nearest capital cities sequentially when traveling from Kanyakumari to Kashmir).
  4. Dynamic Programming: Solve mathematical optimization problems by breaking them into overlapping sub-problems, using recursion, and storing intermediate results over time (e.g., arranging cards in a card game).
  5. Branch and Bound: Use state-space trees and bounding functions to solve combinatorial optimization problems (e.g., solving the 0-1 Knapsack Problem).
  6. Randomized Algorithms: Incorporate random numbers into decision-making and optimization steps to achieve statistical performance guarantees (e.g., random sampling or surprise checks).
  7. Backtracking: Build candidate solutions incrementally, abandoning a candidate ("backtracking") as soon as it is determined that it cannot lead to a valid solution (e.g., solving crosswords).

Algorithm Formalism, Flowcharts, and Asymptotic Complexity Analysis

• Definitions & Fundamental Concepts

  • Algorithm: A finite list of well-defined, step-by-step instructions to solve a specific problem or calculate a function, independent of programming languages. Formally introduced by 9th-century mathematician Muḥammad ibn Mūsā al-Khwārizmī.
  • Pseudocode: An informal, high-level description of an algorithm that mimics programming language constructs without rigid syntax.
  • Flowchart: A graphical/visual representation depicting the control flow and logic of an algorithm using standard geometric symbols.
  • Program: An explicit, unambiguous implementation of an algorithm written in a specific programming language.

• Essential Properties of an Algorithm

  • Finiteness: An algorithm must always terminate after a finite number of steps.
  • Definiteness: Each step must be precisely defined, rigorous, and unambiguous.
  • Input: Accepts zero or more quantities prior to execution.
  • Output: Produces one or more quantities with a defined relationship to inputs.
  • Effectiveness: Operations must be sufficiently basic to be performed exactly in finite time.
  • Determinism vs. Non-determinism: Deterministic algorithms have a well-defined successor for every step, whereas non-deterministic algorithms incorporate random choices.

• Flowchart Symbols and Standards

  • Oval: Start / End of flowchart.
  • Parallelogram: Input and Output operations.
  • Rectangle: Processing (arithmetic operations and data manipulations).
  • Diamond: Decision making (evaluates conditions yielding True/False or Yes/No branches).
  • Arrows / Flow Lines: Indicate direction of logic flow connecting symbols.
  • Circle: In-page connector.
  • Off-Page Connector: Connects flowchart logic spanning across multiple pages.
  • Predefined Process / Function: Represents a call to a group of statements or subroutines.

• Analysis of Algorithms: Performance Metrics

  • Time Complexity: The running time of an algorithm expressed as a function of input size $n$.
  • Space Complexity: The amount of computer memory consumed during execution as a function of input size $n$.
  • A Posteriori vs. A Priori Analysis:
  • A Posteriori Analysis: Relative, empirical analysis dependent on specific hardware, compiler, and language execution times. Gives exact execution metrics for a specific machine.
  • A Priori Analysis: Absolute, theoretical analysis independent of hardware/compiler environments. Uses mathematical asymptotic notations to provide approximate asymptotic bounds valid for all systems.

• Asymptotic Notations

  • Big-O Notation ($O$) - Upper Bound / Worst Case:
  • Definition: $O(g(n)) = \{f(n): \text{there exist positive constants } c \text{ and } n_0 \text{ such that } 0 \le f(n) \le c \cdot g(n) \text{ for all } n \ge n_0\}$.     
  • Omega Notation ($\Omega$) - Lower Bound / Best Case:
  • Definition: $\Omega(g(n)) = \{f(n): \text{there exist positive constants } c \text{ and } n_0 \text{ such that } 0 \le c \cdot g(n) \le f(n) \text{ for all } n \ge n_0\}$.     
  • Theta Notation ($\Theta$) - Asymptotically Tight Bound:
  • Definition: $\Theta(g(n)) = \{f(n): \text{there exist positive constants } c_1, c_2 \text{ and } n_0 \text{ such that } 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ for all } n \ge n_0\}$.     
  • Little-o ($o$) and Little-omega ($\omega$) - Loose Bounds:
  • $f(n) \in o(g(n))$ implies $f(n)$ grows strictly slower than $g(n)$ (e.g., $7n + 8 \in o(n^2)$).
  • $f(n) \in \omega(g(n))$ implies $f(n)$ grows strictly faster than $g(n)$ (e.g., $4n + 6 \in \omega(1)$).     

• Mathematical Properties of Asymptotic Notations

  • General: If $f(n) \in O(g(n))$, then $a \cdot f(n) \in O(g(n))$ for constant $a > 0$ (e.g., $f(n) = 2n^2 + 5 \in O(n^2) \implies 7 \cdot f(n) = 14n^2 + 35 \in O(n^2)$). Applies to $\Omega$ and $\Theta$.
  • Transitive: If $f(n) \in O(g(n))$ and $g(n) \in O(h(n))$, then $f(n) \in O(h(n))$ (e.g., $n \in O(n^2)$ and $n^2 \in O(n^3) \implies n \in O(n^3)$). Applies to $\Omega$ and $\Theta$.
  • Reflexive: $f(n) \in O(f(n))$, $f(n) \in \Omega(f(n))$, and $f(n) \in \Theta(f(n))$.
  • Symmetric: $f(n) \in \Theta(g(n)) \iff g(n) \in \Theta(f(n))$. (Applies exclusively to $\Theta$ notation).
  • Transpose Symmetric: $f(n) \in O(g(n)) \iff g(n) \in \Omega(f(n))$.
  • Sum Rule: If $f(n) \in O(g(n))$ and $d(n) \in O(e(n))$, then $f(n) + d(n) \in O(\max(g(n), e(n)))$ (e.g., $n + n^2 \in O(n^2)$).
  • Product Rule: If $f(n) \in O(g(n))$ and $d(n) \in O(e(n))$, then $f(n) \cdot d(n) \in O(g(n) \cdot e(n))$ (e.g., $n \cdot n^2 = n^3 \in O(n^3)$).

• Mathematical Analysis of Non-Recursive & Recursive Algorithms

  • Selection Sort Analysis (Non-Recursive):
  • Basic operation: Comparison inside inner loop.
  • Inner loop sum: $S(i) = \sum_{j=i+1}^{n-1} 1 = (n - 1) - (i + 1) + 1 = n - 1 - i$
  • Total Comparisons: $C(n) = \sum_{i=0}^{n-2} S(i) = \sum_{i=0}^{n-2} (n - 1 - i) = \frac{n(n - 1)}{2} \in O(n^2)$
  • Factorial Analysis (Recursive):
  • Recurrence relation: $T(n) = T(n - 1) + 3$ with base case $T(0) = 1$
  • Expansion: $T(n) = T(n - 1) + 3 = T(n - 2) + 6 = T(n - k) + 3k$
  • For $k = n$: $T(n) = T(0) + 3n = 1 + 3n \in O(n)$

Python Language Architecture & Environment

• Overview & History

  • General-purpose, interpreted, interactive, high-level, object-oriented language created by Guido van Rossum at Centrum Wiskunde & Informatica (CWI) in the Netherlands; released in 1991.
  • Named after the BBC comedy series "Monty Python's Flying Circus".
  • Widely adopted across industry giants: Google, YouTube, BitTorrent, Intel, Cisco, HP, IBM, Facebook, Maya, iRobot, NASA.

• Compiler vs. Interpreter Execution   | Parameter | Compiler | Interpreter |   | :--- | :--- | :--- |   | Input Processing | Takes entire program at once | Takes single instruction at a time |   | Intermediate Code | Generates intermediate object code | Generates no intermediate object code |   | Execution Speed | Faster conditional control execution | Slower execution |   | Memory Requirement | Higher (stores object code) | Lower |   | Compilation Requirement | Program compiled once for execution | Translated line-by-line during runtime |   | Error Display | Displays all errors after scanning full code | Displays error immediately per line interpreted |   | Examples | C, C++, Java Compilers | Python |

• Python Execution Modes

  • Interactive Mode: Executed via Python Shell/prompt (>>>). Instructions evaluate immediately line-by-line. Ideal for quick testing and exploration; code cannot be saved.
  • Script Mode: Python code written and saved in text files with a .py extension. Reusable, editable, and executed in batch.
  • IDLE: Integrated Development Environment providing interactive shell and script editing with integrated debugging tools.

• Lexical Rules and Code Syntax

  • Identifiers: Names assigned to variables, functions, classes, or modules.
  • Valid characters: Combination of uppercase/lowercase letters (A-Z, a-z), digits (0-9), and underscores (_).
  • Constraints: Cannot begin with a digit; cannot use keywords; special symbols (!, @, #, $, %) are forbidden.
  • Case-sensitive: Num, NUM, and num are distinct identifiers.
  • Keywords: 35 reserved words that define Python structure: False, None, True, and, as, assert, break, class, continue, def, del, elif, else, except, finally, for, from, global, if, import, in, is, lambda, nonlocal, not, or, pass, raise, return, try, while, with, yield.
  • Indentation: Replaces traditional {} block delimiters used in C/C++/Java. Identical indentation levels denote a code block.
  • Comments: Single-line comments begin with #. Multi-line comments require # on every line.
  • Docstrings: Documentation strings declared using triple quotes ("""...""" or '''...''') as the first line in a module, class, or function. Accessible programmatically via func_name.__doc__.
  • Quotations: Supports single ('), double ("), and triple (''' or """) quotes to define string literals.

Variables, Data Types, Expressions, and Operators

• Variables and Dynamic Assignment
  • Variables act as named storage containers referencing data in memory. No type declaration is required.
  • Single assignment: counter = 45
  • Simultaneous identical assignment: a = b = c = 100
  • Multiple assignment: `a, b, c = 2, 4,