📘 PAPER 5 – OPERATING SYSTEM (UNIT 5 – SHELL PROGRAMMING & FILTER COMMANDS) university of allahabad

 

🔴 UNIT 5 – SHELL PROGRAMMING & FILTER COMMANDS

---

🟢 1. Introduction to Shell

✅ What is a Shell?

A Shell is a command-line interpreter that:

• Accepts user commands

• Executes them

• Acts as an interface between user and OS

---

🔹 Types of Shells in Linux

Shell	Description
sh	Bourne shell
bash	Bourne Again Shell (most used)
csh	C shell
ksh	Korn shell
zsh	Advanced shell

👉 Bash is most commonly used.

---

🟢 2. Shell Programming

✅ Definition

Shell programming is writing a script to automate tasks using shell commands.

---

🔹 Advantages

✔ Saves time
✔ Automates tasks
✔ Easy to write
✔ Used in system administration

---

🟢 3. Structure of Shell Script

#!/bin/bash
echo "Hello World"

Explanation:

• #!/bin/bash → Shebang line

• echo → Print output

---

🔹 Running a Shell Script

chmod +x file.sh
./file.sh

---

🟢 4. Variables in Shell

User Defined Variable

name="Amit"
echo $name

---

System Variables

$HOME
$USER
$PATH

---

🟢 5. Read Command

echo "Enter name:"
read name
echo "Hello $name"

---

🟢 6. Conditional Statements

---

🔹 if Statement

if [ $a -gt $b ]
then
  echo "A is greater"
fi

---

🔹 if-else

if [ $a -eq $b ]
then
  echo "Equal"
else
  echo "Not equal"
fi

---

🔹 Case Statement

case $choice in
1) echo "One";;
2) echo "Two";;
*) echo "Invalid";;
esac

---

🟢 7. Looping Statements

---

🔹 for Loop

for i in 1 2 3
do
  echo $i
done

---

🔹 while Loop

i=1
while [ $i -le 5 ]
do
  echo $i
  i=$((i+1))
done

---

🟢 8. Command Line Arguments

echo "File name: $0"
echo "First arg: $1"
echo "Second arg: $2"

---

🟢 9. Filter Commands

Filter commands process text input and give output.

---

🔹 1. grep

Search text in file

grep "hello" file.txt

---

🔹 2. sed

Stream editor (search & replace)

sed 's/old/new/' file.txt

---

🔹 3. awk

Used for report generation

awk '{print $1}' file.txt

---

🔹 4. cut

Extract columns

cut -d ":" -f1 file.txt

---

🔹 5. sort

Sort data

sort file.txt

---

🔹 6. uniq

Remove duplicate lines

uniq file.txt

---

🟢 10. Pipes

Used to connect commands.

ls | grep ".txt"

---

🟢 11. Shell Keywords

Keyword	Use
if	Condition
then	Execution
fi	End if
for	Loop
do	Loop start
done	Loop end

---

🟢 12. Shell Script Example

Program: Check Even or Odd

echo "Enter number:"
read n

if [ $((n % 2)) -eq 0 ]
then
  echo "Even"
else
  echo "Odd"
fi

---

📌 IMPORTANT EXAM QUESTIONS (UNIT 5)

✔ Explain shell scripting
✔ Write shell program for even/odd
✔ Explain grep, sed, awk
✔ Explain pipes & filters
✔ Write notes on shell variables
✔ Explain case statement

📘 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