📘 PAPER 5 – OPERATING SYSTEM (UNIT 3 – FILE SYSTEM & I/O MANAGEMENT) university of allahabad

 

🔴 UNIT 3 – FILE SYSTEM & I/O MANAGEMENT

---

1️⃣ File System – Introduction

✅ What is a File?

A file is a collection of related information stored on secondary storage.

✅ File System

The file system is a method used by the OS to:

• Store files

• Retrieve files

• Organize data efficiently

---

2️⃣ File Attributes

Each file has the following attributes:

Attribute	Description
Name	File name
Type	File extension
Size	File size
Location	Disk location
Protection	Access rights
Time & Date	Creation/modification time

---

3️⃣ File Operations

Common file operations:

✔ Create
✔ Open
✔ Read
✔ Write
✔ Close
✔ Delete

---

4️⃣ File Access Methods

---

🔹 1. Sequential Access

• Data accessed sequentially

• Example: Text file

✔ Simple
❌ Slow for random access

---

🔹 2. Direct Access

• Access any record directly

• Example: Database files

✔ Fast
✔ Efficient

---

🔹 3. Indexed Access

• Uses index to locate data

• Combination of sequential & direct

---

5️⃣ Directory Structure

Types of Directory Structures:

---

🔹 1. Single Level Directory

• All files in one directory
  ❌ Name conflict

---

🔹 2. Two-Level Directory

• Separate directories for each user

---

🔹 3. Tree Structure Directory

• Hierarchical structure

• Most commonly used

---

🔹 4. Acyclic Graph Directory

• Shared files

• No cycles

---

6️⃣ File Allocation Methods

---

🔹 1. Contiguous Allocation

• Files stored in continuous memory

✔ Fast access
❌ External fragmentation

---

🔹 2. Linked Allocation

• File blocks linked using pointers

✔ No fragmentation
❌ Slow access

---

🔹 3. Indexed Allocation

• Index block stores pointers

✔ Fast access
✔ No fragmentation

---

7️⃣ Free Space Management

Methods used to manage free disk space:

✔ Bit vector
✔ Linked list
✔ Grouping
✔ Counting

---

8️⃣ Disk Scheduling

Purpose:

Reduce disk access time

---

🔹 Disk Scheduling Algorithms

---

1️⃣ FCFS (First Come First Serve)

✔ Simple
❌ High seek time

---

2️⃣ SSTF (Shortest Seek Time First)

✔ Better than FCFS
❌ Starvation possible

---

3️⃣ SCAN (Elevator Algorithm)

✔ Moves in one direction
✔ Reduces starvation

---

4️⃣ C-SCAN

✔ Uniform wait time
✔ Used in modern OS

---

9️⃣ I/O Management

I/O System Responsibilities:

✔ Device communication
✔ Error handling
✔ Buffering
✔ Spooling

---

🔹 I/O Techniques

1. Programmed I/O

CPU controls I/O
❌ Slow

---

2. Interrupt Driven I/O

CPU works during I/O
✔ Better performance

---

3. Direct Memory Access (DMA)

• Data transferred directly to memory

• CPU not involved

✔ Fastest
✔ Efficient

---

🔟 Protection & Security

---

🔹 Protection

Ensures controlled access to resources.

🔹 Security

Prevents unauthorized access.

---

Protection Mechanisms:

✔ Passwords
✔ Access control lists
✔ Encryption

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 3)

✔ Explain file allocation methods
✔ Disk scheduling algorithms
✔ Explain DMA
✔ File access methods
✔ Directory structure
✔ Difference between FCFS and SSTF

📘 PAPER 5 – OPERATING SYSTEM ( UNIT 2 – MEMORY MANAGEMENT) university of allahabad

 

🔴 UNIT 2 – MEMORY MANAGEMENT

---

1️⃣ Memory Management – Introduction

✅ Definition

Memory management is the function of the OS that:

• Allocates memory to processes

• Deallocates memory after use

• Manages primary and secondary memory efficiently

---

2️⃣ Memory Management Requirements

✔ Relocation
✔ Protection
✔ Sharing
✔ Logical organization
✔ Physical organization

---

3️⃣ Memory Management Techniques

---

🔹 1. Multiprogramming with Fixed Partitions

Concept:

• Memory is divided into fixed-size partitions

• One process per partition

Advantages:

✔ Simple
✔ Easy implementation

Disadvantages:

❌ Internal fragmentation
❌ Wastage of memory

---

🔹 2. Multiprogramming with Variable Partitions

Concept:

• Memory allocated as per process size

• No fixed partitions

Advantages:

✔ Less internal fragmentation

Disadvantages:

❌ External fragmentation

---

4️⃣ Memory Allocation Strategies

---

🔹 First Fit

Allocates first available memory block

✔ Fast
❌ Fragmentation

---

🔹 Best Fit

Allocates smallest possible block

✔ Less wastage
❌ Slow

---

🔹 Worst Fit

Allocates largest block

❌ Poor utilization

---

5️⃣ Swapping

Definition:

Process is temporarily moved from main memory to disk.

Purpose:

✔ Free memory
✔ Improve multiprogramming

---

6️⃣ Virtual Memory

Definition:

Virtual memory allows execution of processes even if:

• Entire program is not in memory

Uses:
✔ Secondary memory
✔ Demand paging

---

7️⃣ Paging

Concept:

• Memory divided into pages

• Physical memory divided into frames

Address Format:

Page number | Offset

---

Advantages:

✔ No external fragmentation
✔ Easy memory management

---

Disadvantages:

❌ Internal fragmentation

---

8️⃣ Segmentation

Concept:

Memory divided based on logical units:

• Code

• Data

• Stack

Address Format:

Segment number | Offset

---

Advantages:

✔ Logical view
✔ Better protection

Disadvantages:

❌ External fragmentation

---

9️⃣ Paging vs Segmentation

Paging	Segmentation
Fixed size	Variable size
No external fragmentation	External fragmentation
Hardware based	Logical view
Fast	Flexible

---

🔟 Virtual Memory Techniques

---

🔹 Demand Paging

Pages loaded only when needed.

---

🔹 Page Fault

Occurs when required page is not in memory.

---

🔹 Page Replacement Algorithms

1. FIFO

Oldest page removed

2. LRU

Least recently used page removed

3. Optimal

Replaces page not used for longest time (best but impractical)

---

1️⃣1️⃣ Thrashing

Definition:

System spends more time paging than executing.

---

Causes:

• High degree of multiprogramming

• Insufficient memory

---

Prevention:

✔ Reduce multiprogramming
✔ Increase RAM
✔ Use good page replacement

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 2)

✔ Explain paging and segmentation
✔ Difference between paging & segmentation
✔ Explain virtual memory
✔ Explain page replacement algorithms
✔ What is thrashing?
✔ Explain memory allocation strategies

📘 PAPER 5 – OPERATING SYSTEM (UNIT 1 – INTRODUCTION & PROCESS MANAGEMENT) university of allahabad

 

📘 PAPER 5 – OPERATING SYSTEM

🔴 UNIT 1 – INTRODUCTION & PROCESS MANAGEMENT

---

1️⃣ Introduction to Operating System

✅ What is an Operating System (OS)?

An Operating System is system software that:

• Acts as an interface between user and hardware

• Manages computer resources

• Controls execution of programs

---

✅ Functions of Operating System

✔ Process management
✔ Memory management
✔ File management
✔ Device management
✔ Security & protection
✔ User interface

---

✅ Examples of Operating Systems

• Windows

• Linux

• macOS

• Android

• UNIX

---

2️⃣ Types of Operating Systems

🔹 1. Batch Operating System

• Jobs executed in batches

• No user interaction

🔹 2. Multiprogramming OS

• Multiple programs in memory

• CPU utilization increases

🔹 3. Time Sharing OS

• Multiple users at same time

• CPU shared among users

🔹 4. Real-Time OS

• Immediate response

• Used in medical & industrial systems

---

3️⃣ Structure of Operating System

🔹 Layered Structure

• Hardware at bottom

• User interface at top

• Easy to debug and maintain

---

4️⃣ Process Concept

✅ Process

A process is a program in execution.

---

Components of a Process

• Program counter

• Registers

• Stack

• Data section

---

5️⃣ Process States

🔹 Five States of Process

State	Description
New	Process created
Ready	Waiting for CPU
Running	Executing
Waiting	Waiting for I/O
Terminated	Finished

---

6️⃣ Process Control Block (PCB)

Definition:

PCB stores all information about a process.

Contains:

• Process ID

• Process state

• CPU registers

• Memory info

• Scheduling info

---

7️⃣ Process Scheduling

Types of Scheduling:

1. Long-term scheduler

2. Short-term scheduler

3. Medium-term scheduler

---

8️⃣ CPU Scheduling Algorithms

---

🔹 1. FCFS (First Come First Serve)

✔ Simple
❌ High waiting time

---

🔹 2. SJF (Shortest Job First)

✔ Minimum waiting time
❌ Starvation problem

---

🔹 3. Priority Scheduling

• Process with highest priority executes first

---

🔹 4. Round Robin

• Time quantum based

• Fair scheduling

---

9️⃣ Process Synchronization

Problem:

When multiple processes access shared data → inconsistency occurs.

---

🔹 Critical Section Problem

Requirements:

✔ Mutual Exclusion
✔ Progress
✔ Bounded Waiting

---

🔟 Semaphores

Definition:

Semaphore is a synchronization tool.

Types:

1. Binary Semaphore

2. Counting Semaphore

---

Operations:

wait()
signal()

---

1️⃣1️⃣ Deadlock

Definition:

Deadlock occurs when:

• Each process waits for a resource held by others

---

Conditions of Deadlock:

1. Mutual Exclusion

2. Hold and Wait

3. No Preemption

4. Circular Wait

---

Deadlock Handling:

✔ Prevention
✔ Avoidance
✔ Detection
✔ Recovery

---

1️⃣2️⃣ Inter-Process Communication (IPC)

Methods:

• Pipes

• Message Queues

• Shared Memory

• Signals

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 1)

✔ Explain process states
✔ Explain CPU scheduling algorithms
✔ Explain semaphore
✔ What is deadlock? Explain conditions
✔ Explain PCB
✔ Difference between process and program

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS ( UNIT 5 – RANDOMIZED ALGORITHMS & NP-COMPLETENESS) university of allahabad)

 

🔴 UNIT 5 – RANDOMIZED ALGORITHMS & NP-COMPLETENESS

---

🟦 PART A: RANDOMIZED ALGORITHMS

---

1️⃣ Randomized Algorithm

✅ Definition

A Randomized Algorithm uses random numbers to make decisions during execution.

👉 Output or running time may vary for the same input.

---

🔹 Types of Randomized Algorithms

1️⃣ Las Vegas Algorithm

✔ Always gives correct result
✔ Execution time varies

📌 Example: Randomized Quick Sort

---

2️⃣ Monte Carlo Algorithm

✔ Fast execution
❌ May give incorrect result (with small probability)

📌 Example: Primality testing

---

2️⃣ Randomized Quick Sort

Idea:

• Randomly select pivot

• Partition array

• Recursively sort

Time Complexity:

Case	Time
Best	O(n log n)
Average	O(n log n)
Worst	O(n²)

✔ Faster in practice than normal quicksort

---

3️⃣ Randomized Min-Cut Algorithm

Proposed by:

Karger’s Algorithm

Purpose:

Find minimum cut in an undirected graph.

---

Working:

1. Pick random edge

2. Contract vertices

3. Repeat until 2 vertices remain

4. Count crossing edges

---

Advantage:

✔ Simple
✔ Probabilistically correct

---

4️⃣ Randomized Algorithm for N-Queen

Idea:

• Place queens randomly

• If conflict → retry

• Continue until solution found

✔ Faster than backtracking for large N

---

🟦 PART B: APPROXIMATION ALGORITHMS

---

5️⃣ Approximation Algorithm

Definition:

Algorithm that gives near-optimal solution for NP-hard problems.

---

Approximation Ratio:

$$\frac{Solution\_Cost}{Optimal\_Cost}$$

---

6️⃣ Job Scheduling Problem

Objective:

Minimize completion time of jobs on machines.

Greedy Strategy:

• Sort jobs by processing time

• Assign shortest job first

---

7️⃣ Bin Packing Problem

Problem:

Pack objects into minimum number of bins.

Approximate Solution:

• First Fit

• Best Fit

---

8️⃣ Set Cover Problem

Goal:

Select minimum number of sets whose union covers all elements.

Solution:

✔ Greedy approximation

---

9️⃣ Max Cut Problem

Definition:

Divide graph into two sets such that:

• Maximum number of edges cross between them

✔ NP-Hard
✔ Approximation algorithms used

---

🟦 PART C: LOWER BOUND THEORY

---

🔟 Lower Bound

Definition:

Minimum number of operations required to solve a problem.

---

Types:

1. Comparison-based

2. Decision tree based

---

🔹 Decision Tree Method

Used to find:
✔ Lower bound of sorting
✔ Complexity analysis

---

Example:

Sorting requires at least:

$$Ω(n \log n)$$

---

🔹 Reduction Method

Definition:

If problem A can be reduced to problem B, and B is hard → A is also hard.

Used in:
✔ NP-completeness proofs

---

🟦 PART D: NP-COMPLETENESS

---

1️⃣ Class P

✔ Problems solvable in polynomial time
✔ Efficient algorithms exist

Example:

• Sorting

• Searching

---

2️⃣ Class NP

✔ Solution verifiable in polynomial time
✔ Not necessarily solvable fast

Example:

• Traveling Salesman

• Knapsack

---

3️⃣ NP-Hard

✔ At least as hard as NP problems
✔ May not be in NP

---

4️⃣ NP-Complete

✔ Belongs to NP
✔ Also NP-Hard

---

Famous NP-Complete Problems:

• Traveling Salesman Problem

• Knapsack

• SAT

• Graph Coloring

• Hamiltonian Cycle

---

5️⃣ P vs NP Problem

Question:

Is P = NP ?

Answer:

❌ Still unsolved (Millennium problem)

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 5)

✔ Explain randomized algorithms
✔ Explain NP-complete problems
✔ Difference between P, NP, NP-hard
✔ Explain approximation algorithms
✔ Explain min-cut algorithm
✔ Decision tree method

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 4 – DYNAMIC PROGRAMMING & BACKTRACKING) university of allahabad

 

🔴 UNIT 4 – DYNAMIC PROGRAMMING & BACKTRACKING

---

🟦 PART A: DYNAMIC PROGRAMMING

---

1️⃣ Dynamic Programming (DP)

✅ Definition

Dynamic Programming is a technique used to solve problems by:
✔ Breaking them into subproblems
✔ Solving each subproblem only once
✔ Storing results for future use

---

🔹 Properties of DP

1. Optimal Substructure

2. Overlapping Subproblems

---

2️⃣ 0/1 Knapsack Problem

Problem Statement:

Given:

• Weight array w[]

• Profit array p[]

• Capacity W

Goal:
Maximize profit without exceeding capacity.

---

DP Formula:

DP[i][w] = max(
    DP[i-1][w],
    DP[i-1][w - wi] + pi
)

---

Time Complexity:

O(nW)

---

Difference: Fractional vs 0/1 Knapsack

Feature	Fractional	0/1
Item division	Allowed	Not allowed
Approach	Greedy	Dynamic
Optimal	Yes	Yes

---

3️⃣ Matrix Chain Multiplication

Purpose:

Find the most efficient way to multiply matrices.

---

DP Formula:

M[i][j] = min{ M[i][k] + M[k+1][j] + pi-1 * pk * pj }

---

Time Complexity:

O(n³)

---

4️⃣ All-Pairs Shortest Path

---

🔹 Floyd–Warshall Algorithm

Used to find shortest paths between all pairs of vertices.

Formula:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][k])

Time Complexity:

O(n³)

---

5️⃣ Longest Common Subsequence (LCS)

Definition:

Find the longest sequence common to two strings.

---

Example:

X = ABCDGH
Y = AEDFHR
LCS = ADH

---

DP Formula:

if X[i] == Y[j]:
    L[i][j] = 1 + L[i-1][j-1]
else:
    L[i][j] = max(L[i-1][j], L[i][j-1])

---

6️⃣ Traveling Salesman Problem (TSP)

Problem:

Find the shortest path visiting each city exactly once and returning to start.

---

Solution:

✔ Dynamic Programming
❌ NP-Hard Problem

---

🟦 PART B: BACKTRACKING & BRANCH AND BOUND

---

7️⃣ Backtracking

Definition:

Backtracking tries all possibilities and removes those which fail.

---

Applications:

• N-Queen problem

• Graph coloring

• Subset sum

---

8️⃣ N-Queen Problem

Goal:

Place N queens on NxN chessboard so that:

• No two queens attack each other

---

Approach:

✔ Place queen row by row
✔ Backtrack when conflict occurs

---

9️⃣ Graph Coloring

Objective:

Color graph vertices such that:

• No adjacent vertices have same color

---

🔟 Sum of Subsets

Objective:

Find subsets whose sum equals target value.

---

1️⃣1️⃣ Branch and Bound

Definition:

Optimization technique that:

• Uses bounds

• Prunes unnecessary branches

---

Used In:

✔ Traveling Salesman
✔ Job Assignment
✔ Knapsack

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✔ Explain Dynamic Programming
✔ Solve 0/1 Knapsack
✔ Explain Floyd Warshall
✔ LCS with example
✔ N-Queen problem
✔ Branch and Bound

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 3 – DIVIDE & CONQUER AND GREEDY METHODS) university of allahabad

 

🔴 UNIT 3 – DIVIDE & CONQUER AND GREEDY METHODS

---

🔹 PART A: DIVIDE AND CONQUER

---

1️⃣ Divide and Conquer Technique

✅ Definition

Divide and Conquer is an algorithm design technique that:

1. Divides the problem into smaller subproblems

2. Conquers them recursively

3. Combines the solutions

---

General Form:

Divide → Conquer → Combine

---

Examples:

✔ Merge Sort
✔ Quick Sort
✔ Binary Search
✔ Matrix Multiplication

---

2️⃣ Matrix Multiplication

🔹 Normal Method

Time Complexity:

O(n³)

---

🔹 Strassen’s Matrix Multiplication

Reduces multiplication operations.

Time Complexity:

O(n^2.81)

Advantage:

✔ Faster than normal method
✔ Used in large matrix computation

---

3️⃣ Convex Hull

✅ Definition

Convex Hull is the smallest convex polygon that encloses all points.

---

Algorithms:

1. Graham’s Scan

2. Jarvis March

---

Applications:

• Image processing

• Pattern recognition

• GIS systems

---

🔹 PART B: GREEDY METHOD

---

4️⃣ Greedy Algorithm

✅ Definition

Greedy algorithm chooses the best option at each step hoping to get the global optimum.

---

Characteristics:

✔ Simple
✔ Fast
❌ May not give optimal solution always

---

5️⃣ Fractional Knapsack Problem

Problem:

Maximize profit with weight constraint.

Solution:

• Take full item if possible

• Take fraction if needed

Time Complexity:

O(n log n)

✔ Greedy works here
❌ Not applicable for 0/1 knapsack

---

6️⃣ Minimum Spanning Tree (MST)

Definition:

A spanning tree with minimum total edge weight.

---

🔹 1. Prim’s Algorithm

Steps:

1. Start with any vertex

2. Select minimum weight edge

3. Add to tree

4. Repeat

Time Complexity:

O(E log V)

---

🔹 2. Kruskal’s Algorithm

Steps:

1. Sort edges by weight

2. Add smallest edge

3. Avoid cycle

Uses:

✔ Union-Find
✔ Greedy technique

---

Difference: Prim vs Kruskal

Prim	Kruskal
Vertex-based	Edge-based
Uses priority queue	Uses sorting
Dense graphs	Sparse graphs

---

7️⃣ Single Source Shortest Path

---

🔹 Dijkstra’s Algorithm

Purpose:

Find shortest path from source to all vertices.

Condition:

✔ No negative edges

Time Complexity:

O(V²)

---

🔹 Bellman-Ford Algorithm

Advantage:

✔ Handles negative weights

Disadvantage:

❌ Slower than Dijkstra

Time Complexity:

O(VE)

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 3)

✔ Explain Divide and Conquer
✔ Explain Strassen’s matrix multiplication
✔ Explain Greedy method
✔ Difference between Prim and Kruskal
✔ Explain Dijkstra algorithm
✔ Explain Fractional Knapsack

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 2 – ADVANCED DATA STRUCTURES) university of allahabad

 

🔴 UNIT 2 – ADVANCED DATA STRUCTURES

---

1️⃣ AVL TREE (Adelson–Velsky and Landis Tree)

✅ Definition

An AVL Tree is a self-balancing Binary Search Tree (BST) where the height difference (balance factor) of left and right subtrees is at most 1.

---

✅ Balance Factor (BF)

$$BF = Height(left\ subtree) - Height(right\ subtree)$$

Allowed values:

• -1

• 0

• +1

---

✅ Rotations in AVL Tree

When balance factor becomes ±2, rotations are performed.

---

🔹 Types of Rotations

1. LL Rotation (Left-Left)

Occurs when:

• Insertion in left subtree of left child

✔ Single right rotation

---

2. RR Rotation (Right-Right)

Occurs when:

• Insertion in right subtree of right child

✔ Single left rotation

---

3. LR Rotation (Left-Right)

Occurs when:

• Left child has right-heavy subtree

✔ Left rotation + Right rotation

---

4. RL Rotation (Right-Left)

Occurs when:

• Right child has left-heavy subtree

✔ Right rotation + Left rotation

---

✅ Advantages

✔ Balanced tree
✔ Faster searching
✔ Time complexity: O(log n)

---

2️⃣ Red-Black Tree

✅ Definition

A Red-Black Tree is a self-balancing BST where each node is colored either red or black.

---

✅ Properties

1. Every node is red or black

2. Root is always black

3. Red node cannot have red child

4. Every path from root to NULL has same number of black nodes

5. Leaf nodes are black

---

✅ Advantages

✔ Less rotations than AVL
✔ Faster insertion and deletion
✔ Used in STL, Java TreeMap

---

🔹 Comparison: AVL vs Red-Black Tree

Feature	AVL Tree	Red-Black Tree
Balancing	Strict	Less strict
Speed	Faster search	Faster insert/delete
Rotations	More	Less
Use	Search-heavy	Insert-heavy

---

3️⃣ B-Trees

✅ Definition

A B-Tree is a self-balancing tree designed for disk storage systems.

---

✅ Properties

• All leaves at same level

• Multiple keys per node

• Used in databases & file systems

---

Order of B-Tree (m):

• Max children = m

• Min children = ⌈m/2⌉

---

Example:

B-Tree of order 3:

• Max keys = 2

• Min keys = 1

---

Advantages:

✔ Reduces disk access
✔ Balanced structure
✔ Efficient searching

---

4️⃣ Binomial Heap

✅ Definition

A Binomial Heap is a collection of binomial trees.

---

Properties:

• Each binomial tree follows min-heap property

• No two trees have same degree

---

Operations:

• Insert

• Merge

• Delete minimum

• Find minimum

---

Time Complexity:

Operation	Time
Insert	O(log n)
Merge	O(log n)
Delete min	O(log n)

---

5️⃣ Fibonacci Heap

✅ Definition

A Fibonacci Heap is an advanced heap structure used in graph algorithms.

---

Advantages:

✔ Faster decrease-key operation
✔ Used in Dijkstra & Prim algorithms

---

Time Complexity:

Operation	Time
Insert	O(1)
Decrease key	O(1)
Extract min	O(log n)

---

6️⃣ Comparison of Heaps

Feature	Binary Heap	Binomial Heap	Fibonacci Heap
Insert	O(log n)	O(log n)	O(1)
Delete Min	O(log n)	O(log n)	O(log n)
Merge	O(n)	O(log n)	O(1)
Complexity	Simple	Moderate	Complex

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 2)

✔ Explain AVL Tree with rotations
✔ Explain Red-Black Tree
✔ Difference between AVL & RB Tree
✔ Explain B-Tree
✔ Explain Fibonacci Heap
✔ Applications of heaps