METRICS DETAILS
SUBJECT CODE GE23111
SUBJECT NAME PROBLEM SOLVING AND
C PROGRAMMING
DEPARTMENT AIDS
YEAR/SECTION I YEAR / C AND D
BATCH 2025
Vincent Gnanaraj T
AI & DS
UNIT I
COMPUTATIONAL THINKING AND
PROBLEM SOLVING
Topic 1 - Fundamentals of Computing
Basics of Computer & Units
Computer: Electronic device → Input → Process → Output → Storage
Characteristics
Speed
Accuracy
Automation
Storage
Versatility
Basic Units
Input Unit – Keyboard, Mouse, Scanner
CPU
Control Unit (CU) – Directs operations
Arithmetic Logic Unit (ALU) – Calculations & logic
Registers – High-speed storage
Memory Unit
Primary: RAM (volatile), ROM (permanent)
Secondary: HDD, SSD, USB
Output Unit – Monitor, Printer, Speakers
Hardware vs Software
Hardware – Physical parts
Software – Programs & instructions
Topic 1 - Fundamentals of Computing
Topic 1 - Fundamentals of Computing
Generation Duration Technology Used Features Examples
Very large size, high power
1st 1940 – 1956 Vacuum Tubes consumption, slow, costly, ENIAC, UNIVAC, IBM-701
lot of heat
Smaller, faster, more
2nd 1956 – 1963 Transistors reliable, less heat, cheaper IBM-1401, CDC-1604
than 1st
Even smaller, faster,
3rd 1964 – 1971 Integrated Circuits (IC) cheaper, more efficient, IBM-360, PDP-8
better performance
Personal computers,
4th 1971 – 1980s Microprocessors (LSI, VLSI) portable, very fast, high IBM PC, Apple Macintosh
storage
Artificial Intelligence,
parallel processing,
5th 1980s – Present ULSI, AI & Advanced Tech AI Systems, Robotics, Cloud
multimedia, very high
speed
Topic 1 - Fundamentals of Computing
• CPU (Central Processing Unit) – Brain of the computer
• Main Units of CPU:
• Control Unit (CU)
•Directs flow of data and instructions
•Manages communication between input, memory, ALU, and
output
• Arithmetic Logic Unit (ALU)
•Performs arithmetic operations (Add, Subtract, Multiply,
Divide)
•Performs logical operations (AND, OR, NOT, Compare)
• Registers
•High-speed temporary storage inside CPU
•Holds instructions, data, addresses during processing
• Cache Memory (sometimes included)
•Very fast memory, stores frequently used data/instructions
•Reduces time to access main memory
Topic 1 - Fundamentals of Computing
Language Processors & Software Types
1) Language Processors
Translate high-level or assembly language → Machine code
• Assembler – Converts Assembly Language → Machine Code
Example: MOV AX, BX → binary code
• Compiler – Translates entire program → Machine Code at once
Fast execution, but errors shown only after full compilation.
Example: C, C++ compilers
• Interpreter – Translates & executes line-by-line
Translates & executes line by line. Easier for debugging, but
slower execution
Example: Python, JavaScript
2) Types of Software
System Software – Manages hardware & system resources
• Operating Systems (Windows, Linux, macOS)
• Device Drivers
• Utility Programs (Antivirus, Disk Management)
Application Software – Performs specific user tasks
• General Purpose: MS Word, Excel, Photoshop, Browsers
• Specialized: Banking software, Hospital management, CAD tools
Topic 1 - Fundamentals of Computing
Types of Computers
1) By Size & Power
• Supercomputers – Very high speed, complex scientific applications (e.g.,
weather forecasting, space research)
• Mainframe Computers – Large data processing, used in banks, airlines,
industries
• Minicomputers – Mid-sized, used in small businesses & organizations
• Microcomputers (Personal Computers) – Desktop, Laptop, used by
individuals
• Workstations – High-performance PCs for graphics, CAD, AI research
2) By Purpose
• General Purpose – Versatile, handles many tasks (PCs, laptops)
• Special Purpose – Designed for a specific task (ATMs, embedded
systems)
3) By Data Handling
• Analog Computers – Handle continuous data (temperature, pressure)
• Digital Computers – Handle discrete data (0s and 1s, most modern
computers)
• Hybrid Computers – Combine analog + digital (used in medical &
scientific applications)
Topic 1 - Fundamentals of Computing
Levels of Programming Languages
Low-Level Languages
• Closest to hardware
• Types:
• Machine Language – Binary (0s & 1s)
• Assembly Language – Mnemonics (e.g., MOV AX, BX)
Middle-Level Languages
• Act as a bridge between low & high-level
• Provide both hardware control (like low-level) and portability (like high-
level)
• Fact: C is considered a Middle-Level Language because it supports
• Direct memory access (low-level feature)
• Structured programming (high-level feature)
• Examples: C, C++
High-Level Languages
• Human-friendly, problem-oriented, hardware independent
• Easy to learn, portable across systems
• Examples: Python, Java, BASIC, FORTRAN, COBOL
Topic 1 - Fundamentals of Computing
Primary Memory Secondary Memory Tertiary Memory
Feature
(Main) (Storage) (Backup/Archive)
Very fast (nanoseconds Slowest (seconds to minutes
Speed Slower than primary
access) access)
Volatile (RAM) / Non-volatile
Volatility Non-volatile Non-volatile
(ROM)
Cost Very expensive per MB Cheaper than primary Cheapest per GB
Capacity Small (MBs → few GBs) Large (GBs → TBs) Very large (TBs → PBs)
Not directly accessible (needs Requires special devices
Accessibility Directly accessible by CPU
loading) (robotic arms, jukeboxes)
Holds data/programs CPU is Stores OS, software, files Long-term storage, backups,
Purpose
using now permanently disaster recovery
Magnetic tapes, Optical
HDD, SSD, Flash Drives,
Examples RAM, ROM, Cache, Registers jukeboxes, Cloud archival
Optical Discs
storage
Topic 1 - Fundamentals of Computing
Computer Fundamentals Overview
Operating System
• Manages hardware resources
• Acts as system software & user interface provider
• Bridge between hardware and applications
Examples: Windows, Linux, macOS
Syntax, Semantics & Program Translation
• Syntax: Structure of code (e.g., print("Hello"))
• Semantics: Meaning of code (e.g., printing a message)
• Compiler: Translates entire program → machine code
Example: C Compiler
• Interpreter: Executes code line-by-line
Example: Python Interpreter
Debugging
• Syntax Errors: Invalid code form
Example: prnt("Hello")
• Semantic Errors: Logic mistakes
Example: (num1 + num2 + num3)/2 instead of /3
Topic 1 - Fundamentals of Computing
Real-Time
Number Digits Calculation
Base Example Use /
System Used Example
Application
Digital
electronics, Convert 4 → 4/2=2 R0 →
Binary 2 0, 1 (1010)₂ = (10)₁₀ computer 2/2=1 R0 → 1/2=0 R1 →
memory, logic 100₂
circuits
Unix file
permissions,
Convert (1010)₂ →
Octal 8 0–7 (12)₈ = (10)₁₀ compact
group 2 bits → 12₈
representation of
binary
Everyday
(25)₁₀ = counting, 25₁₀ → divide by 2
Decimal 10 0–9
(11001)₂ financial repeatedly → 11001₂
calculations
Memory
addresses, color 26₁₀ → divide by 16 → 1
Hexadecimal 16 0–9, A–F (1A)₁₆ = (26)₁₀
codes in remainder 10 → 1A₁₆
web/graphics
a. Binary: Used internally by CPU & digital circuits.
b. Octal: Shorter representation of binary for humans.
c. Decimal: Human-friendly standard.
d. Hexadecimal: Easier for programmers to read memory contents.
TO SOLVE A PROBLEM
Representation
• Captures all relevant aspects of the problem
• Abstraction: leaves out unnecessary details
Example 1: Man, Cabbage, Goat, Wolf (Brute Force Approach)
• Farmer must cross river with wolf, goat, cabbage
• Can take only one at a time in the boat
• Constraints
• Wolf eats goat if left together
• Goat eats cabbage if left together
Solution Strategy (7 crossings total)
• Take goat across
• Return alone
• Take wolf (or cabbage) across
• Bring goat back
• Take cabbage (or wolf) across
• Return alone
• Take goat across
Outcome: All items safely reach the other side.
Limits of Computational Problem Solving
• Even if an algorithm exists, key question, Can it solve the
problem in reasonable time?
• If not → algorithm has limited practical use
• Example: Traveling Salesman Problem (TSP)
Goal: Find shortest route covering all cities
Brute force approach
• Try all possible routes
• Total possibilities: (n-1)! Routes
Steps in brute force algorithm
• Choose a starting city
• Generate all possible permutations
• Calculate cost of each route → choose minimum
Process of Computational Problem Solving
More than just programming → stepwise process
Step 1: Problem Analysis
• Understand problem & fundamental computational issues
• Small problems → brute force feasible (e.g., MCGW puzzle)
• Large problems (e.g., TSP, chess) → brute force infeasible
Step 2: Program Design
•Represent data (lists, distances, calendar info, etc.)
•Choose / design algorithms (search, heuristic, etc.)
Step 3: Program Implementation
•Convert design into code (Python, C, etc.)
Step 4: Program Testing
•Errors are inevitable → testing is essential
•Testing should be: incremental, systematic, and thorough
•Must understand why a fix works
Algorithm
• A clear sequence of executable instructions that, when followed, yields
the desired result.
• It describes the logic of a program — a step-by-step plan to solve a
problem.
• Key point: an algorithm is any problem whose solution can be
expressed as a list of executable instructions.
Characteristics of an Algorithm
• Instructions must be precise (exact and unambiguous).
• Instructions should not loop infinitely — the algorithm must
terminate.
• Steps must be written in sequence (clear order of execution).
• Should be understandable (read like normal English where possible).
• The desired result is obtained only after termination.
• There can be many algorithms for the same problem (different
logics/approaches).
Qualities of a Good Algorithm
• Time (Efficiency): Less execution time is better.
• Memory (Space efficiency): Uses less storage during execution.
• Accuracy: Produces correct results (or acceptable approximations).
• Sequence / Determinism: Steps form a controlled sequence or repetition
until condition met.
• Generality: Works for a wide range of valid inputs, not just specific cases.
Representation of Algorithms
• Normal English — step-by-step prose; easy to read and write; good for
initial ideas.
• Flowchart — pictorial depiction using standard symbols (Start/End,
Process, Decision, I/O); useful for visualization and review.
• Pseudocode — informal, structured code-like description; great for tying
design to implementation.
• Decision Table — tabular view of complex conditional logic; clarifies
nested selections and test cases.
• Program (Source Code) — final representation in a programming
language (e.g., Python, C); executable.
Algorithm to Find Greatest of 3 Numbers
1.Start
2.Input three numbers: a, b, c
3.If (a >= b) AND (a >= c)
Then a is the greatest
4.Else if (b >= a) AND (b >= c)
Then b is the greatest
5.Else
c is the greatest
6.Display the greatest number
7.Stop
Pseudo-code for finding greatest of three numbers
BEGIN
INPUT a, b, c
IF (a >= b) AND (a >= c) THEN
PRINT "Greatest is", a
ELSE IF (b >= a) AND (b >= c) THEN
PRINT "Greatest is", b
ELSE
PRINT "Greatest is", c
ENDIF
END
Algorithm for Simple Interest
1.Start
2.Input the Principal amount (P)
3.Input the Rate of interest (R)
4.Input the Time in years (T)
5.Compute Simple Interest using the
formula:
𝑃×𝑅×𝑇
𝑆𝐼 =
100
1.Display the value of SI
2.Stop
Pseudo-code for finding Simple
Interest
BEGIN
INPUT P, R, T
SI ← (P * R * T) / 100
PRINT "Simple Interest =", SI
END
Algorithm for swapping without temp
1.Start
2.Input two numbers: a, b
3.Set a = a + b
4.Set b = a - b
5.Set a = a - b
6.Display a and b (swapped values)
7.Stop
Pseudo-code for Swapping two numbers
BEGIN
INPUT a, b
a←a+b
b←a-b
a←a-b
PRINT "After swapping: a =", a, ", b =", b
END
Algorithm for C to F and F to C Pseudo-code for Temperature
degrees conversion
1.Start BEGIN
2.Display: PRINT "Press 1 for Celsius to
1. Press 1 for Celsius → Fahrenheit"
Fahrenheit PRINT "Press 2 for Fahrenheit to
2. Press 2 for Fahrenheit → Celsius"
Celsius INPUT choice
3.Input user’s choice → ch
4.If ch = 1: IF choice = 1 THEN
1. Input temperature in Celsius → INPUT C
C F ← (C * 9/5) + 32
2. Compute F = (C × 9/5) + 32 PRINT "Fahrenheit =", F
3. Display F ELSE IF choice = 2 THEN
5.Else if ch = 2: INPUT F
1. Input temperature in C ← (F - 32) * 5/9
Fahrenheit → F PRINT "Celsius =", C
2. Compute C = (F - 32) × 5/9 ELSE
3. Display C PRINT "Invalid choice"
6.Else ENDIF
1. Display “Invalid choice” END
7.Stop
Algorithmic Problem Solving
• Algorithmic problem solving starts with the informal notion of an algorithm.
• A finite sequence of precise instructions designed to solve a well-defined problem.
• Choosing the right approach is often the key to arriving at the best solution.
• In computer science (and even in psychology), an algorithm is a systematic, step-by-step procedure to reach
the correct answer when solving a problem or making a decision.
1. Understanding the Problem
• Identify the inputs the algorithm will handle.
• Clearly define the expected outputs.
• A correct algorithm must work for all legitimate inputs, not just most of the time.
2. Ascertaining the Capabilities of the Computational Device
• Algorithms are executed by computers or processors.
• If instructions are executed one after another, it is called a sequential algorithm.
• The designer must consider hardware and software limitations when planning an algorithm.
Algorithmic Problem Solving (Contd. )
3. Choosing Between Exact and Approximate Problem Solving
Algorithms can be:
• Exact: Always produce the correct solution.
• Approximate: Provide a near-correct or heuristic solution (useful when exact solutions are too slow or
impossible).
Data structures play a critical role in designing efficient algorithms.
Formula
Algorithm + Data Structure = Program
4. Algorithm Design Techniques
Algorithm design techniques (also called strategies or paradigms) are general approaches for solving problems.
• They provide guidance for creating algorithms for new problems.
• Algorithms are the cornerstone of computer science.
Examples of design techniques
• Divide and Conquer
• Greedy Method
• Dynamic Programming
• Backtracking
• Branch and Bound
Algorithmic Problem Solving (Contd. )
5. Methods of Specifying an Algorithm
Pseudocode
1. A mix of natural language and programming-like constructs.
2. More precise than plain English, but simpler than actual code.
Flowcharts
1. Graphical representation using standard geometric shapes.
2. Useful for visualization and communication.
Programming Language
1. Final implementation form.
2. Allows execution by a computer.
6. Proving Algorithm Correctness
•After specifying an algorithm, you must prove its correctness.
•Correctness means: it terminates and produces the required output for every valid input.
•A common proof method is mathematical induction, since iterations provide a natural sequence of steps.
•Testing with some sample inputs is useful, but cannot prove correctness fully.
•To show an algorithm is incorrect, a single counterexample is enough.
Algorithmic Problem Solving (Contd. )
7. Analyzing an Algorithm
Efficiency
1. Time efficiency: How fast it runs.
2. Space efficiency: How much memory it uses.
Simplicity
1. Should be precisely defined with mathematical expressions.
2. Simpler algorithms are easier to understand, implement, and debug.
Coding an Algorithm
Most algorithms are eventually implemented as programs. A program allows
empirical analysis:
• Run with different inputs.
• Measure execution time and memory usage.
• Analyze results to understand performance.
Iteration
Definition
•Iteration means repeating a block of code using loops until
a condition is met.
•Common loops: for, while, do-while. #include <stdio.h>
Features int main() {
•Uses looping statements. int i = 1;
•Condition checked repeatedly. while (i <= 5) {
•Example: printing numbers 1 to 10. printf("%d\n", i);
i++;
}
return 0;
}
Recursion
#include <stdio.h>
Fact(n):
int main() { If n == 0 or n == 1
int number; return 1
long long factorial = 1; // Use long long to handle larger factorials Else
int i;
return n * Fact(n - 1)
printf("Enter a integer: ");
scanf("%d", &number);
if (number == 0) {
printf("Factorial of 0 is 1.\n");
} else {
// Calculate factorial using a for loop
for (i = 1; i <= number; i++) {
factorial *= i; // Equivalent to factorial = factorial * i;
}
printf("Factorial of %d is %lld.\n", number, factorial);
}
return 0;
}
Illustrative Problems in Algorithmic Problem Solving
• Find Minimum in a List
• Insert a Card in a Sorted List
• Guess an Integer in a Range
• Towers of Hanoi
Problem 1: Find Minimum in a List
Problem Statement
Given a list of numbers, find the smallest element.
Algorithm (Iterative)
1.Start
2.Input the list (A[1…n])
3.Set min = A[1]
4.For i = 2 to n
1. If A[i] < min, then min = A[i]
5.Output min
6.Stop
Example
List: [7, 2, 9, 4] → Minimum = 2
(Flowchart blocks: Start → Input list → Initialize min → Loop → Compare → Update min → End)
Problem 2: Insert a Card in a Sorted List
Problem Statement
Insert an element into its correct position in a sorted list.
Algorithm
1.Start
2.Input sorted list (A[1…n]) and element x
3.Compare x with elements from end of list
4.Shift elements greater than x one position to the right
5.Insert x at correct position
6.Stop
Example
List: [2, 4, 6, 10], x=5 → [2, 4, 5, 6, 10]
(Start → Input list + element → Compare → Shift → Insert → Output → End)
Problem 3: Guess an Integer in a Range
Problem Statement
Guess a hidden integer in a given range using binary search strategy.
Algorithm
1.Start
2.Input range [low, high]
3.While low <= high:
1. mid = (low + high)/2
2. If mid = target → Found
3. Else if mid < target → low = mid + 1
4. Else high = mid - 1
4.Stop
Example
Target = 42, Range = [1,100] → mid guesses: 50 → 25 → 37 → 43 → 42
(Start → Input range → mid = (low+high)/2 → Compare → Adjust range → Loop → Found → End)
Problem
Move n disks from Source rod to Destination rod using an
Auxiliary rod, following the rules
1.Only one disk can be moved at a time.
2.A larger disk cannot be placed on top of a smaller disk.
Algorithm: TOH(n, source, dest, aux)
1.If n == 1
→ Move disk 1 from source to dest.
→ Return.
2.Else
a. Call TOH(n-1, source, aux, dest)
(Move top n-1 disks from source to auxiliary).
b. Move disk n from source to dest.
c. Call TOH(n-1, aux, dest, source)
(Move top n-1 disks from auxiliary to destination).
Example (n = 3, Source = A, Destination = C, Auxiliary = B)
• Step 1: Move 2 disks from A → B (using C).
• Step 2: Move disk 3 from A → C.
• Step 3: Move 2 disks from B → C (using A).
Moves in order
1.A → C
2.A → B
3.C → B
4.A → C
5.B → A
6.B → C
7.A → C
Total moves = 2𝑛 − 1 = 23 − 1 = 7.
