Study sheet: Problem Solving and Algorithm Analysis

📋 Course Outline

1. Computer Problem-Solving Methodology
2. Requirements and Problem Analysis
3. Algorithms and Their Properties
4. Top-Down Algorithm Design
5. Program Implementation and Verification
6. Flowcharts and Pseudocode
7. Programming Languages and Translation
8. Algorithm Efficiency and Complexity
9. Complexity Analysis Examples

📖 1. Computer Problem-Solving Methodology

📝 Essential Points

• A computer is a dumb machine that operates strictly according to instructions and cannot perform useful tasks without software.

• The program-development process consists of:

  • requirements specification
  • problem analysis
  • algorithm design
  • implementation
  • testing and verification
  • documentation

💡 Memory Hook

Requirements → analysis → design → implementation → testing → documentation

📖 2. Requirements and Problem Analysis

🔑 Key Concepts & Definitions

• Requirements specification : states the problem, the required inputs and resources, the expected solution outputs, and the constraints or special conditions

📝 Essential Points

• For the apple-cost problem, the inputs are apple quantity in kilograms and cost per kilogram, the output is total cost in rupees, there are no stated constraints, and total cost equals cost per kilogram multiplied by quantity.

💡 Memory Hook

I-O-C-F: Inputs, Outputs, Constraints, Formulas

📖 3. Algorithms and Their Properties

🔑 Key Concepts & Definitions

• Algorithm : a complete, unambiguous, finite sequence of logical steps for solving a specific problem, independently of any programming language

★ Must-know

• An algorithm must have:
  • clear and unambiguous instructions
  • zero or more well-defined inputs
  • one or more well-defined outputs
  • finite termination
  • feasible operations
  • independence from programming code

Further detail

• 🔄 The average algorithm:
  1. reads a, b, and c
  2. computes their sum
  3. divides the sum by 3
  4. stores the result in d
  5. prints d
  6. ends

💡 Memory Hook

Algorithm = language-independent logic; program = coded implementation

📖 4. Top-Down Algorithm Design

📝 Essential Points

• A top-down algorithm design breaks a process into major steps: get the data, perform computations, and display the result, while requiring correctness, finiteness, and efficiency.

• 🔄 The factorial algorithm:

  1. initializes factorial = 1 and i = 1
  2. reads n
  3. multiplies factorial by i while i ≤ n
  4. increments i
  5. prints factorial

💡 Memory Hook

Get data → perform computations → display result

📖 5. Program Implementation and Verification

🔑 Key Concepts & Definitions

• Program testing : the process of executing a program to demonstrate its correctness
• Program verification : the process of ensuring that a program meets user requirements

📝 Essential Points

• Program documentation includes in-line comments and separate external files, helping others modify the program and helping the original programmer understand it later.

💡 Memory Hook

Translate logic → map flowchart → write source code → test → release

📖 6. Flowcharts and Pseudocode

🔑 Key Concepts & Definitions

• Flowchart : a graphical representation of an algorithm’s logic paths and operation sequence used to analyze and plan a solution systematically
• Pseudocode : an informal, abstract, English-like description of an algorithm that represents operations in execution order without using actual programming syntax

★ Must-know

• Flowchart symbols include: the oval terminator for start and end, the parallelogram data symbol for input and output, the process symbol for actions, the decision symbol for branching, arrows for flow direction

Further detail

📌 A = 10 assigns the value 10 to A, whereas A == 10 tests whether A equals 10.

💡 Memory Hook

Flowcharts show logic pictorially; pseudocode describes it in readable text

📖 7. Programming Languages and Translation

★ Must-know

📌 Low-level languages are close to hardware and machine-dependent, whereas high-level languages are easier to read and more portable across platforms.

• 🔄 The C compilation process applies:
  1. preprocessor
  2. compiler
  3. assembler
  4. linker
  5. loader
  6. execution

📌 A compiler translates the entire source program before execution, whereas an interpreter translates and executes instructions line by line.

Further detail

• Machine-level language consists entirely of binary instructions made of 1s and 0s and executes directly on computer hardware without a compiler or interpreter.

• Assembly language uses mnemonics such as ADD, SUB, INR, DCR, and CMP and must be translated into machine code by an assembler.

💡 Memory Hook

Compiler translates the whole program; interpreter translates line by line

📖 8. Algorithm Efficiency and Complexity

🔑 Key Concepts & Definitions

• Time complexity : measures the time or number of constant-time execution steps required by an algorithm as a function of input size n

★ Must-know

📐 Formula — Space complexity is expressed as $S(p) = A + S_p(I)$, where A is fixed space and $S_p(I)$ is variable space dependent on the problem instance.

• Complexity cases measure: minimum operations in the best case, expected behavior across possible inputs in the average case, maximum operations in the worst case

• For linear search, the best case has complexity Θ(1) when the item is first, while the worst case has complexity Θ(n) when the item is absent and every element is compared.

Further detail

📐 Formula — For adding two n-bit integers, the time requirement is $t(N) = c \cdot n$, so computational time grows linearly with input size.

💡 Memory Hook

Time and space → best, average, worst → asymptotic analysis

📖 9. Complexity Analysis Examples

📝 Essential Points

📐 Formula — For single-loop summation, the exact time cost is $T(n) = 2n + 3$ and its asymptotic time bound is $O(n)$; its space bound is also $O(n)$ because of the array.

📐 Formula — For matrix addition, the exact time cost is $T(n) = 2n^2 + 2n + 2$ and its time and space bounds are both $O(n^2)$.

📐 Formula — For matrix multiplication, the exact time cost is $T(n) = 2n^3 + 3n^2 + 2n + 2$, its time bound is $O(n^3)$, and its space bound is $O(n^2)$.

💡 Memory Hook

Summation O(n) → matrix addition O(n²) → matrix multiplication O(n³)

📊 Synthesis Tables

Compiler and Interpreter

Dimension	Compiler	Interpreter
Translation	Translates the entire program before execution	Translates and executes line by line
Error detection	After compiling the entire program	Immediately after translating each line
Execution speed	Slower analysis but faster execution	Faster analysis but slower execution
Intermediate code	Generates object code and needs more memory	Generates no intermediate object code