📘 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

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS (UNIT 1 – INTRODUCTION & SORTING TECHNIQUES ) university of allahabad

cx 

📘 PAPER 4 – DESIGN & ANALYSIS OF ALGORITHMS

🔴 UNIT 1 – INTRODUCTION & SORTING TECHNIQUES

---

1️⃣ Introduction to Algorithms

✅ What is an Algorithm?

An algorithm is a finite set of well-defined steps used to solve a problem.

✅ Characteristics of Algorithm

✔ Input
✔ Output
✔ Finiteness
✔ Definiteness
✔ Effectiveness

---

2️⃣ Analysis of Algorithms

Algorithm analysis means measuring performance in terms of:

🔹 Time Complexity

Time taken by an algorithm to run.

🔹 Space Complexity

Memory used by the algorithm.

---

3️⃣ Growth of Functions

Used to compare algorithm efficiency.

Common Growth Rates:

Notation	Name
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Linear-log
O(n²)	Quadratic
O(2ⁿ)	Exponential

---

4️⃣ Asymptotic Notations

🔹 Big-O Notation – Worst Case

O(n)

🔹 Omega (Ω) – Best Case

Ω(n)

🔹 Theta (Θ) – Average Case

Θ(n)

---

5️⃣ Recurrence Relations

A recurrence relation defines a function in terms of itself.

Example:

T(n) = T(n/2) + n

Solution Methods:

✔ Substitution method
✔ Recursion tree
✔ Master theorem

---

6️⃣ Sorting Algorithms

---

🔹 1. Shell Sort

Idea:

Improvement over insertion sort by comparing distant elements.

Steps:

1. Choose gap

2. Compare elements

3. Reduce gap

4. Repeat

Time Complexity:

• Best: O(n log n)

• Worst: O(n²)

---

🔹 2. Quick Sort

Concept:

Divide and conquer algorithm.

Steps:

1. Choose pivot

2. Partition array

3. Recursively sort subarrays

Time Complexity:

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

---

🔹 3. Merge Sort

Concept:

Divide array → Sort → Merge

Steps:

1. Divide array into halves

2. Recursively sort

3. Merge sorted parts

Time Complexity:

O(n log n)

Advantage:

✔ Stable
✔ Predictable time

---

🔹 4. Heap Sort

Based on:

Binary Heap

Steps:

1. Build heap

2. Extract max/min

3. Reheapify

Time Complexity:

O(n log n)

---

🔹 5. Counting Sort (Linear Sorting)

Used when:

• Elements are in limited range

Time Complexity:

O(n + k)

---

7️⃣ Comparison of Sorting Algorithms

Algorithm	Best	Worst	Stable
Bubble	O(n)	O(n²)	Yes
Selection	O(n²)	O(n²)	No
Insertion	O(n)	O(n²)	Yes
Quick	O(n log n)	O(n²)	No
Merge	O(n log n)	O(n log n)	Yes
Heap	O(n log n)	O(n log n)	No

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 1)

✔ Define algorithm
✔ Explain asymptotic notations
✔ Explain quick sort with example
✔ Compare merge sort and quick sort
✔ Explain recurrence relation