TOPIC ONE: INTRODUCTION

The Role of Algorithms in Computer Science

What is an Algorithm?

An algorithm is a set of clear, step-by-step instructions that tells how to perform a specific
task.

Simple Examples of Algorithms in Daily Life:

• A recipe (for cooking)

• Directions to find your way in a new city
• Instructions on how to operate a washing machine
• Sheet music (for playing a song)
• Steps for performing a magic trick

Key Point: Algorithms are not only for computers — they exist everywhere we need to solve a
problem in a systematic way.

Algorithms and Computers

Before a computer can perform any task, two things must happen:

1. A correct algorithm for that task must be discovered.

2. The algorithm must be written in a form the computer can understand — this is called a
program.

• Program = A representation of an algorithm that a computer can execute.

• Programming (or Coding) = The process of designing, writing, and putting a program
into a machine.
• Software = Programs + the algorithms they represent.
• Hardware = The physical machinery (monitor, keyboard, CPU, etc.).

Important Distinction:

Software tells the Hardware what to do.

History and Importance of Algorithms

• The study of algorithms started long before computers — it began in mathematics.

• Mathematicians searched for general methods (algorithms) that could solve all
problems of a certain type.

Page 1 of 59
Famous Early Algorithms:

• Long Division Algorithm: Used to divide large numbers.

• Euclidean Algorithm (by Ancient Greek mathematician Euclid): Used to find the
Greatest Common Divisor (GCD) of two positive integers. (This is still taught today
and is very efficient.)

Key Insight: Once an algorithm is created, you don’t need to understand why it works — you
just need to follow the steps correctly. The “intelligence” needed to solve the problem is
captured inside the algorithm.

Why Algorithms Are Central to Computer Science

• Algorithms allow us to capture intelligence (or intelligent behavior) and give it to

machines.
• A machine can only perform a task if a correct algorithm exists for it.
• If no algorithm exists for a problem, then computers cannot solve that problem (at
least not reliably or completely).

This leads to a very important question:

What are the limits of what algorithms (and therefore computers) can do?

Limitations of Algorithms

In the 1930s, mathematician Kurt Gödel published his famous Incompleteness Theorem. It
proved that in any mathematical system that includes basic arithmetic:

• There are some true statements that cannot be proved using algorithms.
• There are limits to what can be solved by following mechanical, step-by-step
procedures.

This discovery:

• Shook the foundations of mathematics.

• Led directly to the birth of Computer Science as a formal field.
• Showed that studying algorithms is not just practical — it is fundamental.

Core Idea of Computer Science:

The study of algorithms is the heart (core) of Computer Science.

Page 2 of 59
Why Algorithms Matter – Extra Important Points for Students

Here’s why algorithms are extremely important:

1. They make complex tasks repeatable and reliable Once written, the same algorithm
can be used by millions of people or computers without mistakes.
2. They turn intelligence into automation Humans discover the smart way to solve a
problem → put it in an algorithm → machines can now do it automatically and very
fast.
3. They are the bridge between human thinking and machine execution Good
algorithms = efficient, fast, and correct programs.
4. They help us understand what computers can and cannot do Not every problem has
an efficient algorithmic solution (e.g., some problems are too slow even for
supercomputers, or impossible).
5. They are the foundation of all software Every app on your phone, every website,
every AI system — they all run because of carefully designed algorithms.

Real-world Analogy: Think of an algorithm like a recipe.

• The cook (computer) doesn’t need to be smart.

• If the recipe (algorithm) is good and followed correctly, the food (result) will be perfect
every time.

Quick Recap (Key Takeaways)

• An algorithm is a step-by-step procedure to solve a problem.

• A program is an algorithm written in a language the computer understands.
• Software = Algorithms + Programs Hardware = Physical machine
• Algorithms existed long before computers (e.g., Euclidean algorithm).
• The intelligence of a machine depends entirely on the quality of its algorithms.
• There are limits to what algorithms can do (Gödel’s Incompleteness Theorem).
• Computer Science is fundamentally the study of algorithms.

History Of Computers

1. Ancient Beginnings: The Abacus

• The abacus is one of the earliest computing devices, with roots in ancient China, and
later used by Greeks and Romans.
• It consists of beads on rods in a wooden frame. Moving the beads represents and stores
numbers.

Page 3 of 59
 • Limitation: It only stores data. A human operator must control the steps of any
calculation. So, it's a data storage tool, not a full "computer" by itself.

Mechanical Calculators (17th–19th Century)

After the Middle Ages, inventors used gears to build better machines:

• Blaise Pascal (France, 1623–1662): Built the Pascaline — a mechanical adding

machine. It could only do addition. The steps were fixed in the machine's design.
• Gottfried Wilhelm Leibniz (Germany, 1646–1716): Improved on Pascal with the
Stepped Reckoner. It could do addition, subtraction, multiplication, and division.
The operator could choose the operation, but the algorithms were still built into the
hardware.
• Charles Babbage (England, 1792–1871):
o Designed the Difference Engine (only a small model was built) for
mathematical tables.
o Envisioned the Analytical Engine — a much more advanced, programmable
machine. It would read instructions from punched cards (holes in paper cards)
and print results on paper to avoid errors.
o This was a huge leap: the machine could be told what to do instead of having
everything fixed in its gears.

Augusta Ada Byron (Ada Lovelace) (1815–1852) worked with Babbage. She wrote detailed
notes showing how the Analytical Engine could be programmed to solve different problems,
including a famous example for calculating Bernoulli numbers. She is widely regarded as the
world's first computer programmer. She even imagined the machine could do more than just
numbers (e.g., music or graphics) — a visionary idea.

The Idea of Punched Cards

• Joseph Jacquard (France, 1752–1834): In 1801, he invented a programmable

weaving loom. Patterns were controlled by thick cards with holes. Changing the cards
changed the design easily. This was the first practical use of "programming" via
punched cards.
• Herman Hollerith (USA, 1860–1929): Borrowed the punched-card idea for the 1890
U.S. Census. His tabulating machine processed data much faster than manual methods
and saved the government years of work and millions of dollars. His company later
became IBM.

Punched cards remained a common way to input data and programs into computers until the
1970s.

Page 4 of 59
Early 20th Century: Electromechanical Machines

• Technology advanced from pure gears to electromechanical systems (using electrically

controlled relays).
• Examples: George Stibitz's machine (1940, Bell Labs) and the Harvard Mark I (1944,
Howard Aiken + IBM).

These were big but soon outdated because vacuum tubes allowed fully electronic computers.

The First Electronic Computers (1940s)

• Atanasoff-Berry Computer (ABC) (1937–1942, Iowa State University): Built by John

Atanasoff and Clifford Berry. It was an early electronic digital computer using vacuum
tubes. (Note: A 1973 court case later ruled that ideas from the ABC influenced the
ENIAC, giving Atanasoff recognition for early electronic computing concepts.)
• Colossus (1940s, UK, Tommy Flowers): Built to break German codes during WWII.
Several were made, but kept secret for decades due to national security.
• ENIAC (Electronic Numerical Integrator and Computer, 1940s): Developed by John
Mauchly and J. Presper Eckert at the University of Pennsylvania. It was a large,
general-purpose electronic computer used for calculations (e.g., artillery tables). Often
called one of the first general-purpose electronic computers.

These machines were room-sized and used thousands of vacuum tubes (which generated a lot
of heat and often failed).

Key Technological Breakthroughs

• Transistor (1947): Invented by William Shockley, John Bardeen, and Walter Brattain
at Bell Labs. Much smaller, more reliable, and used less power than vacuum tubes.
They won the Nobel Prize.
• Integrated Circuit (IC) / Microchip (1958): Jack Kilby (and independently Robert
Noyce) developed ways to put entire circuits on a single small chip. Kilby also won a
Nobel Prize. This made computers dramatically smaller, cheaper, and more powerful.

Moore's Law (observed trend): Processing power roughly doubled every two years — a
pattern that continued for decades.

Personal Computers and the PC Era

• In the 1970s, hobbyists built homemade computers using available chips.

Page 5 of 59
 • Steve Jobs and Stephen Wozniak created the Apple I and II. In 1976, they founded
Apple Computer (now Apple Inc.). Their machines were user-friendly and helped
popularize personal computing.
• Other early companies: Commodore, Heathkit, Radio Shack.
• 1981: IBM launched its Personal Computer (PC). Microsoft (founded by Bill Gates
and Paul Allen) provided the operating system software (MS-DOS). The IBM PC
became hugely successful and set the standard. "PC" now often refers to computers
compatible with this design (mostly running Windows).

The Internet and World Wide Web

• Late 20th century: Computers were linked globally via the Internet.
• Tim Berners-Lee (British scientist) invented the World Wide Web (WWW) in 1989–
1991. He created hypertext links so documents could connect easily. This turned the
Internet into an easy-to-use information network.
• Search engines (Google, Yahoo, Microsoft Bing) were developed to organize and find
information on the Web.

Miniaturization and Modern Devices

• Computers shrank from room-sized to desktop → laptop → tiny chips.

• Today, embedded computers are everywhere: in cars (for GPS, engine control, voice
systems), appliances, and especially smartphones.
• Smartphones are powerful general-purpose computers (with cameras, sensors,
touchscreens, accelerometers, GPS, wireless connectivity). Many say they have had an
even bigger impact on society than the PC revolution.

Quick Summary of the Big Ideas

• Progression: Manual (abacus + human) → Mechanical (gears, fixed tasks) →

Programmable (punched cards) → Electromechanical → Electronic (vacuum tubes) →
Transistor → Integrated circuits → Microcomputers → Internet/Web → Ubiquitous
tiny computers.
• Key theme: Each step made computers smaller, faster, cheaper, more reliable, and
more flexible.
• Computing moved from specialized tools for scientists/government to everyday devices
that anyone can use.

This timeline shows how computing evolved from simple counting aids to the powerful,
connected devices we rely on today. The contributions of visionaries like Babbage, Lovelace,
Hollerith, and the teams behind transistors and chips were foundational.

Page 6 of 59
EXAMINATION QUESTIONS
Section 1: Short Answer Questions (2–5 marks each)

1. Define the term algorithm.

2. What is a program? How is it different from an algorithm?
3. State the difference between software and hardware.
4. Name any two early mechanical computing devices and their inventors.
5. Who is regarded as the world’s first computer programmer and why?
6. What was the main purpose of Herman Hollerith’s punched card machine?
7. Name the two inventors of the transistor and explain its importance.
8. What is Moore’s Law?
9. Mention one major contribution of Tim Berners-Lee.
10. What is the Euclidean algorithm used for?

Section 2: Medium Answer Questions (6–10 marks each)

1. Explain the role of algorithms in computer science. Why are algorithms considered the
core of the discipline?
2. Using examples, explain how an algorithm captures “intelligence” and allows machines
to perform useful tasks.
3. Describe the Euclidean algorithm for finding the Greatest Common Divisor (GCD).
Why is it a good example of an early algorithm?
4. Trace the evolution of computing devices from the abacus to Babbage’s Analytical
Engine. Highlight the major improvements at each stage.
5. Explain how punched cards contributed to the development of programmable
machines. Mention Jacquard and Hollerith in your answer.
6. Describe the technological breakthroughs (transistor and integrated circuit) that made
modern computers possible. What problems did they solve?
7. Compare the ENIAC with modern smartphones in terms of size, power, and capability.

Section 3: Long Answer / Essay Questions (12–15 marks each)

1. “The study of algorithms forms the core of computer science.” Discuss this statement
with reference to the limitations of algorithms as shown by Kurt Gödel’s
Incompleteness Theorem.
2. Give a detailed account of the history of computing from the abacus to the development
of personal computers (PCs). Highlight the contributions of at least five key
individuals or teams.

Page 7 of 59
 3. Explain how the concept of programmability evolved in computing history. Use
examples from Babbage’s Analytical Engine, Jacquard’s loom, and modern computers
to support your answer.
4. Discuss the impact of miniaturization and the rise of smartphones on society. How does
this compare to the earlier PC revolution?
5. “Algorithms existed long before computers, but computers made algorithms truly
powerful.” Do you agree with this statement? Support your answer with examples from
both topics.
TOPIC TWO: Data Storage
Bits and Their Storage

What is a Bit?

At the lowest level, all data inside a modern computer is stored and processed as bits (short for
binary digits).

• A bit is the smallest unit of data in a computer.

• It can have only two possible values: 0 or 1.
• The bit 0 usually represents false or off.
• The bit 1 usually represents true or on.

Important Idea: Although we think of bits as numbers, they are actually just patterns. These
patterns can represent:

• Numbers
• Letters and characters (text)
• Colors
• Images
• Sounds
• Instructions

Key Concept – Abstraction Computers use different levels of abstraction to represent data:

• At the lowest level: Everything is bits (0s and 1s).

• At higher levels: Bits are grouped to represent meaningful things (numbers, text,
images, etc.).

Essential Knowledge Statements:

• Digital data is represented by abstractions at different levels.

• At the lowest level, all digital data is represented by bits.

Page 8 of 59
 • Bits can represent anything — not just numbers.

Boolean Operations (Logic Gates)

To manipulate individual bits, computers use Boolean operations. These are named after
mathematician George Boole (1815–1864).

The three basic Boolean operations are:

Operation Symbol Meaning Example Use

AND ∧ True only if both inputs are true Both conditions must be
satisfied
OR ∨ True if at least one input is true Either condition is enough
XOR ⊕ True if exactly one input is true One must be true, the other
(exclusive or) false
NOT ¬ Reverses the input (0 becomes 1, 1 Opposite of the input
becomes 0)
Truth Tables (Very Important!) AND
Operation:
Input P Input Q Output (P AND Q)
0 0 0
0 1 0
1 0 0
1 1 1
OR Operation:
Input P Input Q Output (P OR Q)
0 0 0
0 1 1
1 0 1
1 1 1
XOR Operation:
Input P Input Q Output (P XOR Q)
0 0 0
0 1 1
1 0 1
1 1 0
NOT Operation:

Page 9 of 59
 Input Output (NOT Input)
0 1
1 0

Page 10 of 59
Logic Gates and Flip-Flops

• Logic Gates: Hardware devices that perform Boolean operations (AND, OR, XOR,
NOT). o They are the building blocks of all digital circuits.
o Represented by special symbols in circuit diagrams.

Common Logic Gate Symbols:

• AND → Rounded rectangle or D-shape

• OR → Curved shape
• XOR → Curved with extra line
• NOT → Triangle with a small circle
• Flip-Flop: A special circuit made from gates that can store one bit of information.
o It “remembers” its value (0 or 1) even after the input changes.
o Flip-flops are the basic units of computer memory. o They can hold their
state until a new signal change it.
Why Flip-Flops Matter: They allow computers to store data temporarily (memory) by using
feedback loops in circuits.

Page 11 of 59
2. Hexadecimal Notation (Base-16)

Page 12 of 59
Long strings of bits (e.g., 10110110) are hard for humans to read. So, we use Hexadecimal
(short for Hex).

• Hex uses 16 symbols: 0–9 and A–F.

• Each hex digit represents exactly 4 bits.

Hexadecimal Table:
4-bit Binary Hexadecimal Decimal
0000 0x0 0
0001 0x1 1
0010 0x2 2
0011 0x3 3
0100 0x4 4
0101 0x5 5
0110 0x6 6
0111 0x7 7
1000 0x8 8
1001 0x9 9
1010 0xA 10
1011 0xB 11
1100 0xC 12
1101 0xD 13
1110 0xE 14
1111 0xF 15
Advantage of Hex: It is much shorter and easier to work with than binary. Programmers and
engineers use hex frequently when working with memory addresses, colors, or machine code.

Example: Binary: 1010 1111 → Hex: 0xAF

1.3 Mass Storage

Mass storage (also called secondary storage or auxiliary storage) refers to non-volatile
storage devices used to store large amounts of data permanently, even when the computer is
powered off. Unlike main memory (RAM), which is fast but volatile and relatively small,
mass storage devices are slower but have much larger capacity and retain data without power.

Why do we need Mass Storage?

• Main memory (RAM) is expensive and limited in size.

• Data must persist even when the computer is turned off.

Page 13 of 59
 • Mass storage provides high capacity, low cost per gigabyte, and non-volatility.

Advantages of Mass Storage Systems

• Large storage capacities

• Low cost
• Ability to remove the storage medium from the machine (in some cases)
• Data persists without power

Disadvantages

• Slower access compared to main memory (especially mechanical devices)

• Mechanical devices (HDDs, magnetic tapes) have moving parts → prone to failure and
slower
• Electronic devices (SSDs, flash) are faster and more reliable but historically more
expensive per GB

Types of Mass Storage Systems

1. Magnetic Systems

Example: Hard Disk Drive (HDD)

• Uses one or more thin spinning disks (platters) coated with magnetic material.
• Data is stored as magnetic patterns (0s and 1s).
• Read/Write heads float just above the platter surface on a cushion of air.
• The disk spins at high speed (typically 5,400 – 15,000 RPM).
• The access arm moves the heads radially to access different tracks.

Key Concepts:

• Track: Concentric circles on the platter.

• Sector: Smallest addressable unit on a track (usually 512 bytes or 4KB).
• Cylinder: All tracks at the same position on all platters.
• Seek time: Time for the head to move to the correct track.
• Rotational latency: Time for the platter to rotate so the desired sector is under the head.
• Access time = Seek time + Rotational latency + Transfer time.
• Data transfer rate: Speed at which data moves between disk and computer (measured
in MB/s or GB/s).

Page 14 of 59
Important Note: Modern HDDs use Perpendicular Magnetic Recording (PMR) or Shingled
Magnetic Recording (SMR) to increase density. However, they still suffer from mechanical
limitations and are gradually being replaced by SSDs for performance-critical tasks.

2. Optical Systems

Example: Compact Disc (CD), DVD, Blu-ray

Page 15 of 59
 • Uses laser light to read and write data.
• Data is stored as tiny pits and lands on a reflective surface.
• A laser beam reflects differently from pits and lands → detected as 0s and 1s.
• CD ≈ 700 MB, DVD ≈ 4.7 GB (single layer), Blu-ray ≈ 25–50 GB+.

How it works:

• The disc spins while a laser head moves radially.

• Information is stored in a spiral track starting from the center outward (unlike HDD’s
concentric tracks).
• Higher density near the center, lower near the outer edge.

Advantages:

• Cheap to produce (especially read-only media)

• Good for distributing software, music, movies Disadvantages:
• Slower than HDDs and much slower than SSDs
• Easily scratched/damaged

Page 16 of 59
Page 17 of 59
Solid-State / Flash Memory Systems

Examples: SSD (Solid-State Drive), USB flash drives, memory cards (SD, microSD), eMMC,
SSDs in laptops/phones.

• No moving parts → much faster, more reliable, more shock-resistant, and silent.
• Uses NAND flash memory (electrically erasable programmable read-only memory).
• Data is stored in floating-gate transistors (trapped electrons represent bits).
• Wear-leveling algorithms are used to distribute writes evenly across memory cells
because each cell has a limited number of write/erase cycles.

Key Performance Terms:

• Bandwidth (or throughput): Amount of data transferred per second (MB/s or GB/s). •
Latency: Time delay between request and data delivery (much lower in SSDs than
HDDs).
• IOPS (Input/Output Operations Per Second): Very important for random access
performance.

Advantages over HDDs:

• Extremely fast random access

• Low power consumption
• No mechanical failure risk
• Better for portable devices

Disadvantages:

• Higher cost per GB (though gap is closing)

• Limited write endurance (mitigated by wear-leveling and over-provisioning)

Modern Context (added explanation): Today, most new computers and smartphones use
SSDs or NVMe SSDs (connected via PCIe) which are dramatically faster than traditional
SATA SSDs. HDDs are still used for bulk/cold storage due to lower cost per terabyte.

Page 18 of 59
 Performance Measurements (Very Important)
1. Seek Time – Time for heads to move to the correct track.
2. Rotational Latency – Average half rotation of the disk.
3. Access Time – Total time to locate and begin reading data.
4. Transfer Rate / Bandwidth – How fast data is actually read/written.
5. Latency – Overall responsiveness.

Rule of thumb (added):

• HDD: Access time ~5–10 ms

• SSD: Access time ~0.05–0.1 ms (50–100× faster)
• RAM: Access time ~10–100 nanoseconds

Summary Comparison
Feature HDD (Magnetic) Optical (CD/DVD) SSD (Flash)
Technology Magnetic + Mechanical Laser + Reflective Electronic (NAND Flash)
Moving Parts Yes Yes (spinning disc) No
Speed Slow Very Slow Very Fast
Durability Moderate Fragile (scratches) High (shock resistant)
Cost per GB Lowest Low Higher
Best For Bulk storage Distribution Performance & Portability

Essential Knowledge Statements

• The choice of storage media affects both the speed and longevity of the data it
contains.
• Bandwidth: Amount of data transferred per unit time.
• Latency: Time between request and response.

Key Takeaway for Students: Modern systems use a storage hierarchy:

1. Registers & Cache (fastest, smallest)

2. RAM (fast, volatile)
3. SSD (fast secondary storage)
4. HDD (cheaper, high capacity)
5. Cloud / Tape (archival)

Page 19 of 59
Representing Information as Bit Patterns

Computers can only understand and process binary (bits — 0s and 1s). All types of
information — text, numbers, images, sound, and video — must be converted into sequences
of bits before they can be stored or processed. This section explains how different types of
data are encoded into bit patterns.

Representing Text

Text is represented using character encoding standards — rules that map each character
(letter, number, symbol) to a unique binary pattern.

Historical Development:

• Early systems used many different incompatible codes.

• In the 1960s, ASCII (American Standard Code for Information Interchange) became the
dominant standard. o Originally 7-bit (128 characters) — enough for English
uppercase/lowercase letters, digits, and common punctuation. o Later extended to 8-
bit (256 characters) to include more symbols.

ASCII is one of the earliest and simplest character encoding standards, developed in the
1960s.

• It uses 7 bits per character → 2⁷ = 128 possible characters (codes 0 to 127).

• These include:
o Control characters (0–31): non-printable codes like newline (\n), tab, carriage
return, etc.
o Printable characters (32–126): English uppercase/lowercase letters (A–Z, a–z),
digits (0–9), punctuation, and symbols like space, !, ", #, etc.
• In practice, computers use 8-bit bytes, so the 8th bit was often unused or extended for
256 characters in various "extended ASCII" versions (e.g., ISO-8859-1 or Windows-
1252). However, these extensions were incompatible across systems and languages.
Example: The word "Hello" in ASCII

Example from the notes: The word "Hello" in ASCII (8-bit) is shown as:

text
01001000 01100101 01101100 01101100 01101111

Limitations of ASCII:

Page 20 of 59
 • Only supports English (and very basic Western characters).
• Cannot represent accented letters (é, ñ, ç), non-Latin scripts (Arabic, Chinese, Hindi,
Japanese), or modern symbols like emojis.
• Different countries created conflicting 8-bit extensions, leading to "mojibake" (garbled
text) when files were opened on the wrong system.

Modern Standard: Unicode + UTF-8

• ASCII is too limited for international languages (e.g., Chinese, Arabic, emojis).
• Unicode assigns a unique number (code point) to every character in every writing
system.
• UTF-8 (Unicode Transformation Format - 8-bit) is the most popular encoding today.
o Backward compatible with ASCII. o Uses 1 to 4 bytes per character. o
Highly efficient for English text (most characters use only 1 byte) but
supports global languages.

Why UTF-8 Dominates Today

• Efficiency: English text takes almost no extra space.
• Compatibility: Old ASCII files work perfectly.
• Universality: Handles any language or symbol without mojibake.
• It is the default encoding for the web (HTML, JSON, XML), modern programming
languages (Python 3, JavaScript, etc.), and operating systems.

Representing Numeric Values

Numbers are stored using the binary number system (base-2).

Key Points:

• In binary, each digit (bit) represents a power of 2.

• Example: The binary number 1011 = 11 in decimal.

text
0000 = 0
0001 = 1
0010 = 2
0011 = 3
...
1000 = 8

Page 21 of 59
 • For larger numbers (e.g., integers from 0 to 65,535), we use 16 bits.
• Computers also use two's complement to represent negative numbers (explained in
later sections).
• Hexadecimal (base-16) is often used by programmers because it is a compact way to
write binary (one hex digit = 4 bits).

Important Addition for Students:

• A single byte = 8 bits = 256 possible values (0–255).

• Word = usually 32 or 64 bits (depends on the CPU architecture).
• Floating-point numbers (for decimals like 3.14) use a completely different format
(IEEE 754 standard) to represent very large or very small numbers with a mantissa and
exponent.

Representing Images

Computers represent images using digital data — a series of numbers (binary: 0s and 1s).
There is no "picture" inside the computer; everything is broken down into numbers. The most
common way computers store images is called Raster or Bitmap format.

• An image is divided into a grid of tiny colored squares called pixels (picture elements).
• Each pixel has a specific color.
• The computer stores the color value of every single pixel.

Example: A small 3×2 image (very tiny) has 6 pixels. The computer stores 6 color values.

How Colors Are Represented (Color Models)

a) RGB Color Model (Most Common)

• Every color is created by mixing Red, Green, and Blue light.

• Each channel (R, G, B) has a value from 0 to 255 (8 bits).
• Total colors possible = 256 × 256 × 256 = 16.7 million colors (24-bit color).

How one pixel is stored:

• Red = 255, Green = 0, Blue = 0 → Pure Red

• Red = 0, Green = 0, Blue = 255 → Pure Blue
• Red = 255, Green = 255, Blue = 255 → White
• Red = 0, Green = 0, Blue = 0 → Black

RGBA (RGB + Alpha)

Page 22 of 59
 • Adds a 4th channel called Alpha (transparency).
• Alpha = 0 → Fully transparent
• Alpha = 255 → Fully opaque

3. How Data is Stored in Memory

A single pixel in a standard color image uses 24 bits (3 bytes):

Channel Bits Value Range

Red 8 0–255
Green 8 0–255
Blue 8 0–255

Example: A 1920 × 1080 Full HD image has:

• 1920 × 1080 = 2,073,600 pixels

• Each pixel = 3 bytes
• Total size (uncompressed) ≈ 6.22 MB

4. Image File Formats

Different formats compress or organize this pixel data differently:

Format Type Compression Best For Transparency

JPEG Lossy High Photos, web images No
PNG Lossless Medium Logos, screenshots, diagrams Yes
GIF Lossless Medium Simple animations Yes (limited)
BMP Uncompressed None Raw data, high quality No
WebP Lossy/Lossless Very High Modern web Yes
SVG Vector - Logos, icons, scalable graphics Yes

Note: JPEG loses some quality when saving (lossy) to reduce file size. PNG preserves quality.

Disadvantages:

• File size grows quickly with resolution.

• When you zoom in too much, pixels become visible ("pixelation").

Vector Images (Alternative Representation)

Page 23 of 59
Unlike raster images, vector images do not store pixels. Instead, they store mathematical
instructions:

• "Draw a circle at position (100,100) with radius 50"

• "Draw a line from (0,0) to (200,300)"

Advantages:

• Can be scaled to any size without losing quality.

• Much smaller file size for simple graphics.
• Used in logos, icons, diagrams (SVG format).

How Computers Display Images

1. Image file is loaded from storage.

2. CPU/GPU decodes the file into raw pixel data.
3. Pixel data is sent to the frame buffer (special memory in the graphics card).
4. The monitor reads the frame buffer millions of times per second and lights up each
pixel accordingly.

Bit Depth (Color Precision)

Bit Depth Colors Available Common Use

1-bit 2 (Black & White) Old displays
8-bit 256 Grayscale, GIF
16-bit 65,536 High-quality photos
24-bit 16.7 million Standard True Color
32-bit 16.7 million + Alpha RGBA

Summary: Step-by-Step Representation

1. Capture → Camera/phone sensor records light as numbers.

2. Processing → Converted into RGB pixel grid.
3. Storage → Saved as a file (JPEG, PNG, etc.) with header + compressed pixel data.
4. Display → Decoded back into pixels and shown on screen.

Key Takeaway: An image in a computer is just a long list of numbers telling the screen
what color each pixel should be at a specific positio

Representing Sound

Page 24 of 59
Computers represent sound as digital data — a long sequence of numbers. Just like images,
sound is converted from analog (continuous waves) to digital (discrete numbers) through a
process called digitization.

Understanding Sound Waves (Analog Signal)

• Sound is a pressure wave caused by vibration (e.g., vocal cords, speaker cone).
• It has two main properties:
o Amplitude → Loudness (height of the wave)
o Frequency → Pitch (how many waves per second, measured in Hertz - Hz)

Human hearing range: 20 Hz to 20,000 Hz (20 kHz).

The Digitization Process (ADC – Analog to Digital Conversion)

To store sound in a computer, we use these three key steps:

a) Sampling

• The continuous sound wave is measured (sampled) at regular time intervals.

• Sampling Rate = How many times per second we measure the wave.
• Measured in Hertz (Hz) or kHz.

Common Sampling Rates:

Sampling Rate Usage Quality

8,000 Hz Telephone Low
44,100 Hz CD Audio, MP3 Standard (Good)
48,000 Hz Professional video High
96,000 Hz Studio recording Very High

Rule (Nyquist Theorem): Sampling rate must be at least twice the highest frequency we want
to capture. That’s why 44,100 Hz is used (captures up to 22,050 Hz).

b) Quantization

• Each sampled value is assigned a number (rounded to the nearest value).

• Bit Depth = How many bits are used to represent each sample.

Page 25 of 59
Common Bit Depths:

Bit Depth Number of Levels Dynamic Range Use Case

8-bit 256 Poor Old games
16-bit 65,536 Good CD Audio
24-bit 16.7 million Excellent Studio recording
32-bit Over 4 billion Highest Professional mixing

c) Encoding

• The numbers are stored in binary format.

3. How One Second of Audio is Stored

Example: CD Quality Audio

• Sampling Rate: 44,100 Hz

• Bit Depth: 16-bit
• Channels: 2 (Stereo)

Calculation:

• Samples per second = 44,100

• Bytes per sample = 2 (16-bit = 2 bytes)
• Channels = 2
• Total bytes per second = 44,100 × 2 × 2 = 176,400 bytes/second ≈ 176 KB/second

One minute of CD audio ≈ 10.6 MB

Audio File Formats

Format Compression Quality Loss Best For Common Use

WAV Uncompressed None Highest quality Studio, editing
MP3 Lossy Some Small size Music, streaming
AAC Lossy Less than Better quality than MP3 YouTube,
MP3 iTunes
OGG Lossy Good Open source Games,
streaming
FLAC Lossless None High quality, smaller than Audiophiles
WAV

Page 26 of 59
Lossy formats (like MP3) remove sounds humans can barely hear to reduce file size.

5. Multi-Channel Audio

• Mono → 1 channel (same sound in both ears)

• Stereo → 2 channels (Left + Right)
• Surround Sound → 5.1, 7.1 channels (front, rear, center, subwoofer)

6. How Computers Play Sound (DAC)

1. Audio file is read from storage.

2. CPU/GPU decodes the file into raw digital samples.
3. Digital-to-Analog Converter (DAC) converts numbers back into electrical signals.
4. Amplifier strengthens the signal.
5. Speaker vibrates and creates sound waves.

Modern devices (phones, laptops) have built-in high-quality DACs.

Key Concepts Summary

Concept Meaning Importance

Sampling How often we measure the wave Determines frequency range
Rate
Bit Depth Precision of each measurement Determines dynamic range (loud vs
soft)
Channels Number of audio tracks Spatial sound
(mono/stereo)
Bitrate Total data per second (kbps) Quality vs file size

8. Real-World Example

Song: 3 minutes long, MP3 at 320 kbps

• Size ≈ 7–8 MB
• Same song in WAV (uncompressed) ≈ 30–40 MB

Page 27 of 59
Page 28 of 59
Binary Notation (Base-2)
Binary uses only two digits: 0 and 1. Each position represents a power of 2 (starting from the
rightmost digit as 2⁰).

Key Idea: Just like in decimal (base-10), the value = digit × (base^position)

Example: Binary 1011

Position 3 2 1 0
Power 2³ 2² 2¹ 2⁰
Value 8 4 2 1
Digit 1 0 1 1

Calculation: 1×8 + 0×4 + 1×2 + 1×1 = 11 (decimal)

Visual Tip: Think of it as switches: 1 = ON, 0 = OFF. Each position is double the previous
one.

Converting Binary → Decimal

Method: Multiply each bit by its position value and add.

Example: Binary 100101

From right (position 0):

• 1 × 2⁰ = 1
• 0 × 2¹ = 0
• 1 × 2² = 4
• 0 × 2³ = 0
• 0 × 2⁴ = 0
• 1 × 2⁵ = 32

Total = 32 + 4 + 1 = 37

Converting Decimal → Binary (Repeated Division by 2)

Algorithm:

1. Divide the number by 2.

2. Record the remainder (0 or 1).
3. Repeat with the quotient until quotient = 0.

Page 29 of 59
 4. Read remainders from bottom to top.

Example: Convert 13 to binary

text
13 ÷ 2 = 6 remainder 1
6 ÷ 2 = 3 remainder 0
3 ÷ 2 = 1 remainder 1
1 ÷ 2 = 0 remainder 1

Binary: 1101 (read remainders upward)

Visual Flow:

text
13
↓
6 r1
↓
3 r0
↓
1 r1
↓
0 r1 ← Read up: 1101

4. Binary Addition

Rules (very simple):

1 0 1
0 0 0
1 1 10 (write 0, carry 1)

Carry works just like in decimal.

Example: 1110 + 1011

text
1110
+1011
---------

Page 30 of 59
1 1 0 0 1 (with carries)

Step-by-step tip: Always move right to left. When sum = 2, write 0 and carry 1.

Binary Fractions (After the Binary Point)

Digits after the point represent negative powers of 2:

• 1st position = 2⁻¹ = 0.5

• 2nd position = 2⁻² = 0.25
• 3rd position = 2⁻³ = 0.125
• etc.

Example: 101.101

• Integer part: 101 = 5

• Fractional part: 101 = 0.5 + 0.125 = 0.625

Total = 5.625 (decimal)

Visual:

text
101.101
842 ½¼⅛

Analog vs Digital (Quick Summary)

• Analog: Continuous (like water level in a bucket). Prone to small errors.

• Digital (Binary): Discrete (only 0s and 1s). Very reliable, easy to store and copy
without degradation.

Modern computers use digital (binary) because it is robust against noise.

Page 31 of 59
Storing Integers

Why Special Systems Are Needed?

Computers use fixed-length binary patterns (e.g., 4 bits, 8 bits, 32 bits). We need a way to
represent both positive and negative integers using the same number of bits.

1. Two’s Complement Notation

Key Features:

• Most popular system in modern computers.

• The leftmost bit is the sign bit:
o 0 = Positive (or zero)
o 1 = Negative
• Positive numbers are represented normally.
• Negative numbers are represented using a special method.

How to Create Two’s Complement (for negative numbers):

1. Write the positive binary of the number.

Page 32 of 59
 2. Invert all bits (change 0→1 and 1→0) → One’s Complement.
3. Add 1 to the result.

Example (4-bit): Represent -6

• +6 = 0110
• Invert = 1001
• Add 1 = 1010 → -6 in two’s complement

4-Bit Two’s Complement Table

Bit Pattern Value
0111 +7
0110 +6
0101 +5
0000 0
1111 -1
1110 -2
1101 -3
1010 -6
1000 -8

Range in 4 bits: -8 to +7

Important Rule: To negate any number in two’s complement → Invert bits and add 1.

2. Addition & Subtraction in Two’s Complement

Great Advantage: You add numbers exactly the same way whether they are positive or
negative. No special subtraction hardware needed.

Example: 5 + (-3) in 4-bit

text
0101 (5)
+ 1101 (-3)
------
0010 (2) ← Correct! (Carry out is ignored)

Overflow occurs when the result of an arithmetic operation (addition or subtraction) is too
large or too small to be represented within the fixed number of bits available.

Page 33 of 59
In fixed-bit systems (e.g., 4-bit, 8-bit, 32-bit), the range of numbers is limited. If the answer
falls outside that range, the computer cannot store it correctly — it produces a wrong answer.

Overflow: Occurs when result is too big to fit in the fixed bits (e.g., 7 + 1 = 8 in 4 bits becomes
wrong). Detection: When sign bit is incorrect.

Range in Two’s Complement

Bits Positive Range Negative Range Total Range

4-bit 0 to +7 -1 to -8 -8 to +7
8-bit 0 to +127 -1 to -128 -128 to +127

How Overflow Happens

Example 1: Positive + Positive (Exceeds Max Positive)

Add 6 + 3 in 4-bit Two’s Complement:

text
0110 (+6)
+ 0011 (+3)
------
1001 ← Result

• Correct answer should be +9

• But in 4-bit, 1001 = -7 (wrong!)

This is overflow.

Example 2: Negative + Negative (Exceeds Max Negative)

Add -5 + -4 in 4-bit:

text
1011 (-5)
+ 1100 (-4)
------

Page 34 of 59
 0111 ← Result (with carry out)

• Correct answer should be -9

• But result 0111 = +7 (wrong!)

This is also overflow.

How to Detect Overflow in Two’s Complement

There is a simple rule:

Overflow occurs when the sign of the result is different from what you expect.

More precisely:

• If you add two positive numbers and get a negative result → Overflow
• If you add two negative numbers and get a positive result → Overflow

Carry-in vs Carry-out method (technical): Overflow = Carry into the sign bit XOR Carry out
of the sign bit.

But for students, the sign rule above is easiest.

Example Without Overflow (Mixed Signs)

Add 5 + (-3):

text
0101 (+5)
+ 1101 (-3)
------
0010 (+2) ← Correct

No overflow — signs were different.

What Does the Computer Actually Do?

• It wraps around (modular arithmetic).

• Example in 4-bit:

Page 35 of 59
 o 7 + 1 = 1000 → interpreted as -8
o This is like a clock going from 12 → 1

Summary Table

Operation Expected Result 4-bit Result Overflow? Reason

7+1 +8 -8 Yes + to -
-8 + -1 -9 +7 Yes - to +
5 + (-3) +2 +2 No -
-5 + 3 -2 -2 No -

Key Takeaways for Students

1. Overflow is dangerous because the computer gives wrong results silently.

2. Two’s Complement makes addition easy, but you must check for overflow.
3. Modern computers use 32-bit or 64-bit integers to reduce overflow risk (but it can still
happen).
4. In programming, languages like Python handle big integers automatically, but C, Java,
etc., can overflow.

Excess Notation (Bias Notation)

Another way to represent signed numbers. Excess notation is a way to represent positive and
negative integers using unsigned binary patterns by applying a bias (offset).

Instead of using a sign bit (like Two’s Complement), we shift the entire range so that some
patterns represent negative numbers and others represent positive numbers.

How Excess Notation Works

Steps:

1. Decide the number of bits (n).

2. Choose a bias (usually 2^(n-1)).
3. To store a number X:
o Compute X + bias
o Convert that result to binary (unsigned).
4. To decode a bit pattern:
Page 36 of 59
 o Convert the bit pattern to decimal → call it Y
o Actual value = Y - bias

Example 1: 3-Bit Excess-4 (Bias = 4)

Bias = 4 (which is 2²)

Bit Pattern Decimal Value of Pattern Actual Value (Pattern - 4)

000 0 -4
001 1 -3
010 2 -2
011 3 -1
100 4 0
101 5 +1
110 6 +2
111 7 +3

Range: -4 to +3

Example 2: 4-Bit Excess-8 (Bias = 8)

Bias = 8 (2³)

Bit Pattern Y (Unsigned Decimal) Actual Value (Y - 8)

0000 0 -8
0001 1 -7
0010 2 -6
0100 4 -4
0111 7 -1
1000 8 0
1001 9 +1
1010 10 +2
1111 15 +7

Range: -8 to +7

Step-by-Step: How to Encode and Decode

Page 37 of 59
Example: Represent -5 in 4-bit Excess-8

1. Add bias: -5 + 8 = 3
2. Convert 3 to 4-bit binary: 0011
3. So, -5 is stored as 0011

Decode 0011:

1. Convert 0011 to decimal = 3

2. Subtract bias: 3 - 8 = -5 ✓

Another Example: Represent +6 in 4-bit Excess-8

1. 6 + 8 = 14
2. 14 in binary = 1110
3. Stored as 1110

Decode 1110:

• 14 - 8 = +6 ✓

Why is Zero Special?

• Zero is represented by the bit pattern equal to the bias.

• In Excess-8 → 1000 (8 in decimal) represents 0.

Comparison with Two’s Complement (4-bit)

Number Two’s Complement Excess-8

+7 0111 1111
+1 0001 1001
0 0000 1000
-1 1111 0111
-8 1000 0000

Key Differences:

• Two’s Complement has a sign bit (leftmost bit).

• Excess Notation has no sign bit — zero is in the middle.
• Two’s Complement is much more common for integers in CPUs.
• Excess Notation is mainly used in floating-point exponents.

Page 38 of 59
Quick Practice

1. Represent -3 in 4-bit Excess-8. Answer: 0101 (because -3 + 8 = 5 → 0101)

2. What number does 1011 represent in 4-bit Excess-8? Answer: 11 - 8 = +3

3. Represent +4 in 4-bit Excess-8. Answer: 1100

Key Comparison

Feature Two’s Complement Excess Notation

Most widely used Yes Less common
Sign bit Leftmost bit No explicit sign bit
Addition/Subtraction Same circuit Needs adjustment
Zero representation Single (000...0) Bias value

Storing Fractions
Integers (whole numbers) are easy to store — just convert them to binary. Fractions (like 2.75,
0.1, or 1/3) are harder because the computer must also store the position of the decimal point
(called the radix point in binary). Solution: Computers use Floating-Point Notation — a
smart way to represent numbers with a decimal point using scientific notation in binary.

Floating-Point Notation

Think of it like scientific notation you learned in school: 2.75 × 10³ = 2750

In computers, instead of base 10, they use base 2 (binary). A floating-point number has three
main parts:

1. Sign Bit – Tells if the number is positive or negative (0 = positive, 1 = negative)

2. Exponent – Tells how far to move the binary point (like the power of 10 in scientific
notation)
3. Mantissa (Significand) – The actual significant digits of the number

Simple 8-Bit Floating-Point Example

Let’s use a toy 8-bit floating-point format:

• 1 bit → Sign
• 3 bits → Exponent
• 4 bits → Mantissa

Structure: S EEE MMMM

Page 39 of 59
Example: Representing 2.75 (which is 10.11 in binary)

Step-by-step:

1. Convert 2.75 to binary → 10.11

2. Normalize it (move the binary point so only one ‘1’ is before the point):
o 10.11 = 1.011 × 2¹
3. Store:
o Sign bit = 0 (positive)
o Exponent = 1 (but stored with bias — we’ll explain bias later)
o Mantissa = 011 (the part after the 1.)

This is called Normalized Form — the mantissa always starts with 1. (this saves space).

Important Concepts

Normalized Form

• The mantissa always starts with 1. (the leading 1 is implied, not stored).
• This gives maximum precision.

Truncation / Rounding Error

• Because we have limited bits (e.g., only 4 bits for mantissa), we cannot store every
possible number exactly.
• Example: 0.1 in decimal cannot be represented exactly in binary → it becomes an
approximation.
• This causes rounding errors or truncation errors.

Real-world impact:

• Small errors in money calculations, navigation systems, or scientific simulations can

become big problems if not handled carefully.

5. Real Formats Used in Computers

Format Total Sign Exponent Mantissa Precision Use Case

Bits
Single 32 1 8 23 ~7 decimal Most games,
Precision digits graphics, apps
Double 64 1 11 52 ~15 decimal Scientific
Precision digits computing, finance

Single Precision (32-bit) is the most common for everyday use.

Page 40 of 59
Summary – How Floating-Point Works

1. Convert the number to binary.

2. Normalize it → Write as [Link] × 2^exponent.
3. Store:
o Sign bit
o Exponent (with a bias added so negative exponents can be stored)
o Mantissa (without the leading 1)

Key Advantage: Can represent very large numbers (e.g., 3.4 × 10³⁸) and very small numbers
(e.g., 1.4 × 10⁻⁴⁵) using limited bits.

Key Disadvantage: Not all decimal fractions can be represented exactly → leads to rounding
errors.

Introduction to Data and Programming (Python)

Why Programming Languages Exist

Computers only understand binary (machine code) at the lowest level. Humans think in high-
level concepts and logic.

Programming languages act as a bridge between human reasoning and machine execution.
They allow us to express algorithms at a higher level of abstraction while the computer (or
interpreter/compiler) handles the low-level details.

In the 21st century, programming skills are becoming foundational literacy alongside reading,
writing, and arithmetic. Many careers now require at least basic coding ability.

Introduction to Python

Python is a popular, modern programming language created by Guido van Rossum in the late
1980s.

Key Features (as highlighted in the book):

• Interpreted Language: Code is executed line-by-line rather than compiled all at once.
This makes development faster and easier for beginners.

Page 41 of 59
 • Highly Readable: Emphasizes clean, English-like syntax.
• Multi-Paradigm: Supports imperative, object-oriented, and functional programming
styles.
• Dynamically Typed: You don’t need to declare variable types in advance. The
interpreter figures it out at runtime.
• Widely used in: Web development, data science, scientific computing, automation, AI,
and education.
• Organizations using Python: Google, NASA, Dropbox, Industrial Light & Magic, etc.

Python 3 is the current standard (the book uses Python 3).

Getting Started: Hello, World!

The traditional first program:

Python

print('Hello, World!')

Output:

text

Hello, World!

Important Observations:

• print() is a built-in function used to display output.

• Text inside single (' ') or double (" ") quotes is called a string.
• Parentheses () are required in Python 3.

Variables and Assignment

Variables are named storage locations for data.

Python

Page 42 of 59
message = 'Hello, World!'
print(message)

Key Points:

• The = sign is an assignment operator (not mathematical equality). Read it as “message

is assigned the value 'Hello, World!'”.
• Python is dynamically typed — no need to specify the type beforehand.
• Variable names must:
o Start with a letter or underscore (_).
o Contain letters, numbers, and underscores only.
o Be case-sensitive (size ≠ Size ≠ SIZE).
• Use meaningful, descriptive names (e.g., total_pay instead of x).

Common Data Types:

• int → integers (e.g., 5)

• float → floating-point numbers (e.g., 26.2)
• bool → True or False
• str → strings (text)

Example:

Python

my_integer = 5
my_floating_point = 26.2
my_boolean = True
my_string = 'characters'

Working with Different Representations

• Hexadecimal: Prefix with 0x

Python

Page 43 of 59
 print(0xFF) # Outputs 255

• Unicode Characters:

Python

print('₹1000') # Direct Unicode

print('\u00A31000') # £1000 using Unicode escape

Comments (ignored by Python):

• Use # for single-line comments

Python

# This is a comment explaining the code

Operators and Expressions

Arithmetic Operators
Operator Meaning Example Result
+ Addition 3+4 7
- Subtraction 5-6 -1
* Multiplication 7*8 56
/ Division (float) 45 / 4 11.25
** Exponentiation 2 ** 10 1024
// Floor Division 45 // 4 11
% Modulo (remainder) 45 % 4 1

String Operators:

• + → Concatenation

Python

s = 'hello' + 'world' # 'helloworld'

Page 44 of 59
 • * → Repetition

Python

t=s*4 # 'helloworldhelloworldhelloworldhelloworld'

Type Conversion Functions

Function Purpose Example

str() Convert to string str(1000) → '1000'
int() Convert to integer int("42") → 42
float() Convert to floating-point float("3.14")

Example (Fixing type error):

Python

print('USD$' + str(1000)) # Correct: "USD$1000"

Practical Example: Currency Converter

The book provides a complete script demonstrating variables, operators, Unicode, and
comments:

Python

USD_to_GBP = 0.76
dollars = 1000
pounds = dollars * USD_to_GBP

print('Today, $' + str(dollars))

print('converts to £' + str(pounds))

This example ties together most concepts introduced in the section.

Debugging and Testing

Page 45 of 59
Debugging = Finding and fixing errors (bugs) in code.

Three Main Types of Errors:

1. Syntax Errors (Most common for beginners)

o Mistakes in the structure of the code.
o Examples:

Python

print(5 + ) # SyntaxError: invalid syntax

print(5.e) # SyntaxError: invalid token
pront(5) # NameError: name 'pront' is not defined

2. Semantic (Logic) Errors

o Code runs but produces wrong results.
o Example: Wrong order of operations

Python

total_pay = 40 + extra_hours * pay_rate # Wrong (should use parentheses)

3. Runtime Errors
o Errors that occur while the program is running.
o Examples: Division by zero, using undefined variable.

Best Practices for Testing & Debugging:

• Understand what the program is supposed to do.

• Run the script frequently (after every few lines).
• Use comments to explain complex logic.
• Test edge cases.

Summary Table: Core Python Concepts

Page 46 of 59
 Concept Description Example
Interpreted Executed line-by-line Immediate feedback
Variables Named memory locations message = 'Hello'
Dynamic Typing Type determined at runtime No type declaration needed
Operators Arithmetic, string, etc. +, *, //, %
Type Conversion Changing data types str(), int()
Debugging Fixing syntax, semantic, runtime errors Test early and often

Key Takeaways for College Students:

• Python is beginner-friendly due to its readability and interpreted nature.

• Mastering variables, operators, and basic debugging forms the foundation for all future
programming.
• Always write code that is clear and well-commented — it helps both you and others
understand the logic.
• Programming is about problem-solving, not just syntax.

Page 47 of 59
Data Compression
Data compression is the process of reducing the number of bits required to store or transmit
data while trying to retain as much of the original information as possible.

Why compress?

• Saves storage space (e.g., on hard drives, memory cards).

• Reduces transmission time and bandwidth usage (important for internet, streaming,
video calls).
• Sometimes mandatory (e.g., limited storage on devices or slow network connections).

Compression is not always perfect — there is a trade-off between size reduction, speed, and
quality.

Lossless vs Lossy Compression

Feature Lossless Compression Lossy Compression

Reconstruction Perfect — original data can be Approximate — some information
recovered exactly is permanently lost
Quality No loss of information Acceptable degradation in quality
Use Cases Text, source code, executables, Images, audio, video
documents, spreadsheets
Compression Generally lower (e.g., 2:1 to 5:1) Much higher (e.g., 10:1 to 100:1 or
Ratio more)

Lossless is used when any change is unacceptable (e.g., a single wrong bit in a program can
crash it). Lossy is used for media where small imperfections are not noticeable to humans.

Generic Data Compression Techniques

1. Run-Length Encoding (RLE) — Lossless

Idea: Replace long sequences (runs) of the same data value with a single value and a count of
how many times it repeats.

Page 48 of 59
Example: Original bit pattern: 1111111000000011111111 (long runs of 1s and 0s)

Compressed form: (7 ones)(7 zeros)(2 ones)(7 ones) → encoded as numbers and flags.

Real-world use:

• Fax machines (black & white text documents have long runs of white pixels).
• Simple image formats.

Advantage: Very fast and simple. Limitation: Works poorly on data without long runs (can
even make it larger).

2. Frequency-Dependent Encoding (Huffman Coding) — Lossless

Idea: Assign shorter bit codes to frequently occurring symbols and longer codes to rare
symbols.

Example (English text):

• ‘e’ is very common → might get code 01 (2 bits)

• ‘z’ is rare → might get code 110101 (6 bits)

Huffman Algorithm:

• Build a frequency table.

• Create a binary tree (Huffman tree) where frequent symbols have shorter paths from
root.
• Assign 0s and 1s along the tree branches.

This is a variable-length code. Most frequency-based codes used today are Huffman codes.

Advantage: Excellent compression for text and data with uneven symbol distribution.
Limitation: Requires the frequency table (or tree) to be stored or reconstructed during
decompression.

Page 49 of 59
3. Relative / Differential Encoding — Can be Lossless or Lossy

Idea: Instead of storing each complete data unit, store only the difference between the current
unit and the previous one.

Example (Video frames):

• Frame 1: Full image stored.

• Frame 2: Only record “pixel at position X changed from blue to red”.

Use: Consecutive video frames or audio samples that change gradually.

Lossless version: Store exact differences. Lossy version: Approximate small differences (or
ignore them).

4. Dictionary Encoding & LZW (Lempel-Ziv-Welsh) — Lossless (Adaptive)

Idea: Build a dictionary (lookup table) of frequently occurring patterns/strings. Replace

repeated patterns with short references (indices) to the dictionary.

How LZW works (Adaptive/Dynamic):

• Starts with a small dictionary (e.g., single characters + space).

• As it encodes, it adds newly discovered strings to the dictionary.
• Both encoder and decoder build the same dictionary dynamically — no need to transmit
the full dictionary.

Detailed Example from the textbook (message: xyx xyx xyx xyx):

Initial Dictionary: 1 → x 2 → y 3 → (space)

Encoding Process:

• xyx → codes 1 2 1 → output 121, then add “xyx” as entry 4.

• Continues → final encoded: 121343434

Page 50 of 59
Decoding: Decoder starts with same initial dictionary and adds entries exactly as the encoder
did when it sees new patterns.

Advantages:

• Very effective for text, GIF images, etc.

• Dictionary grows to match the specific file.

Image Compression Techniques

GIF (Graphic Interchange Format)

• Dictionary-based (uses LZW).

• Limits colors to 256 (8-bit palette).
• Each pixel stores an index (1 byte) into the color palette instead of full RGB (3 bytes).
• Supports transparency (one color can be marked transparent).
• Good for: Logos, cartoons, simple animations, line drawings.

Limitation: Poor for photographs (only 256 colors causes color banding).

JPEG (Joint Photographic Experts Group)

Most popular lossy image compression standard.

How JPEG Baseline (Lossy) Works:

1. Color Space Conversion: Convert to luminance (brightness) + chrominance (color).

Human eye is more sensitive to brightness.
2. Chroma Subsampling: Average color information over 2×2 pixel blocks → reduces
color data by 75% with little visible loss.
3. Block Splitting: Divide image into 8×8 pixel blocks.
4. Discrete Cosine Transform (DCT): Mathematical transformation that converts pixel
values into frequency components (how much patterns change).
5. Quantization: Round small frequency values to zero (removes subtle details human eye
can’t easily see).

Page 51 of 59
 6. Run-Length + Huffman Encoding: Compress the resulting sparse data.

Result: Typical compression 10x to 30x with very good visual quality for photos.

Trade-off: Higher compression = more visible artifacts (blockiness, ringing).

TIFF (Tagged Image File Format)

• Flexible container format.

• Often stores images uncompressed (highest quality, large files).
• Can use RLE or other compression.
• Popular in professional photography because it can store metadata (camera settings,
date, etc.).

Audio and Video Compression

MPEG (Motion Picture Experts Group) Standards

• Used for video (MP4, etc.).

• Key Technique:
o I-frames (Intra-frames): Fully compressed like JPEG.
o P-frames and B-frames: Store only differences from previous or future frames
(differential encoding).

This dramatically reduces data because consecutive video frames are usually very similar.

MP3 (MPEG Layer 3) — Audio Compression

Perceptual Coding — exploits limitations of human hearing:

• Temporal Masking: After a loud sound, the ear cannot hear softer sounds for a short
time.
• Frequency Masking: A loud sound at one frequency masks quieter sounds at nearby
frequencies.

Process:

Page 52 of 59
 • Removes sounds the human ear is unlikely to perceive.
• Uses psychoacoustic model.
• Achieves near-CD quality at ~10% of original size (e.g., 64–128 Kbps vs 1411 Kbps for
CD audio).

Trade-offs and Important Considerations

• Compression Ratio vs Quality: More compression usually means more quality loss (in
lossy methods).
• Encoding Time vs Decoding Time: Some methods are slow to compress but fast to
decompress (good for distribution).
• Artifacts: JPEG → blockiness; MP3 → metallic sound or loss of clarity at high
frequencies.
• Numeric Data: Never use lossy compression for financial, scientific, or critical data —
use lossless or store as integers.
• Real-world Impact: Modern streaming (Netflix, YouTube) relies heavily on advanced
MPEG variants (H.264, H.265/HEVC).

Essential Knowledge Statements (from text):

• There are trade-offs in using lossy and lossless compression techniques.

• Lossless compression allows complete reconstruction.
• Lossy compression significantly reduces size at the cost of approximation.

Page 53 of 59
Communication Errors
When data is stored, transmitted, or processed in a computer, there is always a risk that the bit
patterns can be altered.

Common Causes of Errors:

• Noise/Static on transmission lines.

• Particles of dirt or grease on magnetic disks/tapes.
• Background radiation (cosmic rays) flipping bits in main memory.
• Manufacturing defects or aging hardware.
• Electrical interference or power fluctuations.

Even a single flipped bit can cause serious problems — e.g., changing a bank balance,
corrupting a program, or distorting an image.

To solve this, computer systems use special encoding techniques for error detection and
error correction.

1. Parity Bits (Error Detection)

Basic Idea: Add one extra bit (called a parity bit) to each group of data bits so that the total
number of 1s follows a specific rule.

Two Types of Parity

Type Rule Error Detected When
Odd Parity Total number of 1s (including parity bit) must be Even number of 1s
odd found
Even Total number of 1s must be even Odd number of 1s found
Parity

How to Add Parity Bit:

• Count the number of 1s in the original data.

• Set the parity bit to 0 or 1 to satisfy the chosen parity rule.

Page 54 of 59
Example (from textbook – ASCII character 'A'):

• Original ASCII: 01000001 (2 ones → even)

• For Odd Parity: Add parity bit = 1 → 1 01000001 = 101000001 (3 ones → odd)

Another Example (ASCII 'F' = 01000110 — 3 ones, already odd):

• For Odd Parity: Add parity bit = 0 → 0 01000110 = 001000110 (still 3 ones, odd)

Strengths and Limitations of Parity Bits

Strengths:

• Very simple and cheap to implement.

• Used widely in memory (each byte actually uses 9 bits internally).

Limitations:

• Can only detect odd number of errors (1, 3, 5…).

• Cannot detect even number of errors (2, 4, 6…).
• Cannot correct the error — it only tells you “something is wrong.”

Real-world Use:

• Older memory systems.

• Simple communication protocols.

Improved Detection: Checkbytes, Checksums, and CRC

To overcome the weakness of simple parity, systems use multiple parity bits:

• Checkbyte / Parity Bits across Positions:

o One parity bit for bits in position 1, 9, 17…
o Another for bits in position 2, 10, 18…
o And so on.

Page 55 of 59
This way, errors in different parts of the data are more likely to be caught.

Cyclic Redundancy Check (CRC):

• A powerful, widely used error-detection method.

• Treats the data as a large binary number and divides it by a special polynomial.
• The remainder becomes the CRC bits attached to the data.
• Very good at detecting burst errors (multiple consecutive flipped bits).
• Used in Ethernet, Wi-Fi, ZIP files, etc.

2. Error-Correcting Codes (ECC)

These codes can detect and correct errors automatically.

Hamming Distance

Definition: The Hamming distance between two bit patterns is the number of positions at
which the bits differ.

Example:

• 000000 and 000001 → Hamming distance = 1

• 000000 and 111111 → Hamming distance = 6

Key Principle for Error Correction: If the minimum Hamming distance between any two
valid codewords is d, then the code can:

• Detect up to (d–1) errors.

• Correct up to floor((d–1)/2) errors.

For single error correction: Minimum distance must be at least 3.

Example Error-Correcting Code (from the Textbook)

The textbook presents an 6-bit code for 8 characters (A–H):

Page 56 of 59
 Character Code
A 000000
B 001111
C 010011
D 011100
E 100101
F 101010
G 110110
H 111001

Important Property: Any two codewords differ in at least 3 bits (minimum Hamming
distance = 3).

How Error Correction Works

Decoding Rule:

1. Receive a (possibly corrupted) bit pattern.

2. Compare it with all valid codewords.
3. Choose the codeword that has the smallest Hamming distance to the received pattern.
4. That codeword is assumed to be the original.

Example (from textbook):

• Received pattern: 010100

• Compare distances → closest valid codeword is D (011100) with distance 1.
• Conclusion: Original was D, and one bit was flipped.

This method can:

• Correct 1 error per codeword.

• Detect up to 2 errors (but may not correct them).

Page 57 of 59
Applications of Error-Correcting Codes

Application Technique Used Reason

Main Memory ECC (Extended Hamming or Corrects single-bit errors
(RAM) similar) automatically
Hard Disk Drives Strong ECC Protects against surface defects
CDs/DVDs Reed-Solomon + others Audio CDs tolerate more errors
than data CDs
Network CRC + retransmission Detect + request resend
Transmission
Satellite Very strong ECC High radiation environment
Communication

CD Example:

• Audio CDs: Enough error correction for 1 error in ~2 CDs.

• Data CDs: Much stronger error correction (1 error in 20,000 disks) because even one
wrong bit in a program is unacceptable.

Summary Table: Detection vs Correction

Method Detects Errors Corrects Errors Overhead Typical Use

Simple Parity Odd errors only No 1 bit Basic memory
Checksum / CRC Very good No Several bits Networks, files
Hamming ECC Up to 2 1 error More bits RAM, storage
Advanced ECC Multiple Multiple Higher Critical systems

Key Takeaways for Students

• Errors are inevitable in real hardware.

• Parity bits = simple detection (cheap but limited).

Page 58 of 59
 • Hamming codes = detection + correction using redundancy.
• The more redundancy (extra bits) you add, the more errors you can correct — but this
reduces storage/transmission efficiency.
• Modern systems combine multiple techniques (detection + correction + retransmission
when needed).

These mechanisms are why your computer memory and storage are far more reliable than they
would otherwise be.

Page 59 of 59