Introduction to Problem Solving

di★
n
Dr Isaac Olúwafé.mi E.lé.sè.moyò.
u
x M
O u . wò. University, Ilé.-Ifè.
. báfé.mi Awóló
L
★
June 2, 2026
Problems

▶ A problem is a task to be carried out.

▶ A gap between what is happening now (current state) and
what we want (desired state). di★
n
Mu
▶ a problem is an obstacle to overcome or some question to
x
★ Lu
answer. Once the question is answered or the obstacle
circumvented, the problem is solved and we can declare
victory and move on to the next one

2/23
Traffic congestion in a busy city like Lagos: Vehicles waste time
and fuel at junctions. A computer system could use sensors and
algorithms to adjust traffic lights dynamically.

di★
n
x Mu
★ Lu

Figure:

3/23
Real-World Domains

Healthcare: Long wait times for patients or inaccurate diagnostic

tracking.

di★
n
x Mu
★ Lu
Environment: Inefficient waste management or high energy
consumption in cities.

4/23
How to identify problems

▶ Observe everyday frustrations or inefficiencies.

di★
n
▶ Ask: What is not working well? What wastes
Mu
time/money/resources? Who is affected?
x
Lu
▶ Look for repeatable patterns that data or rules can model.
★

5/23
Problem Definition and Analysis

Once identified, clearly define the problem, then analyse it by

breaking it into smaller parts.
Steps in problem definition and analysis:
▶ Understand the current state — What is happening now?

i★
▶ Define the goal — What should the desired outcome be?
d
n
▶ List constraints — Time, budget, hardware limits, rules.
x Mu
▶ Break it down (decomposition) — Divide into
★ Lu
sub-problems (e.g., input, processing, output).
▶ Identify inputs and outputs — What data goes in? What
result comes out?
▶ Consider edge cases — What happens with unusual inputs
(empty list, very large numbers)?
▶ Model it — Use diagrams, flowcharts, or simple math.

6/23
Example: Cook Noodles
▶ Current state: You are hungry and have no prepared food.
▶ Goal: To have a bowl of fully cooked, seasoned, and
safe-to-eat noodles ready for consumption within the allotted
time.

i★
▶ Inputs: 1 pack of instant noodles, 500ml of water, seasoning
d
packets, A pot or heat-safe bowl, a stove or electric kettle, a
n
Mu
fork/spoon, Electricity or gas for heating, Cooking
x
instructions.
★ Lu
▶ Output: A hot, edible meal.
▶ Analysis:
▶ Heat water until it reaches the boiling point (100°C).
▶ Submerge noodles in boiling [Link] for the chemical
change (hydration/softening) to occur.
▶ Drain excess water and
▶ add seasoning.

7/23
Example: Build a simple calculator for two numbers

▶ Current state: Students do manual addition/subtraction

(error-prone).
i★
▶ Goal: Program that takes two numbers and an operator (+,
d
-, *, /) and gives the result. n
x Mu
▶ Inputs: Two numbers + operator.
L uor error message (e.g., divide by zero).
▶
★
Output: Correct result
▶ Analysis: Need to handle different data types (integers vs.
floats), validate input, and manage exceptions.

8/23
Designing a student attendance system

▶ Problem: Manual roll calls waste time and allow proxy

attendance.
di★
n
▶ Defined: Create a system using ID cards or biometrics to mark
Mu
and store attendance automatically.
x
Lu
▶ Analysis: Sub-problems include user authentication, database
★
storage, report generation, and handling network failures.

9/23
Characteristics of Well-Defined Problems

i★
A well-defined problem has clear starting conditions, a clear goal,
d
n
and known rules or operations to reach the solution. It usually has
Mu
one (or a verifiable) correct answer and follows structured steps
x
called algorithm.
★ Lu

10/23
Key characteristics

▶ Clear initial state and goal.

di★
▶ Known set of possible actions or rules.
n
Mu
▶ Definite way to check if the solution is correct.
x
Lu
▶ Often solvable by an algorithm (step-by-step procedure).
★

11/23
Examples of well-defined problems

▶ Sorting a list of 100 student names alphabetically.

di★
▶ Finding the sum of numbers from 1 to n.
n
Mu
▶ Checking if a number is prime.
x
Lu
▶ Calculating the shortest path in a map with fixed roads
★

12/23
Well-defined vs. Ill-defined (poorly defined) problems

Aspect Well-Defined Ill-Defined (Poorly Defined)

i★
Goal Clear (e.g., "sort list A to Z") Vague (e.g., "make the app

Known inputs and rules n

d user-friendly")
Starting point
Structured steps orM
u Unclear or changing
Solution path
u x algorithm Many possible paths, no sin-

Verifiability
L
★ correctness
Easy to check
gle "correct" way
Subjective or hard to measure

13/23
Ill-Defined Example - Improve traffic in Lagos - too broad.

i★
Well-defined version: "Given current traffic data from 50 junctions,
d
n
minimize average waiting time by adjusting signal timings every 5
minutes."
x Mu
★ Lu

Well-defined problems are ideal for computer programs because we

can write precise code.

14/23
Introduction to Solvable vs. Unsolvable Problems

In computing, a solvable (decidable) problem has an algorithm that

always gives the correct answer in finite time for any input.
di★
n
x Mu
★ Lu
An unsolvable (undecidable) problem has no such algorithm that
works for all cases.

15/23
Solvable examples

▶ Sorting any list of numbers.

▶ Searching for a word in a document.
di★
n
Mu
▶ Calculating factorial or Fibonacci numbers (with care for large
x
Lu
values).
★
▶ Determining if a number is even.

16/23
Unsolvable problems

The most famous is the Halting Problem (proven by Alan Turing in

1936): Given any program and any input, will the program halt

i★
(finish) or run forever (infinite loop)?
d
n
x Mu
★ Lu
No general algorithm can solve this for all possible programs and
inputs.

17/23
Some unsolvable problems are not unsolvable, they are simply non
computable.

di★
u n
x M
★
limL3xu2 + 5x − 4 =
3
x →∞ 2x 2 −x +1 2

18/23
▶ Some programs clearly halt (print "Hello" and stop).
▶ Some clearly loop forever (while true: print "loop").
di★
▶ But for arbitrary programs, we cannot always predict without
n
Mu
running them — and running them might take forever if they
x
loop!
★ Lu

19/23
Introduction to Computational Complexity Basics

Even among solvable problems, some are easy (fast) and some are
extremely hard (take too much time even on supercomputers).
Computational Complexity studies how the running time or
resources grow as the input size (n) increases. Polynomial time
di★
n
x Mu
Lu
(P): Problems solvable quickly — time grows like n, n2, n3, etc.
★
(practical for large n).

Examples: Sorting a list, finding shortest path in a map (with good

algorithms), multiplying two numbers.

20/23
NP (Nondeterministic Polynomial): Problems where a proposed
solution can be verified quickly (in polynomial time), but finding
the solution may be very hard. Example: Sudoku — checking if a

di★
n
x Mu
★ Lu
filled grid is correct is fast, but solving a hard puzzle by
trial-and-error can take enormous time.

21/23
P vs NP question

▶ If P = NP, then every problem whose solution is easy to check

would also be easy to solve automatically.
di★
▶ Most experts believe P ̸= NP — some problems are inherently
n
hard.
x Mu
★ Lu
▶ Practical impact: If P=NP, many optimization tasks (logistics,
scheduling, cryptography) could become trivial, revolutionizing
computing. But it would also break most current encryption.

22/23
Everyday analogy

P: Finding your way home (easy to do and easy to verify). NP:

di★
n
x Mu
u 20 cities exactly once (Traveling
Finding the shortest routeLvisiting
★
Salesman Problem) — guessing a route is easy to check, but
finding the best one is hard for large numbers.

23/23
Problem-Solving Methods

di★
n
Isaac O. Elesemoyo
x Mu
★ Lu
June 2, 2026
Outlines

Algorithm

Actions in Algorithms

Control Flow of Algorithms

di★
n
Categories of Algorithms x Mu
★ Lu
Heuristics

Key Characteristics of Heuristics

Why Do We Need Heuristics?

What is an Algorithms?

▶ An algorithm is a finite, well-defined sequence of instructions

that transforms a set of inputs into a desired output.
Algorithms are the cornerstone of computer science — every
di★
program, database query, and machine-learning model
n
Mu
ultimately reduces to one or more algorithms working in
concert. x
★ Lu
▶ An algorithm is an ordered list of actions that describe how to
perform a task or solve a problem.
▶ Algorithms are an important concept in the study of computer
science, but they are broadly applicable.
Examples of Algorithm

▶ A recipe for making bread is an algorithm, even though

i★
making bread has nothing to do with computers
d
u n
▶ instructions for assembling a bookshelf
x M
▶ steps to operate a coffee
L u maker
▶ a list of things to ★
do in case of a fire
Actions in Algorithms

We have said that an algorithm is made up of a sequence of

actions, so we should say a little more on what an action actually
is. For our purposes, an action should:
di★
n
▶ be imperative: it is a command to do something
x Mu
▶ be feasible: the algorithm’s recipient has the ability to perform
it ★ Lu
▶ be self-explanatory: the algorithm’s recipient knows how to
perform it without further elaboration
Actions in Algorithms

From the criteria above, it should be apparent that an algorithm’s

recipient - that is, the person or thing that we expect will be
i★
following the algorithm - is of critical importance. For example,
d
n
Mu
raise your right hand is a perfectly reasonable action for most adult
x
humans. However, for a toddler who does not yet know right from
★ Lu
left, it is not an appropriate action, because it is not
self-explanatory. For a computer, it is not even a feasible action,
since computers do not typically have hands at all!
Control Flow of Algorithms
Algorithms can contain more than just actions to take; they can
also contain information on when to perform a given action, or
even how many times to perform an action. Consider the following
(very simple) algorithm for tightening a bolt.

di★
n
x Mu
★ Lu
Four Fundamental Characteristics

▶ Determinism — Given identical inputs, an algorithm always

produces identical outputs. There is no ambiguity in its
execution path.
i★
▶ Finiteness — The algorithm terminates after a bounded
d
n
number of steps. An infinite loop is not an algorithm.
x Mu
▶ Correctness (Soundness & Completeness) — It produces
★ Lu
the right answer for all valid inputs. If a solution exists, a
correct algorithm will find it.
▶ Optimality (context-dependent) — Many algorithms are
designed to find not just any solution, but the best possible
one, e.g., the shortest path or minimum cost.
Categories of Algorithms
Algorithms can be organised by their problem-solving strategy:
▶ Divide and Conquer — Split the problem into smaller
sub-problems, solve each recursively, then merge results.
Examples: MergeSort, QuickSort, Binary Search.
▶ Dynamic Programming (DP) — Solve overlapping

i★
sub-problems once and store results. Examples: Knapsack
Problem, Fibonacci, Bellman-Ford.
n d
Mu
▶ Greedy Algorithms — Make the locally optimal choice at each
x
★ Lu
step hoping to reach a global optimum. Examples: Dijkstra’s
shortest path, Huffman coding, Kruskal’s MST.
▶ Backtracking — Incrementally build a solution and abandon
(‘backtrack’) partial solutions that fail constraints. Examples:
N-Queens, Sudoku solver, graph colouring.
▶ Brute Force / Exhaustive Search — Try all possible solutions.
Guaranteed optimal but prohibitively slow for large inputs.
▶ Graph Algorithms — BFS, DFS, A*, Prim’s. Fundamental for
navigation, networking, and AI planning.
Heuristics
What is a Heuristic?

di★
A heuristic (from Greek ‘heuriskein’ — to discover) is a practical,
n
x Mu
experience-based technique that finds a good-enough solution
quickly, without the guarantee of optimality. Heuristics trade
★ Lu
mathematical certainty for computational speed.
Key Characteristics of Heuristics

▶ Approximation — Solutions are near-optimal, not proven

optimal.
▶ Speed — Dramatically faster than exact methods on large
instances. di★
n
Mu
▶ Domain-specific — Often incorporate expert knowledge or
x
★ Lu
empirical observations.
▶ Scalability — Remain practical as problem size grows to
thousands or millions of variables.
▶ No completeness guarantee — May fail to find any feasible
solution in some cases.
Why Do We Need Heuristics?

Many practically important problems are NP-hard: the Travelling

di★
Salesman Problem (TSP), vehicle routing, protein folding,
job-shop scheduling. For a 50-city TSP instance, an exhaustive
n
Mu
search would require evaluating approximately 3 × 102 routes -
x
★ Lu
more than the number of atoms in the observable universe. No
computer could solve this exactly in any reasonable timeframe.
Heuristics make such problems tractable.
Classic Heuristic Examples

▶ Nearest Neighbour (TSP) — Start at any city; always visit the

closest unvisited city next. Fast, but typically 20-25% above
optimal.
i★
▶ Chess centre control — ‘Control the centre’ is a heuristic: it
d
n
guides play without proving it leads to a win.
x Mu
▶ First-Come First-Served (FCFS) — Simple scheduling
Lu
heuristic; not optimal but fair and easy to implement.
★
▶ Avoid tolls / Take motorways — Route-planning rules of
thumb used before GPS optimisation.
▶ 80/20 Rule (Pareto Principle) — Focus on the 20% of causes
producing 80% of effects: a managerial heuristic.
Algorithmic vs Heuristic: A Detailed Comparison
The table below summarises the principal trade-offs between the
two paradigms across eight critical dimensions:

Aspect Algorithmic Heuristic

Guarantee Provides exact/optimal solu- No guarantee of optimality

i★May miss optimal or any so-

tion
Completeness
d
Always finds a solution if one
n lution
Mu
exists
Speed
x
Can be slow on large/complex Usually much faster

Scalability
instances
★ Lu
Poor for very large NP-hard Excellent for large-scale prob-
problems lems
Predictability Deterministic and repeatable Can be stochastic or variable
Resource Us- High memory/time for com- Lower resource requirements
age plex problems
Use Case Well-structured, smaller prob- Ill-structured, time-critical
lems problems
Examples Linear Programming, exact Genetic Algorithms, Simu-
TSP solvers lated Annealing
Overview

1. Linear Search
2. Binary Search
3. Bubble Sort
4. Factorial (Iterative) di★
n
5. Fibonacci Sequence
x Mu
6. Check Palindrome
★ Lu
7. Find Maximum
8. Reverse Array
9. Selection Sort
10. Insertion Sort
Linear Search: Textual Algorithm

1. Start from the first element of the array.

i★
2. Compare the current element with the target value.
d
3. un index.
If they are equal, return the current
M
4.
ux element.
Otherwise, move to the next
L
5. ★ of the array is reached.
Repeat until the end
6. If the target is not found, return -1.
1. Linear Search

Problem: Given an array A of n integers and target x , return

index of x or −1.

Algorithm 1 LinearSearch(A, x)
di★
for i ← 0 to n − 1 do n
if A[i] = x then
x Mu
return i
★ Lu
end if
end for
return −1
Binary Search: Textual Algorithm

1. Set the lower bound to the first index and the upper bound to
the last index.
i★
2. While the lower bound is not greater than the upper bound:
d
n
Mu
2.1 Compute the middle index.
x
2.2 If the middle element equals the target, return its index.

half. ★ Lu
2.3 If the middle element is less than the target, search the right

2.4 Otherwise, search the left half.

3. If the target is not found, return -1.
2. Binary Search
Problem: Search for x in a sorted array A.

Algorithm 2 BinarySearch(A, x)
low ← 0, high ← n − 1
while low ≤ high do
mid ← ⌊(low + high)/2⌋
di★
if A[mid] = x then n
return mid x Mu
Lu
else if A[mid] < x then
★
low ← mid + 1
else
high ← mid - 1
end if
end while
return −1
Bubble Sort: Textual Algorithm

1. Traverse the array repeatedly.

2. Compare each pair of adjacent elements.
di★
3. If the left element is greater than the right element, swap
them. u n
x M
4. u unsorted element moves to its
Continue until the largest
correct position. ★L
5. Repeat the process for the remaining unsorted portion.
6. Stop when the entire array is sorted.
3. Bubble Sort

Problem: Sort array A in ascending order.

Algorithm 3 BubbleSort(A)
for i ← 0 to n − 2 do
di★
for j ← 0 to n − i − 2 do n
x Mu
if A[j] > A[j + 1] then
Lu
swap A[j] ↔ A[j + 1]
★
end if
end for
end for
Factorial: Textual Algorithm

1. If the input number is 0, return 1.

di★
2. Initialize a variable called result to 1.
n
Mu
3. Multiply result by every integer from 1 to n.
x
4. L u result back into result.
Store each multiplication
5. ★ are completed, return result.
After all multiplications
4. Factorial (Iterative)

Problem: Compute n! for non-negative integer n.

Algorithm 4 Factorial(n)
if n = 0 then
return 1 di★
n
end if
x Mu
result ← 1
for i ← 1 to n do ★ Lu
result ← result ×i
end for
return result
Fibonacci Sequence: Textual Algorithm

1. If n is 0 or 1, return n.
2. Initialize two variables:
▶ a=0
di★
▶ b=1 n
x Mu
3. Repeatedly compute the next Fibonacci number as a + b.
L u
4. ★
Update a and b accordingly.
5. Continue until the n-th Fibonacci number is obtained.
6. Return the final value.
5. Fibonacci Sequence

Problem: Find the n-th Fibonacci number (F (0) = 0, F (1) = 1).

Algorithm 5 Fibonacci(n)
if n ≤ 1 then
return n
di★
end if n
a ← 0, b ← 1
x Mu
for i ← 2 to n do
temp ← a + b ★ Lu
a←b
b ← temp
end for
return b
Check Palindrome: Textual Algorithm

1. Set one pointer at the beginning of the string.

2. Set another pointer at the end of the string.
di★
3. Compare the characters at both positions.
n
4. If they differ, return false.
x Mu
5. u and the right pointer backward.
Move the left pointerLforward
6.
★
Repeat until the pointers meet or cross.
7. If all compared characters match, return true.
6. Check Palindrome

Problem: Check if string S is a palindrome.

Algorithm 6 IsPalindrome(S)
left ← 0, right ← length(S) - 1
while left < right do
di★
n
Mu
if S[left] ̸= S[right] then
return false x
end if
★ Lu
left ← left + 1
right ← right - 1
end while
return true
Find Maximum: Textual Algorithm

1. Assume the first element is the maximum value.

i★
2. Traverse the remaining elements of the array.
d
3. Compare each element with the
M uncurrent maximum.
4.
ux update the maximum value.
If a larger element is found,
L
5. Continue until all ★
elements have been examined.
6. Return the maximum value.
7. Find Maximum

Problem: Find the maximum element in array A.

Algorithm 7 FindMax(A)
max ← A[0]
di★
for i ← 1 to n − 1 do n
if A[i] > max then x Mu
max ← A[i]
★ Lu
end if
end for
return max
Reverse Array: Textual Algorithm

1. Place one pointer at the beginning of the array.

2. Place another pointer at the end of the array.
d
3. Swap the elements at both positions.i★
n
Mu
4. Move the left pointer one step right.
x
5. L
Move the right pointer uone step left.
6.
★
Repeat until the pointers meet or cross.
7. The array is now reversed.
8. Reverse Array

Problem: Reverse array A in-place.

Algorithm 8 ReverseArray(A)
left ← 0, right ← n − 1 di★
n
while left < right do
x Mu
swap A[left] ↔ A[right]
left ← left + 1★ Lu
right ← right - 1
end while
Selection Sort: Textual Algorithm

1. Start from the first unsorted position.

i★
2. Find the smallest element in the unsorted portion.
d
3. un element.
Record the position of this smallest
M
4.
ux element.
Swap it with the first unsorted
L
5. Move the boundary ★of the sorted portion one step forward.
6. Repeat until the entire array is sorted.
9. Selection Sort

Problem: Sort array using Selection Sort.

Algorithm 9 SelectionSort(A)
for i ← 0 to n − 2 do
minIndex ← i
di★
n
Mu
for j ← i + 1 to n − 1 do
x
if A[j] < A[minIndex] then
Lu
minIndex ← j
★
end if
end for
swap A[i] ↔ A[minIndex]
end for
Insertion Sort: Textual Algorithm

1. Begin with the second element of the array.

2. Store the current element as the key.
di★
3. Compare the key with elements to its left.
n
Mu
4. Shift larger elements one position to the right.
x
5. u position.
Insert the key into itsLcorrect
6.
★
Repeat for all remaining elements.
7. The array becomes sorted in ascending order.
10. Insertion Sort

Problem: Sort array using Insertion Sort.

Algorithm 10 InsertionSort(A)
for i ← 1 to n − 1 do
key ← A[i]
di★
n
Mu
j ←i −1
x
while j ≥ 0 and A[j] > key do
A[j + 1] ← A[j]
★ Lu
j ←j −1
end while
A[j + 1] ← key
end for
What is a Flowchart?

i★
▶ Visual representation of an algorithm or process
n d
▶ Uses standardized shapes connected by arrows
Mu
▶ Helps in planning, debugging, and explaining logic
x
Lu
▶ Independent of any programming language
★
Common Flowchart Symbols
Start / End

Oval/Terminator

Process Step

Rectangle
di★
n
x Mu
Lu
★Decision?

Diamond

Input / Output Arrow

Parallelogram
Flowchart Symbols & Their Meanings

Shape Purpose
Oval / Terminator i★
Start or End of the program
d
Rectangle n
Processing / Calculation step
Diamond x Mu
Decision (Yes/No question)
Parallelogram
★ Lu Input or Output
Arrow Direction of flow
Example 1: Check Even or Odd Number

Start

Read Number n

di★
n
x Mu
★ Lun mod 2 = 0?
Yes No

Print "Even" Print "Odd"

End
Example 2: Find Maximum of Two Numbers
Start

Read A and B

di★
n
x Mu Is A > B?

★ Lu
Yes No

Max = A Max = B

Print Max

End
Best Practices for Flowcharts

▶ Keep flow direction mostly top to bottom or left to right

▶ Use clear and concise labels di★
n
Mu
▶ Avoid crossing arrows when possible
x
Lu
▶ One flowchart should represent one clear process
★
▶ Test the logic before implementing in code
 di★
Heuristics Problem
M un
L ux
★
Travelling Salesman Problem (Nearest Neighbor)

Problem: Find a short route that visits every city exactly once and
returns to the starting city.
Textual Algorithm
1. Choose a starting city. di★
n
2. Mark the city as visited.
x Mu
3. L u city.
Find the nearest unvisited
4. Move to that city ★
and mark it as visited.
5. Repeat until all cities have been visited.
6. Return to the starting city.
Travelling Salesman Problem (Nearest Neighbor)

Algorithm 11 NearestNeighborTSP
current ← startCity
mark current as visited
di★
while unvisited cities exist do n
Mu
next ← nearest unvisited city
x
visit next
current ← next ★ Lu
end while
return to startCity
Knapsack Problem (Greedy Heuristic)

Problem: Select items that maximize value without exceeding

capacity.
Textual Algorithm
di★
n
1. Compute value-to-weight ratio for each item.
x Mu
2. Sort items in descending order of ratio.
3. Lu the highest ratio.
Pick items starting★from
4. Add an item only if it fits in the remaining capacity.
5. Continue until no more items can be added.
Knapsack Problem (Greedy Heuristic)

Algorithm 12 GreedyKnapsack
Sort items by value/weight ratio
for each item do
di★
if item fits in knapsack then n
add item
x Mu
Lu
update remaining capacity
★
end if
end for
return selected items
Knapsack Problem

Problem:
You have a knapsack that can carry at most 15 kg.
The available items are:
Item Weight (kg)
d i★ ($)
Value
n 40
Mu
A 2
B x3 50
C
★Lu 5 100
D 4 60
E 6 120

Select items to maximize total value without exceeding the

knapsack capacity.
Knapsack Example Solution
Step 1: Compute Value-to-Weight Ratio

Item Weight Value Value/Weight

A 2 40 20
B 3 50 16.67
C 5 100 20
D 4 60
di★ 15
n
Mu
E 6 120 20

Step 2: Select Highest L

x
u First
Ratios
▶ Select A (Weight ★
= 2, Value = 40)
▶ Select C (Weight = 5, Value = 100)
▶ Select E (Weight = 6, Value = 120)
Total Weight = 13 kg
Total Value = $260
Remaining Capacity = 2 kg
Final Solution: {A, C, E}
Greedy Knapsack Heuristic

Algorithm 13 GreedyKnapsack(items, Capacity)

for each item do
ratio ← value / weight
end for
Sort items in descending order of ratio
totalWeight ← 0 di★
n
totalValue ← 0
x Mu
Lu
for each item in sorted order do
★
if totalWeight + [Link] ≤ Capacity then
Select item
totalWeight ← totalWeight + [Link]
totalValue ← totalValue + [Link]
end if
end for
return selected items, totalValue
Graph Coloring (Largest Degree First)

Problem: Assign colors to vertices so that adjacent vertices have

different colors.
Textual Algorithm
di★
n
1. Sort vertices by decreasing degree.
x Mu
2. Select the highest-degree uncolored vertex.
L u color.
3. ★
Assign the smallest available
4. Repeat for the remaining vertices.
5. Continue until all vertices are colored.
Graph Coloring (Largest Degree First)

Algorithm 14 LargestDegreeColoring
Sort vertices by degree
di★
for each vertex do n
x Mu
Assign lowest valid color
end for
★ Lu
return coloring
Job Scheduling (SPT Heuristic)

Problem: Minimize average waiting time for jobs.

Textual Algorithm
di★
1. Determine processing time for each job.
n
Mu
2. Sort jobs by increasing processing time.
x
3. u first.
Schedule the shortest job
L
4. ★ order.
Execute jobs in sorted
5. Compute total waiting time.
Job Scheduling (SPT Heuristic)

Algorithm 15 ShortestProcessingTime
Sort jobs by processing time
di★
n
Mu
for each job do
schedule job x
end for
★ Lu
return schedule
Route Finding (A* Search)

Problem: Find a path from a start node to a goal node.

Textual Algorithm

i★
1. Place the start node in the open list.
d
2. unestimated cost.
Select the node with the lowest
M
3.
ux
Expand its neighboring nodes.
L
4. ★ and heuristic estimate.
Compute actual cost
5. Update the best path information.
6. Repeat until the goal node is reached.
Route Finding (A* Search)

Algorithm 16 AStar
add start node to OpenList
while OpenList is not empty do
current ← node with lowest f-cost
if current = goal then
di★
return path n
end if
x Mu
Lu
for each neighbor do
★
update path cost
compute heuristic estimate
add neighbor if necessary
end for
end while
return failure
Thank You!

di★
n
Mu
Questions?
x
★Lu
Analogies: Definition, Structure, and Use
COS 102 lecture notes, reorganized and lightly expanded

1. What Is an Analogy?
An analogy is a comparison between two different things, based on shared similarities, used to explain or clarify a concept. It
maps a familiar idea (the source) onto an unfamiliar one (the target) so the structure of the familiar idea carries over.
Example: "The brain is like a computer" — this helps people reason about how the brain stores and processes information by
borrowing the logic of a system they already understand.
Note: An analogy is a reasoning tool, not a proof. It transfers plausibility from the source domain to the target domain;
it does not establish that the target domain actually works the same way. Treat conclusions drawn purely from analogy
as hypotheses to verify, not settled facts.

2. Why We Use Analogies

• Simplify complex ideas: e.g., electricity flowing through wires is like water flowing through pipes.
• Improve understanding: concepts connected to familiar experience are easier to grasp.
• Enhance memory: abstract ideas become concrete, often visual, scenarios.
• Support problem-solving: solutions to known problems can be transferred to structurally similar new problems.
• Aid teaching, persuasion, and innovation more broadly — analogies are a standard tool in explanation and in
generating new ideas.

3. Structure of an Analogy
• Source domain: the familiar concept.
• Target domain: the concept being explained.
• The mapping: connects features of the source to corresponding features of the target.
Worked example: "An atom is like a solar system."

Solar System (source) Atom (target)

Sun at center Nucleus at center
Planets orbit sun Electrons orbit nucleus

Second worked example: "The brain is like a computer."

Computer (source) Brain (target)

Stores data Stores memories
Processes information Processes thoughts
Has input devices Receives sensory input
Produces output Produces actions

Third example — Source vs. Target domain: "Computer memory is like a library."

Library (source) Computer Memory (target)

Books Data
 Library (source) Computer Memory (target)
Shelves Storage
Librarian Operating system

4. Analogy vs. Metaphor

Both compare two unlike things, but they differ in purpose and rigor.

Analogy Metaphor

Function Explains similarities in detail (tool for States one thing is another, for effect
reasoning) (figure of speech)
Purpose Used for understanding Used mainly for expression
Nature Logical comparison Figurative comparison

5. Traditional Types of Analogies

The lecture lists eight traditional types: Functional, Structural, Verbal, Symbolic, Simple, Extended, Literal, and Figurative.
Each is expanded below with its defining feature, an example, and the related sub-types it overlaps with (from the extended
list in Section 7).

5.1 Simple Analogy

A straightforward, single-point comparison between two things.
• Example: "A teacher is like a guide." Similarity: both provide direction.

5.2 Structural Analogy

Based on similarity in structure, organization, or relationships among parts, rather than similarity in appearance or purpose.
• Example: Atom : Solar System — both have a central body surrounded by orbiting bodies.

5.3 Functional Analogy

Based on similarity in function, purpose, or role — what the thing does, not what it looks like or how it's arranged internally.
• Example: Heart : Pump — both circulate fluids.

5.4 Verbal Analogy

Expressed through words and the relationships between terms. Common in reasoning and aptitude tests, written as A : B :: C
: D ("A is to B as C is to D").
• Example: Doctor : Hospital :: Teacher : School — meaning "a doctor works in a hospital just as a teacher works in a
school."
• Example: Bird : Fly :: Fish : Swim — "a bird flies just as a fish swims."

5.5 Symbolic Analogy

Uses symbols, images, signs, or representations to convey meaning, often mapping an abstract quality onto a concrete or
visual stand-in.
• Example: "Time is money." Similarity: both are valuable, limited resources.

5.6 Extended Analogy

Develops multiple points of comparison between the same two domains, rather than stopping at one similarity (contrast with
Simple Analogy above).
5.7 Literal Analogy
Compares things from the same category or class — the two items being compared genuinely belong to the same kind of
thing, which is what makes the comparison direct rather than figurative.

5.8 Figurative Analogy

Compares things from different categories, relying on a resemblance in role, feeling, or structure rather than shared category
membership. This is where analogy shades into metaphor (Section 4).

6. How the Traditional Types Relate to Each Other

The lecture cross-references the eight traditional types against a second, finer-grained set of relationship types (covered in
Section 7). This table summarizes that mapping.

Type Based on Related finer-grained types

Functional Similarity in function, purpose, or role Object-to-Function, Cause-to-Effect,
Effort-and-Result
Structural Similarity in structure, organization, or Part-to-Whole, Source-to-Product,
relationships among parts Object-and-Classification
Verbal Words and relationships between terms; Antonyms, Opposite, Characteristic,
common in aptitude tests Object-and-Classification
Symbolic Symbols, images, signs, or representations Affective, Opposite, Characteristic (when
conveying meaning symbols carry ideas/emotions)
Simple A single-point comparison between two Characteristic, Object-to-Function,
things Antonyms, Part-to-Whole
Extended Multiple points of comparison developed Simple, Extended
from one analogy
Literal Compares things from the same category Antonyms, Opposite, Object-and-
Classification

7. Other (Finer-Grained) Relationship Types

These describe the specific kind of relationship the mapping relies on, and cut across the eight traditional types above.
• Source to Product: creator → product relationship.
• Antonyms: opposite meanings.
• Characteristic: a shared attribute or quality.
• Object to Function: same purpose or use.
• Part to Whole: component → system relationship.
• Affective: shared emotional impact.
• Cause to Effect: similar action → similar outcome.
• Effort and Result: work invested → achievement gained.
• Object and Classification: item → category relationship.
• Opposite: contrasting pairs.
• Simple Extended: multiple parallel comparisons built out from one base analogy.
Worked examples:
 Type Example Why it works
Source to Product A sculptor molds their clay similarly to Highlights the relationship between a
how a baker kneads their dough. craftsperson, their raw material, and the
final product created through skill and
effort.
Antonyms The weather went from hot to cold as Hot and cold are direct opposites along a
quickly as an elevator goes up and down. temperature scale, like up and down are
direct opposites along a vertical axis.

8. Analogical Reasoning
Analogical reasoning is the process of drawing conclusions based on similarities. It follows a general pattern: A is related to
B; C is related to what?
Example: Doctor : Hospital :: Teacher : ? → Answer: School.
Reasoning: a doctor works in a hospital just as a teacher works in a school — the underlying relation ("works in") is held
constant while the terms change.
Note: This is the same logical form used in verbal analogy questions (Section 5.4) and in IQ/aptitude testing. Formally:
if relation R holds between A and B, and the same relation R plausibly holds between C and an unknown D, analogical
reasoning proposes D as the term that completes it. The reasoning is only as strong as the claim that R genuinely
transfers from (A,B) to (C,D).

9. Analogy Across Domains

9.1 Mathematics
• Number line = Straight road.
• Equation = Balanced scale.

9.2 Science
• Electric current = Water flow.
• DNA = Blueprint.

9.3 Computer Science

• Database = Filing cabinet.
• Internet = Postal system.
• Memory = Library (expanded in Section 3).
• Abstraction = Driving a car.
These computer-science analogies are especially useful for teaching Computer Science, Software Engineering, and Artificial
Intelligence, because they connect unfamiliar system-level ideas to everyday familiar ones.

9.4 Everyday Life

Example 1 — Car:
• Driver sees: steering wheel, accelerator, brake pedal.
• Hidden details: engine operation, fuel injection, transmission system, electronic control units.
• Analogy: Driving a car is similar to using a computer — users interact with controls without needing to understand
the internal mechanisms. This is the same idea as the Abstraction = Driving a Car analogy above.
Example 2 — ATM Machine:
• User actions: withdraw cash, check balance, transfer funds.
• Hidden processes: database access, authentication, encryption, network communication.
 • Analogy: An ATM is like a vending machine for banking services.
Note: Both examples illustrate the same underlying computer-science idea: abstraction hides implementation detail
behind a simple interface. The analogy itself is doing double duty — it's both an example of a Functional/Structural
analogy and an informal description of what abstraction means.

10. Database Analogy (Worked Structural Mapping)

Physical filing system (source) Database (target)
Drawer Table
Folder Record
Document Data Item

11. Errors in Using Analogies

• False Analogy: comparing two things that are not actually alike in the relevant way.
• Over-Complication: if the analogy is harder to understand than the original concept, it fails.
• Cultural Misalignment: using an analogy (e.g., a sports analogy like baseball) with an audience unfamiliar with it.
• Over-stretching: pushing the comparison too far until it breaks down.

12. Advantages
• Easier learning: makes difficult ideas understandable.
• Better retention: people remember familiar comparisons.
• Creative thinking: helps generate new ideas.
• Knowledge transfer: the ability to take understanding from one familiar situation and apply it to a new, unfamiliar
one.

13. Limitations
• Oversimplification: many analogies ignore important details.
• Incomplete comparison: an analogy usually highlights only some aspects of a concept.
• Potential misconceptions: two things may appear similar but differ significantly.
Note: Sections 11 and 13 overlap: Over-Complication and Cultural Misalignment are failure modes in how an analogy
is deployed, while Oversimplification and Incomplete Comparison are structural limits of analogy as a reasoning
method — even a well-chosen analogy will hide some of the target's real behavior.

14. Summary
• Analogies connect familiar ideas with unfamiliar concepts, making learning clearer and more effective.
• Analogies are "cognitive bridges" between the known and the unknown.
• They are powerful tools for teaching, persuasion, and innovation.
• Rule of thumb: use familiar examples, keep it simple, and make sure the underlying logic actually holds.
Comprehensive Guide to Analogical
Reasoning
Structure, Classifications, and Domain Applications

1. Introduction to Analogy

An analogy is a powerful cognitive tool and linguistic device that establishes a comparison between two
different things based on their underlying similarities. Its primary function is to explain, clarify, or conceptualize
an unfamiliar idea by mapping it onto a familiar one.

Analogies serve as foundational pillars across multiple domains of human intellect and expression, including
teaching, learning, professional communication, structured problem-solving, and scientific discovery.

Core Example: "The brain is like a computer."

This classical analogy aids individuals in conceptualizing complex biological mechanisms by projecting
the familiar architectural functional components of modern computing systems onto human neurology.

Source System (Computer) Target System (Human Brain)

Stores data: Hard drives, solid-state media, and Store memories: Neural networks and synaptic
RAM hold digital information systematically. connections encode and preserve experiences.

Processes information: The Central Processing Unit Processes thoughts: The cerebral cortex actively
(CPU) executes logical operations and computations. integrates cognitive tasks, reason, and analytics.

Has input devices: Keyboards, mice, and sensors Receive sensory input: Eyes, ears, skin, and other
receive telemetry and commands. sensory organs gather environmental data.

Produces output: Monitors, speakers, and printers Produces actions: Motor commands result in
deliver processed data visually or physically. physical movement, speech, and behavioral
responses.

2. The Formal Structure of an Analogy

To construct or evaluate an analogy rigorously, it must be broken down into three essential components:

• Source Domain: The familiar concept or system that acts as the baseline reference point.

• Target Domain: The novel or complex concept currently being examined or explained.

Masterclass: Analogical Reasoning Page 1 of 5

 • The Mapping: The explicit structural or functional alignment connecting features from the Source Domain
directly to the Target Domain.

Structural Case Study: Rutherford-Bohr Model (An Atom is like a Solar System)

Source Domain: Solar System Target Domain: Atom

Sun located at the absolute center Nucleus located at the absolute center

Planets orbit continuously around the sun via Electrons orbit continuously around the nucleus via
gravitational pull electrostatic forces

3. Analogical Reasoning

Analogical reasoning is the specific cognitive process through which logical conclusions are systematically
drawn based on identified similarities between relational networks.

The General Pattern

Element A is related to Element B

Element C is related to [ ? ] in the exact same manner

This is often mathematically and textually represented as: A : B :: C : D (read as "A is to B as C is to D").

Practical Aptitude Example:

Doctor : Hospital :: Teacher : ?
Answer: School

Reasoning: The relationship established in the first pair is [Professional] : [Primary Workplace]. A doctor
works inside a hospital; applying this exact relational logic to the target domain dictates that a teacher
works inside a school.

4. Classifications and Types of Analogies

Analogies are categorized into distinct structural frameworks depending on how the comparison is structured
and expressed.

Masterclass: Analogical Reasoning Page 2 of 5

 Traditional Analogy Related Variants /
Description
Type Classifications

Functional Analogy Based strictly on similarity in function, Object-to-Function, Cause-to-

underlying purpose, or operational role. Effect, Effort-and-Result

Structural Analogy Based on structural similarities, corporate/ Part-to-Whole, Source-to-

physical organization, or relationships among Product, Object-and-
constituent parts. Classification

Verbal Analogy Expressed through specific vocabulary Antonyms, Opposites,

relationships and linguistic linkages. Common in Characteristics, Object-and-
psychological aptitude exams. Classification

Symbolic Analogy Employs symbols, graphical icons, signs, or Affective, Opposites,

abstract representations to convey cross-cutting Emotional/Ideological
meaning. Representations

Simple Analogy A focused, singular, single-point comparison Characteristic, Object-to-

between two specific things. Function, Antonyms, Part-to-
Whole

Extended Analogy Develops and sustains multiple overlapping Simple Extended, Allegory
points of complex structural comparison
throughout a narrative.

Literal Analogy Compares entities that belong natively to the Antonyms, Opposites, Object-
exact same categorical class. and-Classification

Deep Dive: Targeted Exemplars

Analogy Sub-Type Exemplar Expression Why does the comparison hold?

Source to Product "A sculptor molds their clay similarly Highlights the exact operational
to how a baker kneads their dough." relationship between a skilled artisan,
their unformed raw material, and the final
tangible asset generated through
disciplined manual effort.

Antonyms "The weather went from hot to cold Hot and cold are polar opposites along a
as quickly as an elevator goes up linear temperature scale, directly mirroring
and down." how up and down represent opposing
physical directions along a vertical axis.

Masterclass: Analogical Reasoning Page 3 of 5

5. Domain-Specific Cross-Disciplinary Analogies

5.1 Mathematics

• Number Line = Straight Road: Visualizes values as discrete physical milestones along a uniform,
continuous linear path.

• Equation = Balanced Scale: Reinforces the requirement that any mathematical modification executed on
one side must be perfectly mirrored on the other to preserve equilibrium (LHS = RHS).

5.2 Natural Sciences

• Electric Current = Water Flow: Voltage acts as water pressure, current as the volumetric flow rate of
water, and resistors function like narrow constrictions inside a pipe.

• DNA = Blueprint: Conceptualizes deoxyribonucleic acid not simply as chemical bases, but as a dense,
structured master architectural plan containing all necessary instructional specifications for building an
organism.

5.3 Computer Science

• Database = Filing Cabinet: Represents tables, indices, and keys as structured drawers, folders, and
indexed files.

• Internet = Postal System: Equates data packets to addressed physical letters, routers to regional sorting
offices, and IP addresses to explicit geographical drop points.

• Memory (RAM) = Library: Represents storage locations as indexed bookshelves, where fetching item
data requires an explicit address lookup.

• Abstraction = Driving a Car: Users regularly interact with simplified control configurations (steering
wheel, pedals) without needing to understand the internal mechanisms of engine combustion or
transmission layout.

6. Everyday Life Applications: Black-Box Systems

In modern life, users are continuously surrounded by "black-box" systems—complex setups where the internal
operational mechanics are hidden from public view, exposing only a clear user interface.

Masterclass: Analogical Reasoning Page 4 of 5

 The Automotive Interface Analogy:
When a operator drives a car, their immediate sensory experience is bounded by control inputs:

• Steering Wheel (Directional Vector Control)

• Accelerator & Brake Pedal (Velocity Regulation)

The intricate engineering details remain completely obfuscated beneath the chassis:

• Internal Engine Combustion Cycle & Fuel Injection Timings

• Multi-gear Transmission Fluid Dynamics

• Electronic Control Units (ECUs) modulating real-time metrics

The Takeaway: Operating a modern personal computer or digital interface relies on this exact
abstraction layer. A user edits a document or executes software commands utilizing an intuitive UI
without needing to comprehend electronic logic gates, kernel memory allocation, or physical silicon
transistor switching loops.

Masterclass: Analogical Reasoning Page 5 of 5

 The Master Guide to Understanding Analogies
A Comprehensive Guide to Concepts, Types, Applications, and Common Errors

1. Introduction to Analogies
An analogy is a comparison between two different things based on underlying similarities to explain, clarify, or
contextualize a concept. By drawing a parallel between an unfamiliar or complex topic and a familiar one,
analogies serve as powerful cognitive tools across various domains.

Analogies are widely used in teaching, learning, professional communication, systematic problem-solving, and
scientific discovery. They allow individuals to transition from known concepts to new insights by highlighting
structural or functional commonalities.

CLASSIC EXAMPLE

"The brain is like a computer."

This comparison helps people understand how the biological brain processes, stores, and retrieves data by
mapping its functions to the more tangible mechanics of digital hardware and software systems.

2. Cognitive Benefits: Why We Use Analogies

• Simplify Complex Ideas: Abstract or sophisticated concepts become vastly easier to comprehend when framed
appropriately. For example, understanding electricity flowing through wires is simplified by comparing it to
water flowing through pipes.

• Improve Understanding: Learners retain and internalize concepts much better when new information is
directly connected to their existing knowledge and familiar real-world experiences.

• Enhance Memory: Analogies convert abstract ideas into concrete, often visual scenarios, making them easier
to mentally store and recall later.

• Support Problem-Solving: Solutions, structures, or logic from a thoroughly understood problem domain can
be systematically mapped and applied to resolve unfamiliar but structurally similar challenges.

3. Structural Components: Source vs. Target Domain

To construct or analyze an analogy effectively, it must be broken down into its two core structural domains:

• Source Domain: The familiar concept, object, or system used as the reference point.

The Complete Master Guide to Understanding Analogies 1

 • Target Domain: The unfamiliar, abstract, or complex concept being explained.

Source Domain (Library) Target Domain (Computer Memory)

Books Data

Shelves Storage Locations

Librarian Operating System (OS)

4. Classifications and Types of Analogies

Functional Analogies

A Functional Analogy is strictly based on similarity in operation, purpose, or role rather than physical appearance.

• Example: Heart : Pump

• Explanation: While a biological heart and a mechanical pump look entirely different, both share the identical
functional role of circulating fluids through a system.

Other Core Structural Types

• Source to Product: Explores a Creator → Product relationship.

• Antonyms: Formed using completely opposite meanings or contrasting pairs.

• Characteristic: Based on a shared attribute, quality, or trait.

• Object to Function: Highlights a shared purpose or designated use.

• Part to Whole: Establishes a strict Component → System relationship.

• Affective: Connected through a shared emotional impact or feeling.

• Cause to Effect: Maps a specific action directly to a predictable, similar outcome (Action → Outcome).

• Effort and Result: Links the scale of work invested to the corresponding achievement gained (Work →
Achievement).

• Object and Classification: Demonstrates an Item → Category relationship.

• Simple Extended: Consists of multiple parallel comparisons systematically built out from a single foundational
analogy.

5. Case Study Application: The ATM Machine

Analogies are incredibly effective at demystifying modern technical processes by bridging visible actions with
hidden internal mechanics.

The Complete Master Guide to Understanding Analogies 2

 SYSTEM ANALYSIS: AUTOMATED TELLER MACHINE (ATM)

User-Facing Actions (Visible):

• Withdrawing physical cash

• Checking account balance

• Transferring funds between accounts

Hidden Underlying Processes (Technical):

• Secure database access

• Multi-factor authentication

• End-to-end data encryption

• Real-time network communication

Synthesized Analogy:
"An ATM is like a vending machine for banking services." Just as a vending machine handles inventory,
processes payment, and dispenses products securely without human intervention, an ATM automates complex
banking transactions through an intuitive self-service portal.

6. Limitations and Common Pitfalls

While powerful, analogies are inherently imperfect models. Misusing them can lead to significant conceptual
errors.

General Limitations

• Oversimplification: Many analogies completely ignore or obscure critical details and nuances essential for
comprehensive technical mastery.

• Incomplete Comparison: An analogy typically illuminates only a few isolated aspects of a target concept,
leaving other parts unaddressed.

• Potential Misconceptions: Two systems may appear highly similar on the surface but differ fundamentally
upon deep analysis.

Critical Errors in Construction

• The False Analogy: Comparing two things that are not actually alike in the specific, relevant way required to
validate the premise.

• Over-Complication: If the explanatory analogy is more obscure or harder to understand than the original target
concept, it completely fails its purpose.

The Complete Master Guide to Understanding Analogies 3

 • Cultural Misalignment: Utilizing an analogy rooted in specific cultural references (e.g., a highly technical
baseball sports analogy) with an audience entirely unfamiliar with that context.

• Over-stretching: Forcing and pushing the comparison way too far past its logical limits until the parallel breaks
down entirely.

The Complete Master Guide to Understanding Analogies 4

Understanding Analogies
Cognitive Bridges for Learning, Explanation, and Technical Reasoning

Analogies serve as powerful "cognitive bridges" that connect familiar, well-understood ideas with
unfamiliar, complex concepts. By mapping the structure or relationships of a known domain onto a
new one, analogies make learning clearer, faster, and significantly more intuitive.

These cognitive tools are particularly invaluable in technical fields such as Computer Science,
Software Engineering, and Artificial Intelligence, as well as in general pedagogy. They assist
students and professionals alike in deciphering highly abstract logical frameworks by grounding
them in concrete real-world experiences.

Traditional Types of Analogies

The eight classical categories of analogical reasoning used in instruction and cognitive analysis:

1. Functional 5. Simple

2. Structural 6. Extended

3. Verbal 7. Literal

4. Symbolic 8. Figurative

Analogy vs. Metaphor

While both concepts are used to draw comparisons, they serve fundamentally different linguistic and
cognitive purposes. An analogy is primarily a tool for logical reasoning and structured
explanation, whereas a metaphor is a figure of speech designed for vivid expression and
immediate effect.

Masterclass: Theory of Analogies 1

 Feature Analogy Metaphor

Explains similarities in precise States that one thing physically *is*

Core Purpose
detail. another for immediate effect.

Facilitating logical understanding Artistic, emotional, or vivid linguistic

Primary Use
and structural mapping. expression.

Comparison Logical, structural, or relational Figurative, direct, and implicit

Type comparison. comparison.

In-Depth: Key Analogy Types with Examples

1. Simple Analogy

A straightforward, single-point comparison between two distinct things designed to introduce

basic alignment.

Example: "A teacher is like a guide."

Similarity: Both provide clear direction and lead others through unfamiliar territory.

2. Structural Analogy

Based strictly on the similarity in physical structure, organizational hierarchy, or the complex
relationships among internal parts.

Example: Atom : Solar System

Similarity: Both have a massive central body (nucleus/sun) surrounded by smaller orbiting
bodies (electrons/planets).

Masterclass: Theory of Analogies 2

 3. Symbolic Analogy

Uses signs, symbols, representations, or conceptual metaphors to convey deep, abstract meaning
through a highly familiar vehicle.

Example: "Time is money."

Similarity: Both represent finite, highly valuable resources that can be spent, saved, wasted,
or invested.

4. Verbal Analogy

Expressed directly through words and structured proportional relationships between terms,
highly common in standardized aptitude and reasoning tests.

Example: Doctor : Hospital :: Teacher : School

Logic: A doctor operates professionally within a hospital, just as a teacher operates within a
school. (Another classic: Bird : Fly :: Fish : Swim)

5. Technical Analogy: Database Systems

In technical instruction, bridging the gap between physical objects and virtual system structures
helps demystify abstract data layers.

Physical Office Analogy to Database Systems:

• Drawer → Table
• Folder → Record
• Document → Data Item

Pedagogical Advantages of Analogies

• Easier Learning: Simplifies highly abstract, complex, or intimidating topics, making them
approachable.

• Better Retention: Learners retain knowledge far longer when it is anchored to pre-existing,
familiar mental models.

Masterclass: Theory of Analogies 3

 • Creative Thinking: Promotes lateral thinking and the generation of innovative solutions by
viewing old problems through a new lens.

• Knowledge Transfer: Builds the fundamental intellectual capacity to take a structured solution
from one domain and apply it effectively to an entirely new, unfamiliar situation.

"To teach well, start with what is known, construct a reliable bridge, and safely guide the learner to the unknown."

Masterclass: Theory of Analogies 4

COS102 Study Notes
(Compiled from "COS102 Compiled by T" — 151-page
slide deck)

This document covers everything in the deck:

Analogies, Abstraction, Programming Paradigms, and
Python Programming Basics (variables, data types,
strings, data structures, control flow, and functions).

Module 1: Analogies

What is an Analogy?

An analogy is a comparison between two different

things based on their similarities, used to explain or
clarify a concept. It works by mapping something
familiar (the source) onto something unfamiliar (the
target) so the unfamiliar thing becomes easier to
understand.

Example: "The brain is like a computer."

| Computer (Source) | Brain (Target) |
|---|---|
| Stores data | Stores memories |
| Processes information | Processes thoughts |
| Has input devices | Receives sensory input |
| Produces output | Produces actions |

Why We Use Analogies

Simplify complex ideas (e.g., electricity flowing

through wires ≈ water flowing through pipes)

Improve understanding by connecting new ideas

to familiar experiences

Enhance memory by turning abstract ideas into

concrete, visual scenarios

Support problem-solving by applying known

solutions to similar new problems

Structure of an Analogy

Source Domain: The familiar concept

Target Domain: The concept being explained

The Mapping: The connection between features

of the source and the target

Example: An atom is like a solar system — the Sun

(center) maps to the Nucleus; Planets (orbiting) map
to Electrons.

Traditional Types of Analogies

1. Functional — based on similarity in

function/purpose (e.g., Heart : Pump — both
circulate fluids)
 2. Structural — based on similarity in
structure/organization (e.g., Atom : Solar System)

3. Verbal — expressed through words/relationships

between terms, common in reasoning tests (e.g.,
Doctor : Hospital :: Teacher : School)

4. Symbolic — uses symbols or metaphors to convey

meaning (e.g., "Time is money")

5. Simple — a single-point, straightforward

comparison (e.g., "A teacher is like a guide")

6. Extended — develops multiple points of

comparison from one analogy

7. Literal — compares things from the same

category

8. Figurative — compares things from different

categories to evoke imagery or emotion

Other (Related) Types of Analogies

Source to Product — creator → product

relationship

Antonyms — opposite meanings

Characteristic — shared attribute/quality

Object to Function — same purpose or use

Part to Whole — component → system

relationship

Affective — shared emotional impact

 Cause to Effect — similar action → similar
outcome

Effort and Result — work invested → achievement

gained

Object and Classification — item → category

relationship

Analogical Reasoning

Definition: The process of drawing conclusions based

on similarities. General pattern: A is related to B, as C
is related to ?

Example: Doctor : Hospital :: Teacher : ? → Answer:

School (a doctor works in a hospital just as a teacher
works in a school).

Analogies Across Fields

Computer Science: Database = Filing Cabinet;

Internet = Postal System; Memory = Library;
Abstraction = Driving a Car

Database specifically: Drawer → Table; Folder →

Record; Document → Data Item

Mathematics: Number line = Straight road;

Equation = Balanced scale

Science: Electric current = Water flow; DNA =

Blueprint

Everyday Life:
 Driving a car is like using a computer — you
interact with controls (steering wheel, pedals)
without needing to understand what's
happening underneath (engine, fuel injection).

An ATM is like a vending machine for banking

services — you see simple actions (withdraw,
check balance) while complex processes
(database access, authentication, encryption,
network communication) stay hidden.

Advantages and Limitations

Advantages: Easier learning, better retention, sparks

creative thinking, and helps transfer knowledge from a
familiar situation to a new one.

Limitations:

Oversimplification — ignores important details

Incomplete comparison — only highlights some

aspects

Potential misconceptions — things may look

similar but differ significantly

Common Errors in Using Analogies

False Analogy — comparing two things that aren't

actually alike in the relevant way

Over-Complication — the analogy becomes

harder to understand than the original concept
 Cultural Misalignment — using an analogy (e.g., a
sports reference) an audience won't recognize

Over-stretching — pushing the comparison too far

until it breaks down

Analogy vs. Metaphor

Analogy Metaphor

Explains similarities in States one thing is

detail (tool for another for effect (figure
reasoning) of speech)

Used mainly for

Used for understanding
expression

Logical comparison Figurative comparison

Module Summary

Analogies are "cognitive bridges" between the known

and the unknown — powerful tools for teaching,
persuasion, and innovation. Rule of thumb: use
familiar examples, keep it simple, and make sure the
logic actually holds.

Module 2: Abstraction in Computer

Science
What is Abstraction?

Abstraction is the process of hiding unnecessary

implementation details while exposing only the
essential features of a concept. It is a fundamental
tool for managing complexity.

Core philosophy: "Hide the HOW, show the WHAT."

It lets us think about a problem at a higher level

without getting bogged down in how it actually works
underneath.

Why We Need Abstraction

Reduces complexity

Improves understanding

Enhances productivity

Levels of Abstraction

Abstraction exists on a spectrum, not as an all-or-

nothing thing:

High-Level: Very general, far from details (e.g., "I

want to build a house")

Mid-Level: Functional systems (e.g., electrical,

plumbing, framing)

Low-Level: Specific details/components (e.g.,

wire gauge, concrete composition)
Moving up the ladder helps with strategy; moving
down helps with execution.

Why We Use Abstraction (4 reasons)

1. Complexity Management — build massive

systems (like the internet) by breaking them into
manageable layers

2. Efficiency — you don't have to reinvent the wheel

every time

3. Reusability — generic solutions can apply to many

specific problems

4. Clarity — improves communication by focusing on

the "big picture"

Everyday Examples

Car: The driver interacts with an abstract interface

— steering wheel, pedals, gear shift — without
needing to understand internal combustion or fuel
injection. (Driver → Controls → Hidden Systems)

ATM: The customer withdraws cash, checks

balance, transfers funds — while authentication,
the database, and the network stay hidden.
(Customer → ATM Interface → Authentication,
Database, Network)

Art: Abstraction moves away from painting

exactly what is seen ("Representational" art)
toward capturing the essence/spirit of a subject
 using color, shape, and line (e.g., Picasso's
Cubism, Pollock's Abstract Expressionism).

Abstraction in Technology

Programming languages: Python (high-level) vs.

Binary/Machine Code (low-level)

User interfaces: Buttons/icons hide the complex

code running underneath

APIs (Application Programming Interfaces): Let

software talk to other software without knowing
its inner workings

Encapsulation: Grouping related data and

functions while hiding internal state

Abstraction in Computer Systems and

Programming

Layered stack: Applications → OS → Machine

Language → Hardware

print("Hello World") hides complex internal

operations

Functions give simple interfaces to complex

operations

In OOP: Abstraction focuses on what an object

does, not how it does it — achieved through
Abstract Classes and Interfaces

Online banking: simple user actions hide

databases, security, networking
 Web browser: typing a URL hides DNS lookups,
HTTP requests, and page rendering

Abstraction vs. Encapsulation

Abstraction hides complexity; encapsulation hides

data. (These are related but distinct — abstraction is
about what is shown to the user, encapsulation is
about protecting the internal state of an object.)

Advantages, Limitations, Applications

Advantages: Readability, maintainability,

reusability, scalability

Limitations: Performance overhead, hidden

details can obscure understanding, debugging
can be harder

Applications: Software Engineering, Databases,

Networks, AI, Web Development

Module Summary

Abstraction manages complexity by exposing only

essential features — it's described as "a superpower
for the human brain," letting us navigate a complex
world without being overwhelmed. Mastering it
means knowing which details to ignore and which to
keep. Final thought: "Simplicity is the ultimate
sophistication."
Module 3: Programming Paradigms

A programming paradigm is a style/approach to

writing and organizing code.

Declarative Programming

Definition: Expresses the logic of computation

without describing its control flow — focuses on what
needs to be done, not how. Often treats programs as
theories of logic; can simplify writing parallel
programs. Divided into three types:

1. Logic Programming — an abstract model of

computation used to solve logical problems (like
puzzles). Uses a knowledge base (facts known
beforehand) combined with a query to produce
results — this concept underlies some AI/machine
learning models (e.g., the Perceptron model).

2. Functional Programming — rooted in

mathematics and language-independent. Core
principle: executing a series of mathematical
functions that hide their implementation.

3. Database/Data-Driven Programming — based on

data and its movement; program statements are
defined by data rather than a hard-coded
sequence of steps. A database program is the
heart of a business information system.

Imperative Programming
Definition: Works by changing the program's state
through assignment statements, performing tasks
step by step. The main focus is how to achieve the
goal.

Pros Cons

Very simple to Complex problems can be

implement hard to solve

Contains loops, Standard/less parallel-

variables, etc. friendly

Parallel programming is not

—
really possible

Procedural Programming (a type of imperative

programming): Emphasizes procedures based on an
underlying machine model. There's essentially no
difference between "procedural" and "imperative" here
— its main strength is code reusability.

Structured Programming (SP)

Definition: The program is built as a single structure,

executed instruction-by-instruction with no GOTO
statements (no jumping between arbitrary
instructions). Improves reliability and clarity.
Examples of structured languages: C, C++, Java, C#.

Two primary features of SP:

 1. A hierarchical arrangement of highly independent
modules

2. Flow is controlled exclusively by three control

forms: selection, repetition, sequencing (also
called selection, iteration, sequencing)

Basic control structures:

Selection: if / then / else , case statements

Repetition: do while , do until , while

statements

Sequencing: placing statements one after another

Advantages/Disadvantages of High-Level
(Structured) Languages:
| Advantages | Disadvantages |
|---|---|
| Easy to read and understand; user-friendly | Machine-
independent code takes time to convert to machine
code |
| Easier to maintain and debug | Depends on
changeable factors like data types |
| Problem-based, not machine-based | Development
can take longer since it's more language-dependent
than assembly |
| Requires less effort/time to develop | — |

Object-Oriented Programming (OOP)

Definition: A paradigm where everything is
represented as an object, providing concepts like
inheritance, data binding, and polymorphism.

Simula = the first object-oriented programming

language

Smalltalk = the first truly object-oriented

programming language

Popular OOP languages: Java, C#, PHP, Python,

C++

Main aim: to model real-world entities in software

Core OOP concepts: Object, Class, Inheritance,

Polymorphism, Abstraction, Encapsulation, Coupling,
Cohesion, Association

Module 4: Introduction to Python &

Basic Data Types

About Python

Python is a popular, high-level, general-purpose

programming language known for clear, easy-to-read
syntax. Created by Guido van Rossum, released in
1991. Its design emphasizes code readability.

Applications:

Web development (Django, Flask)

 Data science and machine learning (statistics,
visualization, AI)

Automation and scripting (repetitive tasks, file

renaming, emails)

Software development (games to business

software)

Python has an extensive standard library ("batteries-

included" approach) — a huge collection of pre-written
modules/packages. It is open-source, free to use, and
runs on Windows, Mac, and Linux.

Basic Data Types

int — whole numbers, positive or negative, no

fractional part (e.g., age = 30 )

float — real numbers with a decimal point (e.g.,

price = 19.99 )

str (string) — a sequence of characters in single

or double quotes (e.g., "Hello, World!" )

bool (Boolean) — one of two values: True or

False ; essential for decision-making

NoneType — a special type representing "no

value" or null ( None )

You can check a variable's type using the type()

function.

Variables and Assignment

A variable is a symbolic name that acts as a container
to store a value in memory. The assignment operator
( = ) gives a value to a variable.

x = 10 # Variable 'x' is assigned

the value 10
x = "Hello" # variables can be reassigned
to a different type

Multiple assignment: Python allows assigning several

variables at once in one line.

Expressions and Operators

An expression is a combination of values, variables,

and operators that Python evaluates to produce a
single result (e.g., result = 10 + 5 evaluates to
15 ).

Operators are special symbols that perform

computations on values/variables (called operands).

Arithmetic Operators:
| Operator | Name | Example |
|---|---|---|
| + | Addition | 10+5 = 15 |
| - | Subtraction | 10-5 = 5 |
| * | Multiplication | 10*5 = 50 |
| / | Division | 10/5 = 2.0 (always returns a float) |
| // | Floor Division | 10//3 = 3 (discards the
fraction) |
| % | Modulus | 10%3 = 1 (the remainder) |
| ** | Exponentiation | 10**2 = 100 |

Comparison Operators (return a Boolean):

== equal to, != not equal to, > greater than, < less
than, >= greater/equal, <= less/equal.

Logical Operators:

and — True only if both statements are True

or — True if at least one statement is True

not — reverses the result (True becomes False,

and vice versa)

Augmented Assignment Operators (shorthand to

update a variable):
| Operator | Example | Equivalent to |
|---|---|---|
| += | x += 3 | x = x + 3 |
| -= | x -= 3 | x = x - 3 |
| *= | x *= 3 | x = x * 3 |
| /= | x /= 3 | x = x / 3 |

Module 5: Type Casting & Strings

Type Casting

Definition: Converting a value from one data type to

another — needed when performing operations that
require a specific type. Done explicitly using functions
like int() , str() , float() .

count = 100
count_str = str(count) # converts int to
string

String Slicing

Slicing extracts a specific portion of a string using

square brackets [start:stop:step] :

start — the starting index (inclusive)

stop — the ending index (exclusive)

step — the interval between indices

message = "Hello, Python!"

message[0:5] # "Hello"
message[:7] # "Hello, "
message[7:] # "Python!"
message[::2] # "Hlo yhn" (every 2nd
character)
message[::-1] # "!nohtyP ,olleH"
(reversed string)

Modifying Strings

Strings in Python are immutable — you cannot change

them directly. Any "modification" (like .replace() )
actually creates a new string; the original is
unchanged unless reassigned.

Concatenating Strings

Concatenation = joining two or more strings together.

Common methods: the + operator, the .join()
method, and f-strings.

full_name = first_name + " " + last_name

Escape Characters

Special sequences (prefixed with a backslash \ )

used inside a string to represent characters that are
otherwise hard to type:

\n — Newline

\t — Tab

\\ — Backslash

\" — Double quote

\' — Single quote

String Methods

Python's built-in str class has many useful methods:

.strip() — removes whitespace from the

beginning and end

.lower() / .upper() — changes case

 .capitalize() — capitalizes the first letter

Module 6: Data Structures — List,

Tuple, Set, Dictionary

List

Definition: A mutable, ordered collection of items that

can hold different data types. Created with square
brackets [] .

Ordered — items keep a defined order unless the

list is modified

Mutable — you can change, add, or remove items

after creation

Allows duplicates

fruits = ["apple", "banana", "cherry"]

fruits[1] = "orange" # modify an
element
[Link]("grape") # add an element
len(fruits) # get list
length
list3 = list1 + list2 # join two lists

Tuple
Definition: An immutable, ordered collection of items
— similar to a list but cannot be changed after
creation. Created with parentheses () .

Ordered and allows duplicates, but immutable

(cannot add/remove/change items)

Tuples are faster than lists to process, and used

as dictionary keys because they're immutable

Attempting to modify a tuple raises an error

Tuples can be unpacked into separate variables

coordinates = (10, 20, 30)

coordinates[0] # 10
coordinates[1:] # (20, 30)

Set

Definition: An unordered collection of unique

elements. Mutable, but elements themselves must be
an immutable type (numbers, strings, tuples). Created
with curly braces {} .

Unordered — no index access

Mutable — can add ( .add() ) or remove

( .remove() / .discard() ) items

Unique — automatically removes duplicates

Supports set operations: union, intersection,

difference
 set1 = {1, 2, 3}
set2 = {3, 4, 5}
[Link](set2) # {3}
[Link](set2) # {1, 2, 3, 4,
5}

Dictionary

Definition: A mutable, unordered collection of key-

value pairs, mapping unique immutable keys to values
of any type. Created with curly braces {} .

Key-Value pairs: stored as key: value

Mutable: you can add, remove, or change pairs

Unique keys: a duplicate key overwrites the

previous entry

Immutable keys: keys must be strings, numbers,

or tuples

As of Python 3.7, dictionaries maintain insertion

order

person = {"name": "Alice", "city": "New

York"}
person["name"] # access:
"Alice"
person["age"] = 31 # add a new key
del person["city"] # remove a key
for key, value in [Link](): #
 iterate
print(f"{key}: {value}")

Module 7: Control Flow —

Conditionals & Loops

Conditional Statements

Control the flow of a program, executing different

code depending on whether a condition is True or
False.

if statement: runs code only if the condition is True.

if age >= 18:

print("The number is positive.")

if-else statement: provides an alternative block

when the condition is False.

if num % 2 == 0:
print("The number is even.")
else:
print("The number is odd.")

if-elif-else statement: checks multiple conditions

in order; runs the first True block, else runs the final
else .
 if score >= 90:
print("Grade: A")
elif score >= 80:
print("Grade: B")
else:
print("Grade: F")

Nested if statements: an if placed inside another

if , for more complex logic.

Logical operators in conditions: and , or , not can

combine multiple conditions (e.g., checking age >=
18 and born_again ).

Loops

Loops repeat a block of code. Python has for loops

and while loops.

for loop — iterates over items in a sequence (list,

string, etc.) or other iterable:

for fruit in fruits:

print(fruit)

for i in range(5): # prints 0,1,2,3,4

print(i)

while loop — continues executing as long as a

condition remains True:
 count = 3
while count > 0:
print(count)
count -= 1
print("Go!")

Loop control statements:

break — exits the loop entirely

continue — skips the current iteration, moves to
the next

pass — a placeholder where a statement is

syntactically required but nothing needs to
happen

Module 8: Functions

What is a Function?

Definition: A block of code that performs a specific,

organized, reusable task. You run ("call") it by name.
Functions help break complex problems into smaller
pieces, avoid repeated code, and make programs
easier to read and maintain.

Defining and Calling a Function

Defined with the def keyword:

 def function_name(parameter1, parameter2,
...):
"""Docstring: brief description of what
the function does."""
# code block
return result # optional

def greet():
print("Hello, welcome to the Python
lecture.")
greet() # calling the function

Parameters vs. Arguments

Parameters — variables listed inside the

parentheses in the function definition;
placeholders for expected values

Arguments — the actual values passed in when

the function is called

def my_sum(a, b): # a, b = parameters

return a + b
my_sum(10, 20) # 10, 20 = arguments

The return Statement

Sends a value back to the code that called the

function, and immediately exits the function. If a
function has no return statement, it implicitly
returns None .
Types of Arguments

1. Positional Arguments — matched to parameters

based on their order

2. Keyword Arguments — identified by parameter

name, so order doesn't matter (e.g.,
describe_pet(pet_name="Buddy",
animal_type="dog") )

3. Default Arguments — a parameter is given a

default value in the definition, used only if no
argument is provided (e.g., def greet(name,
greeting="Hi") )

4. Variable-Length Arguments — accept an

unknown number of arguments:

*args — for positional arguments, stored as

a tuple

**kwargs — for keyword arguments, stored

as a dictionary

def print_info(**kwargs):
for key, value in [Link]():
print(f"{key}: {value}")
print_info(name="Tom", age=45,
city="London")

Recursive Functions

Definition: A function that calls itself to solve a

problem. Requires a base case to stop the recursion
and prevent an infinite loop.

def factorial(n):
if n == 0 or n == 1: # base case
return 1
else: # recursive
case
return n * factorial(n - 1)

Lambda Functions

Definition: A small, anonymous function defined with

the lambda keyword. Can take any number of
arguments but only one expression.

square = lambda x: x * x
print(square(4)) # 16

Key Points to Remember

1. Analogy = comparing something unfamiliar

(target) to something familiar (source) to make it
easier to understand; useful but can mislead if
pushed too far (false analogy, over-stretching).

2. Abstraction = "hide the HOW, show the WHAT" —

expose only essential features, hide complexity.
It's the single biggest tool for managing
complexity in computing.
 3. Abstraction ≠ Encapsulation: abstraction hides
complexity/detail; encapsulation hides data
(protects internal state).

4. Programming paradigms fall broadly into

declarative (what to do: logic, functional,
database) and imperative (how to do it:
procedural, structured, OOP).

5. Structured programming bans GOTO and relies

only on sequencing, selection, repetition.

6. OOP treats everything as an object; Simula was

first OOP language, Smalltalk was first true OOP
language.

7. Python's core data types: int, float, str, bool, None

— check any variable's type with type() .

8. Division / always returns a float; use // for

floor (integer) division and % for the remainder.

9. Strings are immutable in Python — "modifying"

one always creates a new string.

10. Data structure cheat sheet:

List [] — ordered, mutable, duplicates

allowed

Tuple () — ordered, immutable, duplicates

allowed, faster than lists

Set {} — unordered, mutable, no duplicates

Dictionary {key: value} — unordered

(technically insertion-ordered since 3.7),
mutable, unique keys
11. Control flow keywords: if/elif/else for
decisions; for / while for loops; break exits a
loop, continue skips to the next iteration, pass
does nothing (placeholder).

12. Functions: parameters are placeholders in the

definition, arguments are actual values passed at
call time. *args → tuple of extra positional args;
**kwargs → dictionary of extra keyword args.

13. A function with no return implicitly returns

None .
14. Recursive functions must have a base case, or
they will run forever.

15. Lambda functions are quick, unnamed, one-

expression functions — good for short, throwaway
logic.