✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS (DISCRETE MATHEMATICS)

 

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS

A. Relations

Definition

A relation R from A to B is a subset of A×B.

Representation

• List of ordered pairs

• Matrix representation

• Directed graph

Operations

• Union

• Intersection

• Composition (R ∘ S)

• Inverse relation (R⁻¹)

Types of Relations

1. Reflexive: (a,a) ∈ R for all a

2. Symmetric: (a,b) ⇒ (b,a)

3. Transitive: (a,b) & (b,c) ⇒ (a,c)

4. Anti-symmetric

---

Counting Relations

If A has n elements:

Total possible relations =

$$2^{n^2}$$

---

Closure of Relations

• Reflexive closure = R ∪ {(a,a)}

• Symmetric closure = R ∪ R⁻¹

• Transitive closure = Add pairs until transitivity satisfied (Warshall)

---

Equivalence Relation

When R is:

• Reflexive

• Symmetric

• Transitive

Then A is partitioned into equivalence classes.

---

Partial Order Relation

R is:

• Reflexive

• Anti-symmetric

• Transitive

Forms a poset.

---

Power of a Relation

Rⁿ = R composed with itself n times.

---

Functions

Definition

A function f: A → B assigns each element in A to exactly one element in B.

Terms

• Domain

• Co-domain

• Range

Types

• One-one (Injective)

• Onto (Surjective)

• Bijective

• Constant

• Identity function

---

Counting Functions

From set A (m elements) to B (n elements):

$$n^m \text{ functions}$$

---

Inverse Function

Exists only for bijective functions.

---

Composition

If f: A→B and g: B→C
Then g∘f: A→C.

---

Group Theory (Basics)

A set G with binary operation * is a group if:

1. Closure

2. Associativity

3. Identity element

4. Inverse exists for all elements

If operation is commutative → Abelian group.

✅ UNIT 2 — COMBINATORICS (DISCRETE MATHEMATICS)

 

✅ UNIT 2 — COMBINATORICS

1. Permutations & Combinations

Permutation

Arrangement of objects where order matters.

• Formula:

  $$^nP_r = \frac{n!}{(n-r)!}$$

Example:
Number of ways to arrange 3 letters from ABCD
= $^4P_3 = 24$

Combination

Selection of objects where order does NOT matter.

• Formula:

  $$^nC_r = \frac{n!}{r!(n-r)!}$$

Example:
Choose 2 students from 5
= $^5C_2 = 10$

---

2. Summation

Properties of Σ:

• Linearity:
  $\sum (a_i + b_i) = \sum a_i + \sum b_i$

• Constant factor:
  $\sum c\cdot a_i = c\sum a_i$

---

3. Binomial Function

Binomial Theorem:

$$(a + b)^n = \sum_{k=0}^{n} {^nC_k a^{n-k} b^k}$$

Properties:

• Number of terms = n+1

• Middle term depends on n (odd/even)

• Coefficients symmetric:

  $$^nC_k = ^nC_{n-k}$$

---

4. Generating Functions

Used in recurrence and combinatorics.

Basic idea:

If we have sequence {a₀, a₁, a₂, …}
Generating function is:

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$$

Example: For sequence 1,1,1,1,…

$$G(x) = \frac{1}{1 - x}$$

---

5. Recurrence Relation

Example: Fibonacci

$$f(n) = f(n-1) + f(n-2)$$

Solving Linear Recurrences

General form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2}$$

Steps:

1. Form characteristic equation

   $$r^2 - c_1 r - c_2 = 0$$

2. Find roots r₁, r₂

3. General solution:

   $$a_n = A r_1^n + B r_2^n$$

✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping) NUMERICALS

 

✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping)

Q1.

A computer has:

• Main memory = 4K words

• Cache = 128 words

• Block size = 4 words

Find:

1. No. of blocks in main memory

2. No. of lines in cache

3. Mapping of memory block 205 to cache line.

---

Solution

1) Blocks in main memory

Main memory size = 4K = 4096 words
Block size = 4 words

$$\text{No. of blocks} = \frac{4096}{4} = 1024$$

---

2) Cache lines

Cache size = 128 words
Block size = 4 words

$$\text{Cache lines} = \frac{128}{4} = 32$$

---

3) Mapping of block 205

Direct mapping:

$$\text{Cache line} = \text{Block number} \mod \text{No. of lines}$$ $$205 \mod 32 = 13$$

✔ Answer:

Block 205 maps to cache line 13.

---

✅ 2. SET-ASSOCIATIVE CACHE NUMERICAL

Q2.

8 KB cache, block size = 64 bytes, 4-way set associative.
Find number of sets.

---

Solution

Cache size = 8 KB = 8192 bytes
Block size = 64 bytes

1 set has 4 blocks (because 4-way).

Total blocks =

$$\frac{8192}{64} = 128$$

No. of sets =

$$\frac{128}{4} = 32$$

✔ Answer:

32 sets

---

✅ 3. MEMORY INTERLEAVING

Q3.

A system has 4 memory banks using lower-order interleaving.
Words are stored starting from address 0.
Find the bank number for address: 37.

---

Solution

Lower-order interleaving:

$$\text{Bank} = \text{Address} \mod \text{No. of banks}$$

Here:
37 mod 4 = 1

✔ Answer:

Address 37 is in Bank 1.

---

✅ 4. EFFECTIVE ACCESS TIME (EAT)

Q4.

Hit ratio = 90%
Cache access time = 10 ns
Main memory access = 100 ns

Find EAT.

---

Solution

$$EAT = (Hit\ Ratio \times Cache\ Time) + (Miss\ Ratio \times Memory\ Time)$$

Hit ratio = 0.9
Miss ratio = 1 – 0.9 = 0.1

$$EAT = (0.9 \times 10) + (0.1 \times 100)$$ $$= 9 + 10 = 19\ \text{ns}$$

✔ Answer:

19 ns

---

✅ 5. PIPELINE THROUGHPUT

Q5.

A pipeline has 5 stages, each taking 20 ns.
Calculate time to execute 10 instructions.

---

Solution

Pipeline time =

$$kT + (n - 1)T$$

k = stages = 5
T = 20 ns
n = instructions = 10

$$= 5(20) + 9(20)$$ $$= 100 + 180 = 280\ \text{ns}$$

✔ Answer:

280 ns

---

✅ 6. BINARY → EXCESS-3 NUMERICAL

Q6.

Convert 75 (decimal) into Excess-3 code.

---

Solution

Digits: 7 and 5

Step 1 → Convert to BCD:
7 → 0111
5 → 0101

Step 2 → Add 3 (0011) to each:

0111 + 0011 = 1010
0101 + 0011 = 1000

✔ Answer:

75 = 1010 1000 (Excess-3)

---

✅ 7. BINARY MULTIPLICATION (Booth’s Algorithm)

Q7.

Multiply: (+7) × (−3) using Booth’s algorithm.
(Short exam-style solution.)

---

Solution Summary

7 = 0111
−3 = 1101 (2’s complement)

Perform Booth steps → final answer:

✔ Answer:

(+7) × (−3) = −21
Binary result: 1010 1011

---

✅ 8. ADDRESSING MODE NUMERICAL

Q8.

Effective address = ?
Instruction: MOV A, M
HL register pair = 2050H

---

Solution

Indirect addressing:
Address = content of HL.

✔ Answer:

EA = 2050H

---

✅ 9. MEMORY SIZE CALCULATION

Q9.

How many bytes in a memory with 16-bit address bus?

---

Solution

No. of addressable locations =

$$2^{16} = 65536$$

Each location stores 1 byte.

✔ Answer:

64 KB

---

✅ 10. CACHE TAG CALCULATION

Q10.

Find tag, set, and block offset for:

• Cache = 4 KB

• Block size = 32 bytes

• 2-way associative

• 16-bit address

---

Solution Steps

1. Cache size = 4096 bytes
   Block size = 32 →
   Blocks = 4096 / 32 = 128 blocks

2. 2-way set associative →
   Sets = 128 / 2 = 64 sets

3. Set bits = log₂(64) = 6 bits

4. Offset bits = log₂(32) = 5 bits

5. Tag bits = 16 – (6 + 5) = 5 bits

---

✔ Final Answer:

• Tag = 5 bits

• Set = 6 bits

• Offset = 5 bits

✅ UNIT 5 — MEMORY & I/O ORGANIZATION

 

This unit explains how data is stored, accessed, and transferred inside a computer — essential for understanding how modern CPUs achieve high speed.

---

⭐ 5.1 Memory Hierarchy

Memory is organized in layers based on speed, cost, and capacity.

From Fastest → Slowest

1. Registers

2. Cache Memory

3. Main Memory (RAM)

4. Secondary Memory (HDD/SSD)

5. Tertiary (CD/DVD)

Key Idea:

• Higher levels → faster, expensive, smaller

• Lower levels → slower, cheap, larger

CPU always tries to read from the fastest possible level.

---

⭐ 5.2 Cache Memory

Cache = small, very fast memory between CPU & RAM.

Why cache is needed?

Because CPU is extremely fast but RAM is slower → cache avoids waiting.

---

Types of Cache

1. L1 Cache

Fastest, smallest, inside CPU core.

2. L2 Cache

Bigger, slower.

3. L3 Cache

Shared between multiple cores.

---

Cache Mapping Techniques

1️⃣ Direct Mapping

Each block of main memory maps to exactly one cache line.

Advantages: Simple
Disadvantages: Conflict misses

2️⃣ Associative Mapping

Any memory block → any cache line.

Advantages: Flexible
Disadvantages: Expensive hardware

3️⃣ Set-Associative Mapping

Memory block → a small set of cache lines.
Most commonly used.

---

⭐ 5.3 Main Memory (RAM + ROM)

RAM Types

• SRAM → used in cache

• DRAM → used in main memory

ROM Types

• PROM

• EPROM

• EEPROM

---

⭐ 5.4 Memory Interleaving

Memory speed can be increased by storing data across multiple banks.

Types:

1️⃣ Lower-Order Interleaving

Low-order bits choose memory bank.

2️⃣ Higher-Order Interleaving

High-order bits choose memory bank.

Goal: Increase reading speed by accessing multiple banks simultaneously.

---

⭐ 5.5 Associative Memory (Content Addressable Memory)

Data is accessed by content, not by address.

Used in:

• Cache tag matching

• TLB (Translation Lookaside Buffer)

---

⭐ 5.6 I/O Organization

Two main categories:

1️⃣ Programmed I/O

CPU controls I/O directly.
Simple but slow.

2️⃣ Interrupt-Driven I/O

I/O device interrupts CPU when ready.
Faster than programmed I/O.

3️⃣ Direct Memory Access (DMA)

Fastest I/O method.

DMA Features:

• Transfers data directly between memory & I/O

• CPU is freed during transfer

• Very efficient for large data (disk, graphics)

---

⭐ 5.7 Memory-Mapped vs I/O-Mapped I/O

Feature	Memory-Mapped I/O	I/O-Mapped I/O
Address Space	Uses normal memory addresses	Separate I/O address space
Instructions	Normal memory instructions	Special I/O instructions (IN, OUT)
Speed	Faster	Moderate
Example	Modern CPUs	8085 (IN/OUT)

---

⭐ 5.8 Secondary Storage Concepts

HDD

• Mechanical

• Slower

• Large capacity

SSD

• No moving parts

• Much faster

• Expensive

CD/DVD

• Optical storage

• Used for distribution & backup