📘 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

📘PAPER 3 – ARTIFICIAL INTELLIGENCE & ROBOTICS UNIT 5 – COMPUTER VISION & ROBOT PROGRAMMING (university of allahabad)

 

🔴 UNIT 5 – COMPUTER VISION & ROBOT PROGRAMMING

(Very important for theory + application-based questions)

---

👁️ 1. Computer Vision – Introduction

✅ Definition

Computer Vision is a field of AI that enables machines to:

• See

• Interpret

• Understand images and videos

Just like human vision, but using cameras and algorithms.

---

👁️ 2. Components of Computer Vision System

Main Components:

1. Image Sensor (Camera)

2. Image Acquisition System

3. Image Processing Unit

4. Feature Extraction

5. Decision Making System

---

👁️ 3. Image Formation Process

Steps:

1. Light falls on object

2. Reflected light captured by camera

3. Image converted into digital form

4. Image processed by computer

---

👁️ 4. Image Processing Steps

🔹 Step 1: Image Acquisition

• Capturing image using camera or sensor

🔹 Step 2: Pre-processing

• Noise removal

• Image enhancement

• Filtering

🔹 Step 3: Segmentation

• Dividing image into meaningful parts

🔹 Step 4: Feature Extraction

• Shape

• Color

• Texture

🔹 Step 5: Recognition

• Object identification

• Classification

---

👁️ 5. Object Recognition

Definition:

Identifying objects in an image.

Techniques:

• Template matching

• Feature-based recognition

• Pattern matching

Applications:

• Face recognition

• Number plate detection

• Medical imaging

---

👁️ 6. Vision Training & Adaptation

Vision Training

Teaching the system to recognize objects using sample images.

Adaptation

System improves performance by:

• Learning from experience

• Updating database

---

👁️ 7. Robot Programming

✅ Definition

Robot programming is the process of instructing a robot to perform tasks.

---

🔹 Types of Robot Programming

1️⃣ Online Programming

• Robot programmed in real-time

• Uses teach pendant

• Slow but accurate

---

2️⃣ Offline Programming

• Program written on computer

• Simulated before execution

• Faster and safer

---

🤖 8. Robot Programming Languages

Language	Use
VAL	Industrial robots
AML	Manufacturing
RAPID	ABB robots
KRL	KUKA robots
Python	AI & robotics

---

🤖 9. Robot Design

Key Factors:

✔ Mechanical design
✔ Sensors selection
✔ Actuators
✔ Control system
✔ Power supply

---

🤖 10. Robot Process Specifications

Defines:

• Task sequence

• Speed

• Accuracy

• Safety limits

---

🤖 11. Applications of Computer Vision & Robotics

✔ Industrial automation
✔ Medical diagnosis
✔ Surveillance
✔ Autonomous vehicles
✔ Face recognition
✔ Object detection

---

📌 IMPORTANT EXAM QUESTIONS (UNIT 5)

✅ Explain computer vision system
✅ Steps in image processing
✅ Robot programming methods
✅ Vision training and adaptation
✅ Applications of robot vision

📘PAPER 3 – ARTIFICIAL INTELLIGENCE & ROBOTICS UNIT 4 – ROBOT MOTION & CONTROL (university of allahabad)

🔴 UNIT 4 – ROBOT MOTION & CONTROL

---

🤖 1. Robot Motion

✅ Definition

Robot motion refers to the movement of robot parts (links & joints) to perform a task.

Robot motion includes:

• Translation

• Rotation

• Combined motion

---

🔹 Types of Robot Motion

1️⃣ Translational Motion

Movement in a straight line.

✔ Forward
✔ Backward
✔ Left / Right

Example: Conveyor belt movement

---

2️⃣ Rotational Motion

Movement around an axis.

✔ Joint rotation
✔ Arm rotation

Example: Robotic arm rotating to pick an object

---

🤖 2. Motion Conversion

Definition:

Conversion of one type of motion into another.

Examples:

Input Motion	Output Motion
Rotary	Linear
Linear	Rotary

---

Devices Used:

• Gears

• Belts

• Pulleys

• Lead screws

---

🤖 3. Lagrangian Analysis of Manipulator

✅ Definition

Lagrangian method is used to analyze robot dynamics using:

• Kinetic energy (T)

• Potential energy (V)

---

Lagrangian Equation:

$$L = T - V$$

Where:

• T = Kinetic Energy

• V = Potential Energy

---

Purpose:

✔ Used to derive equations of motion
✔ Helps in control system design
✔ Used in robot dynamics

---

🤖 4. Control of Actuators

✅ Actuator

An actuator converts electrical energy into mechanical motion.

---

Types of Actuators:

🔹 1. Electric Actuators

• DC motor

• Stepper motor

• Servo motor

✔ Easy to control
✔ Used in most robots

---

🔹 2. Hydraulic Actuators

• High force

• Used in heavy robots

---

🔹 3. Pneumatic Actuators

• Uses compressed air

• Fast but less accurate

---

🤖 5. Robot Control Systems

---

🔹 Open Loop Control

• No feedback

• Simple

• Low accuracy

Example: Timer-based robot

---

🔹 Closed Loop Control

• Feedback present

• High accuracy

• Used in industrial robots

Example: Servo motor system

---

🤖 6. Robot Sensory Devices

✅ Definition

Sensors provide information about:

• Position

• Speed

• Force

• Environment

---

Types of Sensors:

Sensor	Function
Position sensor	Joint position
Velocity sensor	Speed
Proximity sensor	Object detection
Touch sensor	Contact
Vision sensor	Image capture
Force sensor	Pressure detection

---

🤖 7. Robot Motion Control System

Components:

1. Controller

2. Actuator

3. Sensor

4. Feedback loop

---

Control Process:

1. Receive command

2. Compare with actual position

3. Generate error signal

4. Adjust movement

5. Reach target position

---

🤖 8. Linear vs Non-Linear Control

Linear Control	Non-Linear Control
Simple equations	Complex equations
Easy to implement	Difficult to design
Less accurate	More accurate
Used in basic robots	Used in advanced robots

---

🤖 9. Applications of Robot Motion Control

✔ Industrial automation
✔ Medical robots
✔ CNC machines
✔ Space robots
✔ Autonomous vehicles

---

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✅ Explain robot motion
✅ Lagrangian formulation
✅ Types of actuators
✅ Sensors used in robots
✅ Open vs closed loop control
✅ Motion conversion methods

📘PAPER 3 – ARTIFICIAL INTELLIGENCE & ROBOTICS UNIT 3 – ROBOTICS (university of allahabad)

 

🔴 UNIT 3 – ROBOTICS

(Kinematics, Control & Vision)

---

🤖 1. Introduction to Robotics

✅ What is a Robot?

A robot is a programmable electro-mechanical device capable of:

• Sensing environment

• Processing information

• Performing actions automatically

---

✅ Definition (Exam Ready)

A robot is a reprogrammable, multifunctional manipulator designed to move materials, parts, tools or devices through variable programmed motions.

---

🤖 2. Classification of Robots

🔹 Based on Structure:

1. Cartesian Robot

2. Cylindrical Robot

3. Spherical Robot

4. SCARA Robot

5. Articulated Robot

---

🔹 Based on Application:

• Industrial robots

• Medical robots

• Military robots

• Space robots

• Service robots

---

🤖 3. Robot Manipulator

A robot manipulator consists of:

• Links

• Joints

• End effector

---

🔹 Types of Joints

Joint	Motion
Revolute	Rotation
Prismatic	Linear
Spherical	Multi-axis
Cylindrical	Rotation + translation

---

🤖 4. Robot Kinematics

✅ Definition

Kinematics deals with motion of robots without considering forces.

---

🔹 Types of Kinematics

1️⃣ Forward Kinematics

• Determines end-effector position from joint values

• Easy to compute

📌 Example:
If joint angles are known → find hand position

---

2️⃣ Inverse Kinematics

• Determines joint values from end-effector position

• Difficult to compute

• Multiple or no solutions possible

📌 Used in:

• Robot arm movement

• Industrial automation

---

🤖 5. Robot Arm & Wrist Control

🔹 Arm Control

Controls position of robot arm using:

• Joint angles

• Velocity

• Acceleration

---

🔹 Wrist Control

Controls:

• Orientation

• Rotation

• Alignment of end-effector

---

🤖 6. Trajectory Generation

✅ Definition

Trajectory is the path followed by robot end-effector during motion.

---

Types:

1. Point-to-Point (PTP)

2. Continuous Path (CP)

---

Importance:

✔ Smooth motion
✔ Accuracy
✔ Energy efficiency

---

🤖 7. Robot Control System

Types of Control Systems:

---

🔹 1. Open Loop Control

• No feedback

• Simple

• Less accurate

Example: Washing machine timer

---

🔹 2. Closed Loop Control

• Feedback present

• High accuracy

• Used in robots

Example: Servo motor

---

🤖 8. Linear and Non-Linear Control

🔹 Linear Control

• Simple equations

• Easy to analyze

• Used in basic robots

---

🔹 Non-Linear Control

• Complex equations

• High accuracy

• Used in advanced robotics

---

🤖 9. Robot Vision System

✅ Definition

Robot vision is the ability of a robot to see and understand images using cameras and sensors.

---

Components:

1. Camera

2. Image processor

3. Feature extractor

4. Decision system

---

Applications:

• Object detection

• Quality inspection

• Face recognition

• Path planning

---

🤖 10. Robot Sensors

🔹 Types of Sensors

Sensor	Function
Position sensor	Detects position
Proximity sensor	Detects nearby object
Vision sensor	Image capture
Touch sensor	Detects contact
Force sensor	Measures force

---

🤖 11. Advantages of Robotics

✔ High accuracy
✔ Works in hazardous areas
✔ Increases productivity
✔ Reduces human error

---

🤖 12. Applications of Robotics

• Manufacturing

• Medical surgery

• Space exploration

• Military

• Agriculture

• Automation industry

---

📌 IMPORTANT EXAM QUESTIONS (UNIT 3)

✅ Explain robot kinematics
✅ Difference between forward and inverse kinematics
✅ Explain robot control system
✅ Write a note on robot vision
✅ Explain robot sensors
✅ Short note on trajectory planning