📘 PAPER 5 – OPERATING SYSTEM (UNIT 4 – UNIX & LINUX COMMANDS) university of allahabad

 

🔴 UNIT 4 – UNIX & LINUX COMMANDS

---

1️⃣ Introduction to UNIX / Linux

✅ UNIX

UNIX is a multi-user, multitasking operating system developed at AT&T Bell Labs.

✅ Linux

Linux is an open-source UNIX-based operating system.

---

🔹 Features of Linux

✔ Open source
✔ Secure
✔ Portable
✔ Multi-user
✔ Multitasking

---

2️⃣ Linux File System Structure

Directory	Purpose
/	Root directory
/bin	System commands
/etc	Configuration files
/home	User files
/usr	User programs
/var	Variable files
/tmp	Temporary files

---

3️⃣ Basic Linux Commands

---

📁 Directory Commands

Command	Description
pwd	Show current directory
ls	List files
cd	Change directory
mkdir	Create directory
rmdir	Remove empty directory

---

📄 File Commands

Command	Description
touch	Create file
cat	View file
cp	Copy file
mv	Move/rename file
rm	Delete file
file	File type

---

📘 Viewing Files

Command	Use
more	View page by page
less	Scrollable view
head	First 10 lines
tail	Last 10 lines

---

4️⃣ File Permission Commands

Permission Types:

Symbol	Meaning
r	Read
w	Write
x	Execute

---

Example:

-rwxr-xr--

---

Change Permission:

chmod 755 file.txt

---

5️⃣ Disk Related Commands

Command	Description
df	Disk free space
du	Disk usage
mount	Mount disk
umount	Unmount disk

---

6️⃣ Process Management Commands

Command	Function
ps	Show running processes
top	Real-time process
kill	Kill process
nice	Set priority
sleep	Delay execution

---

7️⃣ Input / Output Redirection

Symbols:

Symbol	Use
>	Output redirect
>>	Append
<	Input redirect
`	`

---

Example:

ls > file.txt
cat file.txt | grep abc

---

8️⃣ Background Processing

command &

---

9️⃣ Process Scheduling Commands

Command	Purpose
at	Schedule job
cron	Repeated jobs
crontab	Cron table

---

🔹 Example Cron Job:

* * * * * echo "Hello"

---

🔟 File Editing Commands

Editors:

✔ vi
✔ vim
✔ nano

---

vi Editor Modes:

1. Command mode

2. Insert mode

3. Exit mode

---

Important vi Commands:

Command	Function
i	Insert
:w	Save
:q	Quit
:wq	Save & quit
dd	Delete line

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✔ Explain Linux file system
✔ Explain Linux commands
✔ File permission in Linux
✔ Explain I/O redirection
✔ Explain process management commands
✔ Explain cron & at

📘 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