Saturday, January 24, 2026

day one of theory of computation

1. The Three Pillars of ToC

Automata Theory: Studying abstract mathematical models (machines) to understand how they process input.
Computability Theory: Identifying which problems are "solvable" by a computer and which are "undecidable" (e.g., the Halting Problem).
Complexity Theory: Measuring how efficiently a problem can be solved in terms of time (steps) and space (memory).

2. Basic Definitions (The Vocabulary)

To begin, you must master these fundamental building blocks:

Symbol: The smallest unit of data (e.g., 0, 1, a, b).
Alphabet (
$cap sigma$
): A finite, non-empty set of symbols (e.g., binary
$cap sigma equals the set 0 comma 1 end-set$
).
String: A finite sequence of symbols from an alphabet (e.g., 0101).
Language: A set of strings (e.g., the set of all binary strings that end in 1).

3. Introduction to Finite Automata (FA)

The first model usually introduced is the Finite State Machine, which has no external memory.

Deterministic Finite Automata (DFA): For every state and input symbol, there is exactly one transition to a next state.
Non-Deterministic Finite Automata (NFA): Can have multiple possible next states for the same input, providing a more flexible but equivalent model for regular languages.

Friday, January 2, 2026

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS ( UNIT 5 – APPLICATION LAYER & NETWORK APPLICATIONS )

🔴 UNIT 5 – APPLICATION LAYER & NETWORK APPLICATIONS

🟦 1. Application Layer – Introduction

✅ Definition

The Application Layer is the topmost layer of the OSI model.
It provides services directly to the user.

👉 It acts as an interface between:

User
Network

🟦 2. Functions of Application Layer

✔ File transfer
✔ Email communication
✔ Remote login
✔ Web browsing
✔ Network management

🟦 3. Application Layer Protocols

🔹 1. FTP (File Transfer Protocol)

Purpose:

Used to transfer files between client and server.

Features:

✔ Reliable
✔ Uses TCP
✔ Supports upload & download

Ports:

Port 21 → Control
Port 20 → Data

🔹 2. TFTP (Trivial File Transfer Protocol)

Features:

✔ Simpler than FTP
✔ Uses UDP
✔ No authentication
❌ Less secure

🔹 3. SMTP (Simple Mail Transfer Protocol)

Purpose:

Used to send emails

Characteristics:

✔ Push protocol
✔ Works on TCP
✔ Port 25

🔹 4. POP3 (Post Office Protocol)

Purpose:

Used to receive emails

Features:

✔ Downloads mail
✔ Deletes mail from server

🔹 5. IMAP (Internet Message Access Protocol)

Difference from POP:

✔ Emails remain on server
✔ Can access from multiple devices

🔹 6. HTTP (Hyper Text Transfer Protocol)

Used for:

✔ Web browsing
✔ Communication between browser and server

Features:

✔ Stateless
✔ Uses TCP
✔ Port 80

🔹 7. HTTPS

Secure version of HTTP

Uses:
✔ SSL / TLS encryption
✔ Port 443

🟦 4. DNS (Domain Name System)

Definition:

DNS converts:


Domain Name → IP Address

Example:


www.google.com → 142.250.192.14

DNS Hierarchy:

🟦 5. SNMP (Simple Network Management Protocol)

Purpose:

Used to manage and monitor network devices.

Components:

✔ Manager
✔ Agent
✔ MIB

🟦 6. TELNET

Definition:

Allows remote login to another computer.

❌ Not secure
✔ Replaced by SSH

🟦 7. Network Applications

Common Applications:

✔ Email
✔ File sharing
✔ Video conferencing
✔ Web browsing
✔ Cloud services

🟦 8. Client–Server Model

Client:

Requests services

Server:

Provides services

Example:
Browser → Web Server

🟦 9. Peer-to-Peer Network

Features:

✔ No central server
✔ Each node is client & server
✔ Used in file sharing

🟦 10. Internet & Public Networks

Internet:

Global network of networks

Public Network:

Accessible by all users

📌 EXAM IMPORTANT QUESTIONS (UNIT 5)

✔ Explain FTP, SMTP, POP, IMAP
✔ Difference between HTTP & HTTPS
✔ DNS working
✔ Application layer protocols
✔ Client-server vs P2P
✔ SNMP explanation

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS (UNIT 4 – TRANSPORT, SESSION & PRESENTATION LAYERS)

🔴 UNIT 4 – TRANSPORT, SESSION & PRESENTATION LAYERS

🟦 PART A: TRANSPORT LAYER

1️⃣ Transport Layer – Introduction

✅ Definition

The Transport Layer is responsible for:
✔ End-to-end communication
✔ Reliable data transfer
✔ Flow control
✔ Error control

It works between:
➡ Application Layer and Network Layer

2️⃣ Functions of Transport Layer

✔ Segmentation & Reassembly
✔ Service point addressing (Port numbers)
✔ Flow control
✔ Error control
✔ Connection control

3️⃣ Transport Layer Protocols

🔹 1. TCP (Transmission Control Protocol)

Features:

✔ Connection-oriented
✔ Reliable
✔ Error-free transmission
✔ Flow control
✔ Congestion control

TCP Services:

TCP Header Contains:

4️⃣ TCP Connection Management

🔹 Three-Way Handshake

1️⃣ SYN →
2️⃣ SYN + ACK →
3️⃣ ACK →

✔ Connection established

🔹 Connection Termination

Uses:

5️⃣ UDP (User Datagram Protocol)

Features:

✔ Connectionless
✔ Fast
✔ No error checking
✔ No flow control

Used In:

6️⃣ TCP vs UDP

TCP	UDP
Reliable	Unreliable
Connection-oriented	Connectionless
Slower	Faster
Error control	No error control
Used for emails	Used for video

🟦 PART B: SESSION LAYER

7️⃣ Session Layer – Introduction

Definition:

Session layer manages:
✔ Session establishment
✔ Session maintenance
✔ Session termination

Functions:

Dialog control
Synchronization
Session checkpointing

Example:

✔ Video conferencing
✔ Online login sessions

🟦 PART C: PRESENTATION LAYER

8️⃣ Presentation Layer – Introduction

Definition:

Presentation layer is responsible for:
✔ Data formatting
✔ Encryption
✔ Compression

Functions:

🔹 1. Data Translation

Converts data format (ASCII, EBCDIC)

🔹 2. Encryption

Provides security

🔹 3. Compression

Reduces data size

9️⃣ Encryption Techniques

🔹 Symmetric Encryption

Same key for encryption & decryption
Example: AES

🔹 Asymmetric Encryption

Public key + Private key
Example: RSA

🔟 Comparison of Layers

Layer	Main Function
Transport	End-to-end delivery
Session	Session control
Presentation	Data formatting & security

📌 EXAM IMPORTANT QUESTIONS (UNIT 4)

✔ Explain TCP/IP
✔ TCP vs UDP
✔ Three-way handshake
✔ Functions of session layer
✔ Functions of presentation layer
✔ Encryption techniques

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS (UNIT 3 – NETWORK LAYER) university of allahabad

🔴 UNIT 3 – NETWORK LAYER

1️⃣ Network Layer – Introduction

✅ Definition

The Network Layer is responsible for:

Routing packets
Logical addressing
Path selection
Congestion control

👉 It ensures data reaches the correct destination network.

2️⃣ Functions of Network Layer

✔ Logical addressing
✔ Routing
✔ Packet forwarding
✔ Congestion control
✔ Internetworking

3️⃣ Network Layer Services

🔹 Connection-Oriented Service

Establishes connection before transmission
Reliable
Example: Virtual circuits

🔹 Connectionless Service

No prior connection
Fast but unreliable
Example: Internet (IP)

4️⃣ Routing

✅ Definition

Routing is the process of selecting the best path to transfer data from source to destination.

5️⃣ Types of Routing

🔹 1. Static Routing

Fixed routes
Manually configured
Used in small networks

🔹 2. Dynamic Routing

Routes change automatically
Uses routing algorithms

6️⃣ Routing Algorithms

🔹 1. Distance Vector Routing

Features:

Based on distance and direction
Uses Bellman-Ford algorithm

Example:

RIP (Routing Information Protocol)

Problems:

❌ Count to infinity
❌ Slow convergence

🔹 2. Link State Routing

Features:

Each node knows full topology
Uses Dijkstra’s algorithm

Example:

OSPF (Open Shortest Path First)

Advantages:

✔ Fast
✔ Accurate

7️⃣ Congestion Control

✅ Definition

Congestion occurs when:

Network traffic exceeds capacity.

Causes:

Too many packets
Limited bandwidth
Slow routers

Congestion Control Techniques:

🔹 Open Loop

Prevent congestion
No feedback

Examples:
✔ Traffic shaping
✔ Admission control

🔹 Closed Loop

Detect & correct congestion
Uses feedback

Examples:
✔ Backpressure
✔ Choke packet

8️⃣ Internetworking

Definition:

Connecting multiple networks together to form the Internet.

Devices Used:

Router
Gateway
Bridge

9️⃣ Internet Protocol (IP)

✅ IP

Responsible for:

Logical addressing
Packet delivery

🔹 IPv4 Address

IPv4 Classes

Class	Range
A	1–126
B	128–191
C	192–223
D	Multicast
E	Experimental

🔹 IPv6

Features:

✔ 128-bit address
✔ Larger address space
✔ Better security
✔ No NAT needed

Example:


2001:0db8:85a3::8a2e:0370:7334

🔟 Difference Between IPv4 and IPv6

IPv4	IPv6
32-bit	128-bit
Limited addresses	Large address space
NAT required	No NAT
Less secure	More secure

📌 EXAM IMPORTANT QUESTIONS (UNIT 3)

✔ Explain Network Layer
✔ Routing algorithms
✔ Difference between distance vector & link state
✔ Congestion control
✔ IPv4 vs IPv6
✔ IP addressing

📘 PAPER 6 – DATA COMMUNICATION & NETWORKS (UNIT 2 – DATA LINK LAYER & MEDIUM ACCESS CONTROL) university of allahabad

🔴 UNIT 2 – DATA LINK LAYER & MEDIUM ACCESS CONTROL

1️⃣ Data Link Layer – Introduction

✅ Definition

The Data Link Layer is the second layer of the OSI model.
It is responsible for reliable data transfer between two directly connected nodes.

✅ Main Functions

✔ Framing
✔ Error control
✔ Flow control
✔ Access control
✔ Physical addressing

2️⃣ Framing

🔹 Definition

Framing divides the data stream into manageable units called frames.

🔹 Methods of Framing

1. Character Count

Frame size specified in header
❌ Error-prone

2. Byte Stuffing

Special character added to data
✔ Used in HDLC

3. Bit Stuffing

Extra bit inserted after 5 consecutive 1s
✔ Used in modern networks

3️⃣ Error Detection Techniques

🔹 1. Parity Check

Adds 1 parity bit
Detects single-bit error

🔹 2. Checksum

Sum of data bits
Used in TCP/IP

🔹 3. Cyclic Redundancy Check (CRC)

Most powerful method
Uses polynomial division

✔ Highly reliable
✔ Widely used

4️⃣ Error Control

Error control ensures reliable data delivery.

Methods:

✔ Error detection
✔ Error correction
✔ Retransmission

5️⃣ Flow Control

Definition:

Controls the amount of data sent to avoid receiver overflow.

Methods:

Stop-and-Wait
Sliding Window

6️⃣ Sliding Window Protocol

Types:

🔹 1. Stop-and-Wait ARQ

Send one frame
Wait for ACK
Simple but slow

🔹 2. Go-Back-N ARQ

Sends multiple frames
Retransmits all frames after error

🔹 3. Selective Repeat ARQ

Retransmits only erroneous frame
Efficient but complex

7️⃣ Medium Access Control (MAC)

Definition:

MAC controls who can transmit data on shared medium.

8️⃣ Channel Allocation Methods

🔹 1. Static Channel Allocation

Fixed bandwidth
Inefficient for bursty traffic

🔹 2. Dynamic Channel Allocation

Bandwidth allocated as needed
Used in LANs

9️⃣ Multiple Access Protocols

🔹 ALOHA Protocol

Types:

Pure ALOHA
Slotted ALOHA

Pure ALOHA

Send anytime
High collision
Low efficiency (~18%)

Slotted ALOHA

Time divided into slots
Higher efficiency (~36%)

🔹 CSMA (Carrier Sense Multiple Access)

Types:

1️⃣ CSMA/CD (Collision Detection)

Used in Ethernet
Detects collision and stops transmission

2️⃣ CSMA/CA (Collision Avoidance)

Used in Wi-Fi
Avoids collision before transmitting

1️⃣0️⃣ IEEE Standards

Standard	Description
IEEE 802.3	Ethernet
IEEE 802.11	Wi-Fi
IEEE 802.5	Token Ring
IEEE 802.15	Bluetooth

1️⃣1️⃣ Data Link Layer Protocols

✔ HDLC
✔ PPP
✔ Ethernet

📌 EXAM IMPORTANT QUESTIONS (UNIT 2)

✔ Explain Data Link Layer
✔ Framing techniques
✔ Sliding Window Protocol
✔ ALOHA vs CSMA
✔ Error detection methods
✔ CRC explanation