Note

Combinational circuits have outputs that depend only on present inputs, while sequential circuits
depend on present inputs and previous states.

 Logic gates
 Boolean algebra
 Karnaugh maps (K-maps)
 Multiplexers/Decoders
 Flip-flops
 Registers
 Counters

Feature Greedy Best-First Search A* Search

Evaluation Function (f(n)=h(n)) (f(n)=g(n)+h(n))
Uses Path Cost (g(n))? No Yes
Optimal? No Yes (with admissible heuristic)
Usually Faster? Often Sometimes slower
It ignores path cost g( n) and relies only on h( n)

RAID and Its Levels

What is RAID?
RAID (Redundant Array of Independent Disks) is a technology that combines multiple hard
disks into one logical unit to improve:

 Performance (Speed)
 Reliability (Fault Tolerance)
 Storage Capacity

RAID Levels
1. RAID 0 (Striping)

 Data is split across multiple disks.

 No backup or redundancy.

Advantages

 Very fast read/write speed.

 Uses 100% of disk capacity.
Disadvantages

 No fault tolerance.
 If one disk fails, all data is lost.

Disk 1: A1 A3 A5
Disk 2: A2 A4 A6

✅ High Performance
❌ No Data Protection

2. RAID 1 (Mirroring)

 Data is copied identically to two or more disks.

Disk 1: A B C D
Disk 2: A B C D

Advantages

 Excellent reliability.
 Easy recovery if a disk fails.

Disadvantages

 Requires double storage space.

✅ High Reliability
❌ 50% Storage Efficiency

3. RAID 2

 Uses bit-level striping and error-correcting codes.

 Rarely used today.

Advantages

 Error correction.

Disadvantages

 Complex and expensive.

✅ Error Detection
❌ Rarely Used

4. RAID 3

 Byte-level striping with a dedicated parity disk.

Disk 1: Data
Disk 2: Data
Disk 3: Parity

Advantages

 Good fault tolerance.

Disadvantages

 Parity disk can become a bottleneck.

✅ Fault Tolerance
❌ Parity Bottleneck

5. RAID 4

 Block-level striping with a dedicated parity disk.

Advantages

 Better performance than RAID 3.

Disadvantages

 Dedicated parity disk may slow writes.

✅ Fault Tolerance
❌ Write Bottleneck

6. RAID 5

 Block-level striping with distributed parity.

Disk 1: Data + Parity
Disk 2: Data + Parity
Disk 3: Data + Parity

Advantages

 Good balance of speed and reliability.

 Can survive one disk failure.

Disadvantages

 Rebuilding after failure can be slow.

✅ Most Popular RAID Level

✅ Good Performance + Protection

7. RAID 6

 Similar to RAID 5 but uses double parity.

Advantages

 Can survive two disk failures.

Disadvantages

 More storage overhead.

✅ Very High Reliability

❌ Slightly Slower Writes

8. RAID 10 (RAID 1+0)

 Combines RAID 1 (Mirroring) and RAID 0 (Striping).

Mirror Pair 1
Mirror Pair 2
Data striped across pairs

Advantages

 Excellent speed and reliability.

 Common in enterprise servers and databases.
Disadvantages

 Requires many disks.

✅ Best Performance + Reliability

❌ Expensive

Quick Comparison
RAID Technique Fault Tolerance Performance
RAID 0 Striping ❌ No ⭐⭐⭐⭐⭐
RAID 1 Mirroring ✅ Yes ⭐⭐⭐
RAID 2 ECC ✅ Yes ⭐⭐
RAID 3 Striping + Parity ✅ Yes ⭐⭐⭐
RAID 4 Block Striping + Parity ✅ Yes ⭐⭐⭐
RAID 5 Distributed Parity ✅ Yes (1 disk) ⭐⭐⭐⭐
RAID 6 Double Parity ✅ Yes (2 disks) ⭐⭐⭐
RAID 10 Mirroring + Striping ✅ Yes ⭐⭐⭐⭐⭐

Exit Exam Shortcuts

 RAID 0 → Fastest, no backup.
 RAID 1 → Mirroring, highest simple reliability.
 RAID 5 → Most common enterprise RAID.
 RAID 6 → Survives 2 disk failures.
 RAID 10 → Best combination of speed and reliability.

Memory Trick

 0 = Zero protection
 1 = One copy (mirror)
 5 = One parity disk worth of protection
 6 = Two parity protections
 10 = 1 + 0 (Mirror + Stripe)

For most Exit Exams, remember:

RAID 0 = Speed, RAID 1 = Safety, RAID 5 = Balanced, RAID 10 = Best Overall.

A Masquerade Attack occurs when an attacker pretends to be another legitimate user to gain
unauthorized access or deceive others

 Replay Attack: Captures a valid message and retransmits it later.

 Notation Cardinality
No arrows Many-to-Many (M:N)
Arrow to one entity Many-to-One (M:1)
Arrow to both entities One-to-One (1:1)
One side "one", other side "many" One-to-Many (1:M)

Functional vs Non-Functional Requirements

Requirements in software engineering are commonly divided into Functional Requirements
and Non-Functional Requirements.

Functional Requirements Non-Functional Requirements

Describe what the system should do Describe how well the system should perform
Define system features and functions Define quality attributes and constraints
Focus on behavior Focus on performance and quality
Usually expressed as services Usually expressed as measurable criteria

1. Functional Requirements
Functional requirements specify the services, tasks, or functions the system must provide.

Examples

 User can log in.

 Student can register for courses.
 Customer can place an order.
 Admin can generate reports.
 System can calculate grades.

Question Example

What should the system do?

 Allow users to create accounts.

 Search products.
 Process payments.

These are functional requirements.

2. Non-Functional Requirements
Non-functional requirements specify the quality attributes of the system.

Examples

 The system shall respond within 2 seconds.

 The system shall be available 99.9% of the time.
 User passwords shall be encrypted.
 The system shall support 10,000 users simultaneously.
 The interface shall be easy to use.

Question Example

How should the system perform?

 Fast
 Secure
 Reliable
 Scalable

These are non-functional requirements.

Easy Example: Online Shopping System

Functional Requirements

 Users can register.

 Users can log in.
 Users can add products to a cart.
 Users can make payments.

Non-Functional Requirements

 Pages load within 3 seconds.

 Payment transactions are encrypted.
 System uptime is 99.9%.
 Support up to 5,000 concurrent users.

Exit Exam Shortcut

Functional = WHAT
  Login
 Register
 Search
 Add Product
 Generate Report

Non-Functional = HOW WELL

 Fast
 Secure
 Reliable
 Available
 Scalable
 User-Friendly

Memory Trick

Functional → Features (What)

Non-Functional → Quality (How Well)

✅ "The system shall allow students to register courses." → Functional Requirement

✅ "The system shall respond within 2 seconds." → Non-Functional Requirement

Method Overloading vs Method Overriding

Feature Method Overloading Method Overriding
Same method name, different Same method name and same parameters in
Definition
parameters parent and child classes
Inheritance
❌ No ✅ Yes
Required?
Parameters Must be different Must be the same
May differ (depending on
Return Type Usually same or compatible
language rules)
Polymorphism
Compile-time (Static) Run-time (Dynamic)
Type

1. Method Overloading
Method overloading occurs when multiple methods have the same name but different
parameter lists.

Example (C++)
class Math {
public:
int add(int a, int b) {
return a + b;
}

int add(int a, int b, int c) {

return a + b + c;
}
};

Here, add() is overloaded because the number of parameters is different.

Key Point

✅ Same method name

✅ Different parameters

2. Method Overriding
Method overriding occurs when a child class provides its own implementation of a method
already defined in the parent class.

Example (C++)
class Animal {
public:
void sound() {
cout << "Animal sound";
}
};

class Dog : public Animal {

public:
void sound() {
cout << "Dog barks";
}
};

Here, Dog overrides the sound() method of Animal.

Key Point

✅ Inheritance required
✅ Same method name
✅ Same parameters
Easy Example
Overloading
print(int x);
print(double x);
print(string x);

Same name, different parameters.

Overriding
class Parent {
void show();
}

class Child : public Parent {

void show();
}

Child replaces Parent's method.

Exit Exam Shortcut

Method Overloading

 Same name
 Different parameters
 No inheritance required
 Compile-time polymorphism

Method Overriding

 Same name
 Same parameters
 Requires inheritance
 Run-time polymorphism

Memory Trick

Overloading = Adding more versions of a method

Overriding = Replacing a parent's method in the child class

Common Exit Exam Question

Method overriding is associated with:

A. Compile-time polymorphism
B. Run-time polymorphism
C. Encapsulation
D. Abstraction

✅ Answer: B. Run-time polymorphism

Method overloading is associated with:

A. Compile-time polymorphism
B. Run-time polymorphism

✅ Answer: A. Compile-time polymorphism

 Private → Same class only.

 Default → Same package only.
 Protected → Same package + subclasses in other packages. ✅
 Public → Accessible everywhere.

Keyword Purpose
final method Cannot be overridden
final class Cannot be inherited
final variable Cannot be changed (constant)

In Java, a method declared as final cannot be overridden by subclasses.

These are types of reasoning in Artificial Intelligence and Logic:

1. Deductive Reasoning

 Goes from general → specific.

 If the premises are true, the conclusion must be true.

Example:

 All humans are mortal.

 Socrates is a human.
 Therefore, Socrates is mortal.

✅ Conclusion is certain.
2. Inductive Reasoning

 Goes from specific observations → general rule.

 Conclusion is probable, not guaranteed.

Example:

 The sun has risen every day so far.

 Therefore, the sun will rise tomorrow.

✅ Conclusion is likely.

3. Abductive Reasoning

 Starts with an observation and seeks the most likely explanation.

Example:

 The ground is wet.

 It probably rained.

✅ Best possible explanation, but not certain.

4. Analogical Reasoning

 Solves a problem by comparing it to a similar known situation.

Example:

 Earth has gravity and supports life.

 A similar planet may also support life.

✅ Based on similarity.

Exit Exam Shortcut

Reasoning Type Pattern

Deductive General → Specific
Reasoning Type Pattern
Inductive Specific → General
Abductive Observation → Best Explanation
Analogical Similarity → Conclusion

Memory Trick

 Deduction = Definite conclusion.

 Induction = Infer a general rule.
 Abduction = Best explanation.
 Analogy = Similar cases.

A common MCQ:

"Which reasoning derives a general rule from specific observations?"

A. Abductive
B. Analogical
C. Deductive
D. Inductive

✅ Answer: D. Inductive Reasoning.

In Java, interfaces are used to achieve multiple inheritance. While Java doesn't support multiple
inheritance through classes, it allows a class to implement multiple interfaces. Interfaces provide a way
to define methods that must be implemented by any class that uses them, thus allowing different
behaviors to be inherited from multiple sources

Polymorphism allows a class in Java to implement multiple interfaces. It enables objects to be treated as
instances of their parent interface or class, allowing different classes to define their own unique
implementations of interface methods. By implementing multiple interfaces, a class can adopt behaviors
defined by those interfaces, leveraging polymorphism to interact with them

Top-Down Parser vs Bottom-Up Parser

Parsers are used in Compiler Design to check whether a program follows the grammar of a
language.

1. Top-Down Parser
A top-down parser starts from the start symbol and tries to derive the input string.
How it Works

 Builds the parse tree from root to leaves.

 Starts with the start symbol.
 Expands productions until the input is matched.

Examples

 Recursive Descent Parser

 Predictive Parser (LL(1))

Derivation Used

✅ Leftmost Derivation

Simple Example

Grammar:

S → aB
B → b

Input:

ab

Derivation:

S ⇒ aB ⇒ ab

2. Bottom-Up Parser
A bottom-up parser starts from the input string and reduces it to the start symbol.

How it Works

 Builds the parse tree from leaves to root.

 Repeatedly reduces symbols according to grammar rules.

Examples

 Shift-Reduce Parser
 LR Parser
 SLR Parser
 LALR Parser
Derivation Used

✅ Rightmost Derivation in Reverse

Example

Input:

ab

Reduction:

ab ⇒ aB ⇒ S

Comparison
Feature Top-Down Parser Bottom-Up Parser
Starts From Start Symbol Input String
Parse Tree Root → Leaves Leaves → Root
Derivation Leftmost Rightmost (Reverse)
Simplicity Simpler More Complex
Efficiency Less Powerful More Powerful
Examples LL(1), Recursive Descent LR, SLR, LALR

Exit Exam Shortcuts

Top-Down Parser

 Start symbol → Input

 Root → Leaves
 Leftmost Derivation
 Example: LL(1)

Bottom-Up Parser

 Input → Start symbol

 Leaves → Root
 Rightmost Derivation in Reverse
 Example: LR Parser

Memory Trick
Top-Down
➡️Start from the TOP (root) and go down.

⬆️Start from the BOTTOM (input) and go up.

Bottom-Up

Common Exit Exam Question

Which parser uses rightmost derivation in reverse?

A. Predictive Parser
B. Recursive Descent Parser
C. Top-Down Parser
D. Bottom-Up Parser

✅ Answer: D. Bottom-Up Parser

Which parser builds the parse tree from root to leaves?

A. Bottom-Up Parser
B. Top-Down Parser

✅ Answer: B. Top-Down Parser.

It looks like the question is incomplete (no statement is given), but this type of MCQ usually
asks to identify a search strategy or compare them.

Here is a quick Exit Exam summary of each option so you can answer any variant of the
question:

A. Greedy Best-First Search

 Uses a heuristic (h(n))
 Expands the node that seems closest to goal
 Fast but not optimal

📌 Idea: “Go where the goal looks nearest”

B. Depth-First Search (DFS)

 Explores deep first, then backtracks
  Uses a stack (or recursion)
 Not optimal, may get stuck in deep paths

📌 Idea: “Go deep before wide”

C. Depth-Limited Search (DLS)

 Same as DFS but with a depth limit
 Avoids infinite search

📌 Idea: “DFS with a maximum depth”

D. Breadth-First Search (BFS)

 Explores level by level
 Uses a queue
 Complete and optimal (for unweighted graphs)

📌 Idea: “Explore all neighbors first”

Quick Comparison Table

Algorithm Strategy Uses Heuristic Optimal
Greedy Best-First Best-looking node Yes ❌ No
DFS Deep exploration No ❌ No
DLS Limited DFS No ❌ No
BFS Level-by-level No ✅ Yes

Most Common Exit Exam Answer Rules

 If question says “uses heuristic” → Greedy Best-First
 If question says “level order / shortest path (unweighted)” → BFS
 If question says “deep search” → DFS
 If question says “DFS with limit” → DLS
If you send the full question, I can give you the exact correct option.

These options are types of security attacks (CIA model attacks).

Let’s define each:

A. Modification (Tampering)
 Attacker changes data/content
 Integrity is violated

Example:

 Changing bank account balance from 1000 → 10000

📌 Meaning: Data is altered

B. Interception
 Attacker secretly accesses data
 Violates confidentiality

Example:

 Eavesdropping on messages
 Packet sniffing

📌 Meaning: Data is read without permission

C. Interruption
 Attack that makes system/service unavailable
 Violates availability

Example:

 Denial of Service (DoS)

 Server crash
📌 Meaning: System is blocked or stopped

D. Fabrication
 Attacker creates fake data/messages
 Violates authenticity

Example:

 Fake login messages

 Spoofed emails

📌 Meaning: Fake data is inserted

Exit Exam Summary Table

Attack Type Meaning Security Property
Modification Change data Integrity
Interception Steal/read data Confidentiality
Interruption Stop service Availability
Fabrication Create fake data Authenticity

Memory Trick
 Interception → I see it (secretly)
 Interruption → Interrupt service
 Modification → Modify data
 Fabrication → Fake data

If you want, I can also give you CIA triad + attack mapping questions (very common in exit
exams).

These are CPU Scheduling performance metrics in Operating Systems.

1. Turnaround Time (TAT)

  Total time taken for a process from arrival to completion

[
TAT = Completion\ Time - Arrival\ Time
]

📌 Meaning: How long the process stays in the system

2. Waiting Time (WT)

 Total time a process spends waiting in the ready queue

[
WT = Turnaround\ Time - Burst\ Time
]

📌 Meaning: Time spent waiting before execution

3. Response Time (RT)

 Time from arrival to first response (first CPU allocation)

[
RT = First\ CPU\ Start - Arrival\ Time
]

📌 Meaning: How quickly the system responds

4. Throughput
 Number of processes completed per unit time

[
Throughput = \frac{Number\ of\ Completed\ Processes}{Total\ Time}
]

📌 Meaning: System productivity

Quick Comparison Table
Metric Definition
Turnaround Time Arrival → Completion
Waiting Time Time spent waiting in queue
Response Time Arrival → First response
Throughput Processes completed per time

Easy Memory Trick

 Turnaround → Total time in system
 Waiting → Time waiting only
 Response → First reaction time
 Throughput → How many finished

Exit Exam Tip

If a question says:

 “Total time to finish process” → Turnaround Time

 “Time waiting in queue” → Waiting Time
 “First response time” → Response Time
 “Number of processes completed” → Throughput

If you want, I can give you a numerical example (very common in exit exams).

Got it — here is a clear Exit-Exam style cheat sheet for BOTH Symmetric and Asymmetric
Cryptography, including the exact MCQ pattern like your question.

🔐 1. Symmetric Cryptography (Secret Key)

📌 Core Idea
Same key is used for encryption and decryption
🔁 Process
Sender encrypts → Shared Secret Key → Receiver decrypts

📌 Important Points
 One shared key
 Same key for both sides
 Very fast
 Used for large data encryption
 Key distribution is difficult

📚 Examples
 AES
 DES
 3DES

❓ MCQ Style Questions

Q1:

Encryption and decryption use the same key. This is:

A. Asymmetric
B. Symmetric
C. Hashing
D. Steganography

✔️Answer: B. Symmetric

Q2:

Symmetric cryptography is mainly used for:

A. Digital signatures
B. Key exchange
C. Bulk data encryption
D. Authentication only

✔️Answer: C. Bulk data encryption

🧠 Memory Trick
👉 “Same Key = Symmetric”

🔐 2. Asymmetric Cryptography (Public Key)

📌 Core Idea
Two different keys: Public + Private

🔁 Process
Encrypt → Receiver Public Key
Decrypt → Receiver Private Key

📌 Important Points
 Uses key pair
 Public key = shared
 Private key = secret
 More secure than symmetric
 Slower than symmetric
 Solves key distribution problem

📚 Examples
 RSA
 ECC
 Diffie-Hellman
❓ MCQ Style Questions
Q1:

In asymmetric cryptography, message is decrypted using:

A. Receiver’s public key

B. Receiver’s private key
C. Sender’s private key
D. Sender’s public key

✔️Answer: B. Receiver’s private key

Q2:

In asymmetric cryptography, encryption is done using:

A. Receiver’s private key

B. Receiver’s public key
C. Sender’s private key
D. Sender’s public key

✔️Answer: B. Receiver’s public key

🧠 Memory Trick
👉 “Public locks 🔒, Private unlocks 🔑”

⚖️FINAL COMPARISON (VERY

IMPORTANT)
Feature Symmetric Asymmetric
Keys One key Two keys
Speed Fast ⚡ Slow 🐢
Security Medium High
 Feature Symmetric Asymmetric
Encryption Same key Public key
Decryption Same key Private key
Usage Bulk data Secure communication
Example AES RSA

🎯 SUPER EXIT EXAM SUMMARY

🔹 Symmetric:

 Same key
 Fast
 AES / DES
 Bulk encryption

🔹 Asymmetric:

 Two keys
 Public encrypt, Private decrypt
 RSA
 Secure communication

If you want next, I can give you:

✔ 20 exit exam MCQs on cryptography
✔ Digital signature + hashing (very important)
✔ One-page final revision sheet for exam night

Just tell me 👍

grammars are considered equivalent if

. When the languages represented by both grammars are the same

To speed up search and edge lengths to compute optimal paths. Explanation: The A* (A-star) search
method is a heuristic search algorithm that is widely used for finding the shortest path in graphs. It
combines the cost to reach a node (g(n)) with a heuristic estimate of the cost to reach the goal from that
node (h(n))

1. Dijkstra's Algorithm (Greedy)

Purpose: Find the shortest path from a source node to all other nodes in a weighted graph.
How it works

1. Start from the source node.

2. Assign distance 0 to source and ∞ to others.
3. Choose the unvisited node with the smallest distance.
4. Update distances of its neighbors.
5. Repeat until all nodes are visited.

Example
A --2-- B
| |
4 1
| |
C --3-- D

Shortest path from A:

 A→B=2
 A→B→D=3
 A→C=4

✅ Used for: GPS navigation, network routing.

2. Prim's Algorithm (Greedy)

Purpose: Find a Minimum Spanning Tree (MST).

MST

A tree that:

 Connects all vertices.

 Has no cycles.
 Has minimum total edge weight.

How it works

1. Start from any vertex.

2. Select the smallest edge connecting the tree to a new vertex.
3. Repeat until all vertices are included.

Example
A--1--B
| /
4 2
| /
C

Choose:

 A-B (1)
 B-C (2)

Total cost = 3

✅ Used for: Network design, cable laying.

3. Kruskal's Algorithm (Greedy)

Purpose: Find a Minimum Spanning Tree (MST).

How it works

1. Sort edges by weight.

2. Pick the smallest edge.
3. Add it if it doesn't create a cycle.
4. Continue until MST is complete.

Example

Edges:

AB=1
BC=2
AC=4

Choose:

 AB=1
 BC=2

Skip AC=4 (creates cycle)

✅ Used for: Road networks, communication networks.

Difference Between Prim and Kruskal

 Prim Kruskal

Starts from a vertex Starts from edges

Grows one tree Builds forest then merges

Better for dense graphs Better for sparse graphs

4. Huffman Coding (Greedy)

Purpose: Data Compression.

Idea

Characters occurring more frequently get shorter codes.

Example

Character Frequency

A 5

B 2

C 1

Possible codes:

A = 0
B = 10
C = 11

Since A occurs most, it gets the shortest code.

✅ Used in ZIP files, JPEG, MP3 compression.

5. Fractional Knapsack (Greedy)

Purpose: Maximize profit when fractions of items can be taken.

Example
Knapsack Capacity = 50

Item Weight Profit

A 10 60

B 20 100

C 30 120

Profit/Weight:

Item Ratio

A 6

B 5

C 4

Take:

 A completely
 B completely
 20/30 of C

Maximum profit obtained.

✅ Used in resource allocation problems.

6. Banker's Algorithm
Purpose: Deadlock Avoidance in Operating Systems.

Idea

Before allocating resources, the OS checks whether the system will remain in a safe state.

If safe → Allocate resource.

If unsafe → Deny request.

Example
Suppose:

 Total printers = 10
 Processes request printers.

Before giving more printers to a process, the OS checks:

"Can all processes still finish eventually?"

If YES → Grant resource.

If NO → Wait.

Key Terms

Safe State

A sequence exists where all processes can complete.

Unsafe State

May lead to deadlock.

Deadlock

Processes wait forever for resources held by each other.

✅ Used for: Deadlock Avoidance.

Exit Exam Quick Table

Algorithm Purpose Type

Dijkstra Shortest Path Greedy

Prim Minimum Spanning Tree Greedy

Kruskal Minimum Spanning Tree Greedy

Huffman Coding Data Compression Greedy

Fractional Knapsack Profit Maximization Greedy

Banker's Algorithm Deadlock Avoidance OS Algorithm

Most Asked MCQs

1. Which algorithm is used for deadlock avoidance?

o ✅ Banker's Algorithm
2. Which algorithm finds the shortest path?
o ✅ Dijkstra's Algorithm
3. Which algorithms find MST?
o ✅ Prim's and Kruskal's Algorithms
4. Which algorithm is used for data compression?
o ✅ Huffman Coding
5. Which knapsack problem uses a greedy approach?
o ✅ Fractional Knapsack
6. Banker's Algorithm checks whether the system is in a ______ state.
o ✅ Safe State

1. N-Queens Problem
Type

✅ Backtracking Algorithm

Purpose

Place N queens on an N × N chessboard so that no two queens attack each other.

A queen can attack:

 Horizontally (row)
 Vertically (column)
 Diagonally

Example: 4-Queens

One valid arrangement:

. Q . .
. . . Q
Q . . .
. . Q .

No two queens share the same row, column, or diagonal.

How It Works

1. Place a queen in the first row.

2. Move to the next row.
3. If a position is safe, place a queen.
4. If no safe position exists, remove the previous queen (backtrack) and try another
position.
5. Continue until all queens are placed.

Exam Questions

N-Queens problem is solved using:

A. Greedy
B. Dynamic Programming
✅ C. Backtracking
D. Divide and Conquer

2. Floyd–Warshall Algorithm
Type

✅ Dynamic Programming

Purpose

Find the shortest paths between all pairs of vertices in a graph.

Key Formula

dist[i][j]=\min(dist[i][j],;dist[i][k]+dist[i][j])

(Conceptually, we compare the current path with a path going through an intermediate vertex
(k).)

Example
Graph:

A --3--> B
B --2--> C
A --10-> C

Direct path:

A → C = 10

Via B:

A → B → C = 3 + 2 = 5

Since 5 < 10:

A → C = 5

Features

✅ Finds shortest path between every pair of nodes

✅ Can handle negative edge weights
❌ Cannot handle negative cycles

Exam Questions

Floyd–Warshall Algorithm is used for:

A. Minimum Spanning Tree

B. Deadlock Avoidance
✅ C. All-Pairs Shortest Path
D. Compression

Quick Comparison
Algorithm Type Purpose
N-Queens Backtracking Place N queens safely
Floyd–Warshall Dynamic Programming All-pairs shortest path
Dijkstra Greedy Single-source shortest path
Prim Greedy Minimum Spanning Tree
 Algorithm Type Purpose
Kruskal Greedy Minimum Spanning Tree
Huffman Greedy Data Compression
Fractional Knapsack Greedy Optimization
Banker's Deadlock Avoidance OS Resource Allocation

Exit Exam Memory Table

 N-Queens → Backtracking
 Floyd–Warshall → Dynamic Programming
 Dijkstra → Greedy
 Prim → Greedy
 Kruskal → Greedy
 Huffman → Greedy
 Fractional Knapsack → Greedy
 Banker's → Deadlock Avoidance ✅

Quation 64

Quation 79 114 121 147

Entity Integrity

. Referential Integrity

Domain Integrity

. Enterprise Integrity

Operation (Singly Linked List) Time Complexity

Insert at beginning O(1)
Insert at end (head only known) O(n)
Insert at end (tail pointer available) O(1)
Delete at beginning O(1)
Search O(n)

Doubly Linked List (Head and Tail Available)

Time Complexity
Operation
Insert at beginning O(1)
Insert at end O(1)
Delete at beginning O(1)
Delete at end O(1)
Doubly Linked List (Head and Tail Available)

Time Complexity
Operation
Search O(n)

A checkpoint is a point in time where the database management system (DBMS) saves all
completed transactions and updates from memory to disk.

constant Folding (Compiler Design)

Constant Folding is an optimization technique used by a compiler where constant expressions

are evaluated at compile time rather than at run time.

Attribute Type Best Parser

Synthesized Attributes (S-attributed SDD) ✅ LR (Bottom-Up)
Inherited Attributes (L-attributed SDD) ✅ LL (Top-Down)
 Disclosure → Someone sees your secret data.
 Modification → Someone changes your data.
 Deception → Someone lies to the system using fake data.

 Interruption → Someone stops the service from working.

Class First Bits Pattern Range

A 0 0xxxxxxx 1–126
B 10 10xxxxxx 128–191
C 110 110xxxxx 192–223
D 1110 1110xxxx Multicast

In DNS (Domain Name System):

 Forward resolution = converting a hostname → IP address

 Reverse (backward) resolution = converting an IP address → hostname

Tool Main Purpose Example Question

Ping Check connectivity “Is server reachable?”
Traceroute Show route path “Where is delay happening?”
Netstat Show active connections “What is using my network?”
Nslookup DNS lookup “What is this domain’s IP?”

 The short-term scheduler (CPU scheduler) selects which process should run next.
 But the selected process cannot run immediately on its own.
👉 The dispatcher is the module that actually gives control of the CPU to that selected process.

Symbol table

Problems Prevented by Concurrency Control

1. Lost Update

A lost update occurs when two transactions update the same data simultaneously, and one
update overwrites the other.

Example:

 Account balance = 1000

 T1 withdraws 200 → balance should be 800
 T2 withdraws 300 → balance should be 700
 If T2's update overwrites T1's update, the final balance becomes 700 instead of 500.

Result: One transaction's update is lost.

2. Dirty Read

A dirty read occurs when a transaction reads data that has been modified by another transaction
but not yet committed.

Example:

 T1 changes salary from 5000 to 6000.

 Before T1 commits, T2 reads the salary as 6000.
 T1 then rolls back the change.

Result: T2 read invalid (dirty) data that never actually existed in the database.

3. Unrepeatable Read

An unrepeatable read occurs when a transaction reads the same data twice and gets different
values because another transaction modified it in between.

Example:

 T1 reads account balance = 1000.

 T2 updates the balance to 1200 and commits.
  T1 reads the balance again and gets 1200.

Result: The same query returns different results within the same transaction.

4. Inconsistent Data (Inconsistent Retrieval)

This occurs when a transaction reads some updated data and some old data during another
transaction's execution.

Example:

 T1 transfers 100 Birr from Account A to Account B.

 T2 reads Account A after the deduction but reads Account B before the addition.

Before transfer:

 A = 1000
 B = 500

After deduction:

 A = 900
 B = 500

T2 reads:

 A = 900
 B = 500

Result: T2 sees an inconsistent state because the transfer is only partially completed.

Summary Table

Problem Meaning

Lost Update One transaction's update is overwritten by another.

Dirty Read Reading uncommitted data.

Unrepeatable Read Same data gives different values within one transaction.

Inconsistent Retrieval Reading a mixture of old and new data.

 Problem Meaning

Concurrency Control ensures that transactions execute safely and that these problems do not
occur, maintaining database consistency and integrity.

Symbol Table
A Symbol Table is a data structure used by a compiler to store information about identifiers
(variables, functions, constants, classes, etc.) used in a program.

It is created during the lexical analysis and syntax analysis phases and used throughout
compilation.

Information Stored in a Symbol Table

For each identifier, the symbol table stores:

 Name of the identifier

 Data type
 Scope (local/global)
 Memory location (address)
 Value (if known)
 Function parameters (for functions)

Example
Source Code
int x = 10;
float y = 5.5;

Symbol Table

Identifier Type Value

x int 10
y float 5.5

Functions of Symbol Table

1. Stores identifier information.
 2. Detects duplicate declarations.
3. Helps in type checking.
4. Assists memory allocation.
5. Supports code generation and optimization.

Example of Error Detection

int x;
int x;

The compiler checks the symbol table and reports:

Error: Variable 'x' already declared.

Implementation of Symbol Table

Common data structures used:

 Hash Table (most common)

 Binary Search Tree (BST)
 Linked List
 Array

Exit Exam Definition

Symbol Table: A data structure maintained by a compiler that stores information about
identifiers such as their names, types, scopes, and memory locations.

Exit Exam MCQ

Which compiler data structure stores information about variables, functions, and
identifiers?

A. Parse Tree
B. Stack
C. Symbol Table
D. Queue

✅ Answer: C. Symbol Table

Quick Memory Tip

Symbol Table = Identifier Database of the Compiler. It keeps track of every variable,
function, and their properties during compilation.

-db algo comp auto

73 What is the extension of ?