📘 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

📘 PAPER 3 – ARTIFICIAL INTELLIGENCE & ROBOTICS UNIT 2: KNOWLEDGE REPRESENTATION & REASONING (university of allahabad)

 

🔴 UNIT 2: KNOWLEDGE REPRESENTATION & REASONING

---

1️⃣ Knowledge Representation (KR)

✅ Definition

Knowledge Representation is the method used to store knowledge in a machine so that it can:

• Reason

• Learn

• Make decisions

---

✅ Goals of Knowledge Representation

✔ Represent real-world information
✔ Enable reasoning
✔ Easy to modify
✔ Efficient retrieval

---

2️⃣ Propositional Logic

✅ Definition

Propositional Logic is a formal system in which:

• Statements are either True or False

• Uses logical connectives

---

🔹 Basic Elements

Propositions

Statements that have truth values.

Example:

• “Ram is tall” → True/False

---

Logical Connectives

Symbol	Meaning
¬	NOT
∧	AND
∨	OR
→	IMPLIES
↔	IFF

---

Example:

P: It is raining  
Q: I carry umbrella  

P → Q

---

3️⃣ Syntax and Semantics

Syntax

Rules for forming valid expressions.

Semantics

Meaning or truth value of expressions.

---

4️⃣ Inference in Propositional Logic

🔹 Reasoning Methods

1. Forward Chaining

• Data-driven

• Starts from facts

• Moves forward using rules

2. Backward Chaining

• Goal-driven

• Starts from goal

• Works backward

---

5️⃣ Resolution Principle

Definition:

Resolution is a rule of inference used for proving statements.

Example:

P ∨ Q  
¬Q  
---------
P

✔ Used in theorem proving
✔ Important exam topic

---

6️⃣ First Order Logic (FOL)

✅ Definition

First Order Logic is more powerful than propositional logic because it:

• Uses quantifiers

• Represents objects and relationships

---

🔹 Quantifiers

Symbol	Meaning
∀	For all
∃	There exists

---

Example:

∀x (Human(x) → Mortal(x))

---

7️⃣ Inference in First Order Logic

🔹 Unification

Process of making two expressions identical.

Example:

P(x) and P(Ram)
⇒ x = Ram

---

🔹 Resolution in FOL

Steps:

1. Convert to clause form

2. Skolemization

3. Apply resolution rule

4. Derive empty clause

---

8️⃣ Knowledge Representation Techniques

---

🔹 1. Semantic Networks

Graph-based representation:

• Nodes → Objects

• Arcs → Relationships

Example:

Bird → can fly  
Sparrow → Bird

✔ Easy to understand
❌ Limited reasoning power

---

🔹 2. Frames

Structured representation using slots and values.

Example:

Slot	Value
Name	Bird
Wings	Yes
Fly	Yes

✔ Used in expert systems

---

🔹 3. Conceptual Graphs

• Graphical form of logic

• Combines semantic nets + logic

---

9️⃣ Uncertain Knowledge

Problem:

Real-world information is often:

• Incomplete

• Uncertain

• Imprecise

---

🔹 Probabilistic Reasoning

Uses probability to represent uncertainty.

Example:
P(Rain) = 0.7

---

🔹 Fuzzy Logic

Definition:

Fuzzy logic allows partial truth values between 0 and 1.

---

Example:

Temperature	Truth Value
Cold	0.2
Warm	0.7
Hot	0.9

---

Advantages:

✔ Handles uncertainty
✔ Used in washing machines, ACs
✔ Human-like reasoning

---

🔟 Learning in AI

Types of Learning:

🔹 1. Supervised Learning

• Uses labeled data

• Example: Classification

🔹 2. Unsupervised Learning

• No labeled data

• Clustering

🔹 3. Reinforcement Learning

• Reward-based learning

---

1️⃣1️⃣ Concept Learning

Learning general concepts from examples.

Example:
Learning “Bird” from examples like sparrow, pigeon.

---

1️⃣2️⃣ Inductive Learning

Learning by:

• Observing examples

• Generalizing rules

---

1️⃣3️⃣ Decision Tree Learning

Steps:

1. Select attribute

2. Split data

3. Build tree

4. Predict output

✔ Simple
✔ Easy to understand

---

1️⃣4️⃣ Neural Networks (Intro)

Definition:

A Neural Network is inspired by the human brain.

---

Single Layer Neural Network

• Input layer

• Output layer

• Weighted connections

Used for:

• Classification

• Pattern recognition

📘 PAPER 3: ARTIFICIAL INTELLIGENCE & ROBOTICS UNIT 1 – INTRODUCTION TO AI & SEARCH TECHNIQUES (university of allahabad)

 

🔴 UNIT 1 – INTRODUCTION TO AI & SEARCH TECHNIQUES

---

1️⃣ Introduction to Artificial Intelligence (AI)

✅ Definition of AI

Artificial Intelligence is a branch of computer science that deals with creating intelligent machines capable of performing tasks that normally require human intelligence.

Examples:

• Speech recognition

• Face detection

• Self-driving cars

• Chatbots

• Robotics

---

2️⃣ Scope of Artificial Intelligence

AI is widely used in the following fields:

🔹 1. Games

• Chess

• Ludo

• Video games

• AlphaGo

🔹 2. Theorem Proving

• Logical reasoning

• Mathematical proof verification

🔹 3. Natural Language Processing (NLP)

• Language translation

• Chatbots

• Speech recognition

🔹 4. Vision Systems

• Face recognition

• Object detection

• Medical image analysis

🔹 5. Robotics

• Industrial robots

• Medical robots

• Space robots

🔹 6. Expert Systems

• Medical diagnosis

• Fault detection

• Decision-making systems

---

3️⃣ AI Techniques

AI techniques are methods used to solve complex problems.

Important AI Techniques:

• Search techniques

• Knowledge representation

• Heuristic methods

• Machine learning

• Reasoning techniques

---

4️⃣ Intelligent Agents

✅ Definition

An Intelligent Agent is an entity that:

• Perceives environment using sensors

• Acts using actuators

• Makes decisions intelligently

---

Components of Intelligent Agent:

Component	Description
Sensors	Collect information
Actuators	Perform actions
Environment	Where agent operates
Agent function	Maps perception to action

---

Types of Agents

1. Simple reflex agent

2. Model-based agent

3. Goal-based agent

4. Utility-based agent

5. Learning agent

---

5️⃣ Search Techniques in AI

Search is the heart of AI.

Search Problem Components:

• Initial state

• Goal state

• Operators

• State space

• Path cost

---

6️⃣ State Space Search

Definition:

State space is a set of all possible states from initial to goal state.

Example:

8-puzzle problem

---

7️⃣ Control Strategies

Control strategy decides:

• Which node to expand next

• How to traverse state space

---

8️⃣ Blind Search Techniques

🔹 1. Breadth First Search (BFS)

Characteristics:

• Explores level by level

• Uses Queue (FIFO)

• Finds shortest path

Advantages:

✔ Complete
✔ Optimal

Disadvantages:

❌ High memory usage
❌ Slow for large problems

---

🔹 2. Depth First Search (DFS)

Characteristics:

• Goes deep first

• Uses Stack (LIFO)

Advantages:

✔ Less memory
✔ Easy to implement

Disadvantages:

❌ May go into infinite loop
❌ Not optimal

---

🔹 BFS vs DFS

BFS	DFS
Uses queue	Uses stack
Complete	Not always
High memory	Low memory
Optimal	Not optimal

---

9️⃣ Heuristic Search Techniques

✅ Heuristic

A heuristic is a rule of thumb used to guide the search.

---

🔹 1. Hill Climbing

• Moves toward better state

• Uses heuristic function

• Greedy approach

Problems:

• Local maxima

• Plateau

• Ridge

---

🔹 2. Best First Search

• Uses evaluation function f(n)

• Chooses best node first

---

🔹 3. A* Algorithm

Formula:

$$f(n) = g(n) + h(n)$$

Where:

• g(n) = cost from start to n

• h(n) = heuristic estimate

✔ Complete
✔ Optimal
✔ Widely used

---

🔟 AND–OR Graphs & AO* Algorithm

AND–OR Graph

• OR node → choose one path

• AND node → all paths required

---

AO* Algorithm

• Used for AND–OR graphs

• Improves A* algorithm

• Finds optimal solution graph

---

1️⃣1️⃣ Constraint Satisfaction Problem (CSP)

Definition:

A problem defined by:

• Variables

• Domains

• Constraints

Example:

• N-Queens problem

• Map coloring

---

1️⃣2️⃣ Game Playing in AI

Minimax Algorithm

• Two-player game

• MAX vs MIN

• Used in chess

---

Alpha-Beta Pruning

• Optimization of minimax

• Reduces nodes explored

• Faster execution

---

1️⃣3️⃣ Genetic Algorithms

Inspired by:

• Natural selection

• Evolution

Steps:

1. Initialization

2. Selection

3. Crossover

4. Mutation

5. New generation