UNIT-IV

FILL IN THE BLANKS

1. Dynamic Programming is a method used to solve problems by breaking them into
__________ sub-problems.

Answer: overlapping

2. In Dynamic Programming, the sub-problems are solved __________ and their results
are stored to avoid redundant computation.

Answer: once

3. The two main approaches used in Dynamic Programming are __________ and
__________.

Answer: top-down, bottom-up

4. The top-down approach in Dynamic Programming is also known as __________.

Answer: memorization

5. The bottom-up approach in Dynamic Programming is also known as __________.

Answer: tabulation

6. The problem of finding the shortest path in a graph can be solved using __________
algorithm, which is based on Dynamic Programming.

Answer: Floyd-Warshall

7. In the Knapsack Problem, Dynamic Programming helps in choosing the best

combination of items to maximize __________ under a weight constraint.

Answer: profit (or value)

8. The key principle behind Dynamic Programming is known as __________.

Answer: optimal substructure

9. A problem is suitable for Dynamic Programming if it exhibits both __________ and

__________ properties.

Answer: overlapping sub-problems, optimal substructure

10. In Dynamic Programming, storing previously computed results is called __________.

Answer: caching (or memoization)

 11.The Dynamic Programming technique is more efficient than recursion when the problem
has __________ sub-problems.

Answer: overlapping

12. The __________ algorithm uses Dynamic Programming to find the longest common
subsequence between two strings.

Answer: LCS (Longest Common Subsequence)

13. Bellman-Ford algorithm, used for finding shortest paths, is an example of

__________ Programming.

Answer: Dynamic

14.__________ is a common optimization technique used to reduce space complexity in

Dynamic Programming.

Answer: Space optimization

15. The Time Complexity of a Dynamic Programming solution is often

__________ than that of a brute-force recursive solution.

Answer: lower (or better)

CHOOSE THE CORRECT ANSWERS:

1. Dynamic Programming is primarily used to solve problems that exhibit:

A) Greedy structure
B) Divide and conquer only
C) Optimal substructure and overlapping sub-problems
D) Random inputs

Correct Answer: C) Optimal substructure and overlapping sub-problems

2. What is the main advantage of using Dynamic Programming over

recursion?

A) Less memory usage

B) Simplifies code
C) Avoids redundant computations
D) No need to store results

Correct Answer: C) Avoids redundant computations

3. Which of the following problems can be solved using Dynamic
Programming?

A) Binary Search
B) Merge Sort
C) Knapsack Problem
D) Quick Sort

Correct Answer: C) Knapsack Problem

4. In Dynamic Programming, the top-down approach is known as:

A) Tabulation
B) Recursion
C) Memoization
D) Iteration

Correct Answer: C) Memoization

5. The bottom-up approach in Dynamic Programming is referred to as:

A) Backtracking
B) Tabulation
C) Memoization
D) Greedy approach

Correct Answer: B) Tabulation

6. Which of these algorithms is based on Dynamic Programming?

A) Prim's Algorithm
B) Dijkstra's Algorithm
C) Floyd-Warshall Algorithm
D) Kruskal's Algorithm

Correct Answer: C) Floyd-Warshall Algorithm

7. The principle that a problem’s optimal solution contains the optimal

solution of its sub-problems is called:

A) Divide and Conquer

B) Greedy choice
C) Optimal Substructure
D) Memoization

Correct Answer: C) Optimal Substructure

8. In Dynamic Programming, the technique of storing intermediate results is
called:

A) Brute-force
B) Memoization
C) Tabulation
D) Recursion

Correct Answer: B) Memoization

9. What is the time complexity of a basic Dynamic Programming solution for

the 0/1 Knapsack Problem?

A) O(n log n)
B) O(n^2)
C) O(n * W), where n = number of items, W = capacity
D) O(W^n)

Correct Answer: C) O(n * W), where n = number of items, W = capacity

10. Which of the following problems does NOT typically require Dynamic
Programming?

A) Longest Common Subsequence

B) Matrix Chain Multiplication
C) Fibonacci Series
D) Binary Search

Correct Answer: D) Binary Search

11. Which of the following is an example of a problem that exhibits

overlapping sub-problems?

A) Merge Sort
B) Binary Search
C) Fibonacci Sequence
D) Quick Sort

Correct Answer: C) Fibonacci Sequence

12. Which of the following is NOT a characteristic of Dynamic Programming?

A) Solving sub-problems independently

B) Storing solutions to sub-problems
C) Reusing stored results
D) Breaking problems into overlapping sub-problems

Correct Answer: A) Solving sub-problems independently

13. What is the purpose of using a table (array or matrix) in Dynamic
Programming?

A) To reduce code complexity

B) To store the final result only
C) To store solutions of sub-problems
D) To improve recursion speed

Correct Answer: C) To store solutions of sub-problems

14. Which of the following algorithms solves the Longest Increasing

Subsequence problem using Dynamic Programming?

A) Bellman-Ford
B) Kadane’s Algorithm
C) Patience Sorting
D) LIS using O(n²) DP solution

Correct Answer: D) LIS using O(n²) DP solution

15. In the tabulation method, computation is done in a:

A) Depth-First manner
B) Bottom-Up manner
C) Top-Down manner
D) Randomized order

Correct Answer: B) Bottom-Up manner

16. Which type of programming technique is Dynamic Programming most

closely related to?

A) Divide and Conquer

B) Greedy
C) Backtracking
D) Brute Force

Correct Answer: A) Divide and Conquer

17. In the context of Dynamic Programming, what does “overlapping sub-

problems” mean?

A) Sub-problems are identical and solved multiple times

B) Sub-problems are totally different
C) Problems do not share any part
D) Sub-problems appear only once

Correct Answer: A) Sub-problems are identical and solved multiple times

18. What is the space complexity of the standard Dynamic Programming
solution to the Fibonacci problem (using an array)?

A) O(1)
B) O(n)
C) O(log n)
D) O(n²)

Correct Answer: B) O(n)

19. Which of the following is solved using Dynamic Programming and not a
greedy algorithm?

A) Activity Selection
B) Fractional Knapsack
C) 0/1 Knapsack
D) Huffman Coding

Correct Answer: C) 0/1 Knapsack

20. Which of the following Dynamic Programming problems involves matrix

multiplication?

A) Bellman-Ford Algorithm
B) Matrix Chain Multiplication
C) Longest Common Substring
D) Edit Distance

Correct Answer: B) Matrix Chain Multiplication

LONG QUESTION & ANSWERS:

4.1 Dynamic Programming: Introduction

1Q) What is Dynamic Programming? Explain its concept, characteristics, and

how it differs from other problem-solving approaches. Also, provide examples
of problems where Dynamic Programming is applied.

Dynamic Programming (DP) is a powerful algorithmic technique used for solving complex problems
by breaking them down into simpler sub-problems, solving each of those only once, and storing
their solutions – typically using a table (array or matrix) to avoid re-computation. It is particularly
useful when a problem has overlapping sub-problems and optimal substructure.

The term “dynamic programming” was coined by Richard Bellman in the 1950s. He developed it as a
method for solving multistage decision problems efficiently.
Key Concepts of Dynamic Programming:

1. Overlapping Sub-problems:
o Problems can be broken down into sub-problems that are reused several times.
o Example: In computing Fibonacci numbers, F(5) requires F(4) and F(3), and F(4)
again requires F(3) and F(2) – F(3) appears multiple times.
2. Optimal Substructure:
o The optimal solution to a problem contains within it the optimal solution to its sub-
problems.
o Example: In the shortest path problem, the shortest path from node A to C via B is
made up of the shortest paths from A to B and B to C.
3. Memoization (Top-Down Approach):
o Recursively solves sub-problems and stores results to avoid duplicate work.
o Uses a hash map or array to cache results of function calls.
4. Tabulation (Bottom-Up Approach):
o Solves all related sub-problems first, then combines them to solve the overall
problem.
o Uses a table to iteratively build solutions from smallest sub-problems.

Why Use Dynamic Programming?

 To improve efficiency of recursive algorithms by avoiding repeated work.

 To reduce time complexity of exponential problems to polynomial time.
 To make previously unsolvable problems feasible due to time or space constraints.

Examples of Problems Solved by Dynamic Programming:

1. Fibonacci Sequence
o Recursive solution: exponential time
o DP solution: O(n) time with memoization or tabulation
2. 0/1 Knapsack Problem
o Optimization problem: maximize value without exceeding weight capacity
 o Solved using a 2D DP table
3. Longest Common Subsequence (LCS)
o Find the longest sequence common to two strings
o DP builds a matrix of subproblem solutions
4. Matrix Chain Multiplication
o Determine the most efficient way to multiply a chain of matrices
o Uses DP to avoid redundant computations
5. Edit Distance (Levenshtein Distance)
o Minimum number of operations to convert one string into another
o Solved using a 2D table (tabulation)
6. Rod Cutting Problem
o Determine maximum revenue by cutting and selling rod pieces
o Solved using top-down or bottom-up DP
7. Floyd-Warshall Algorithm
o All-pairs shortest path in a graph
o Dynamic Programming-based graph algorithm

Advantages of Dynamic Programming:

 Saves computation time by storing intermediate results

 Simplifies complex recursive problems
 Reduces time complexity dramatically
 Guarantees optimal solutions (when applicable)

Disadvantages of Dynamic Programming:

 Can consume significant memory (especially in 2D problems)

 Requires proper problem formulation (not all problems can be approached with DP)
 Sometimes more complex to implement than greedy or recursive solutions

2Q) What are the main characteristics of problems that can be solved using Dynamic
Programming? Explain with examples.

To effectively apply Dynamic Programming (DP), a problem must exhibit two key properties:

1. Overlapping Sub-Problems:

This means the problem can be broken down into smaller sub-problems which are reused several
times. Instead of solving the same sub-problems repeatedly, DP solves them once and stores the
results.

Example:
In the Fibonacci sequence, F(n) = F(n-1) + F(n-2). Both F(n-1) and F(n-2) are used in
future calculations multiple times. By storing their results, we avoid redundant calculations.

2. Optimal Substructure:
A problem exhibits optimal substructure if the optimal solution to the entire problem contains
optimal solutions to its sub-problems.

Example:
In the shortest path problem, if the shortest path from node A to D goes through B and C, then the
path from A to B, B to C, and C to D must all be the shortest paths themselves.

3Q) Differentiate between Memoization and Tabulation in Dynamic Programming.

Answer:

Memoization and Tabulation are two different ways to implement Dynamic Programming.

Memoization (Top-Down):

 Solves the problem recursively.

 Stores results of expensive function calls.
 Uses recursion and a cache (usually a hash table or array).
 Sub-problems are solved on-demand (only when needed).

Tabulation (Bottom-Up):

 Solves the problem iteratively.

 Starts from the base case and builds up the solution.
 Uses a table (array or matrix) to store results.
 Sub-problems are solved before they are needed.
4Q) Explain the steps involved in designing a Dynamic Programming algorithm.

Answer:

Designing a Dynamic Programming algorithm involves several well-structured steps:

1. Identify the Problem Type

Check whether the problem has:

 Overlapping Sub-Problems
 Optimal Substructure

2. Define Sub-Problems

Break the main problem into smaller, manageable sub-problems. Decide what parameters change
and what values must be calculated.
Example:
In LCS (Longest Common Subsequence), the sub-problem is:
LCS(i, j) = LCS of first i characters of string A and first j characters of
string

3. Recurrence Relation

Formulate the recurrence (recursive) relation based on the problem's rules.

Example (LCS):
If A[i] == B[j]:
LCS(i, j) = 1 + LCS(i-1, j-1)
Else:
LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

4. Choose Memoization or Tabulation

Decide between:

 Memoization for simpler recursive problems

 Tabulation for better performance or memory usage

5. Initialize Base Cases

Set up initial values in the DP table or cache.

Example:
In LCS, LCS(0, j) = 0 and LCS(i, 0) = 0

6. Compute the Result

Either recursively compute the value using memoization or fill the table iteratively in tabulation.

7. (Optional) Trace Back

For optimization problems like LCS, you may also trace back through the table to find the actual
sequence or path.

4.2 Applications of Dynamic Programming

5Q) What are the real-world applications of Dynamic Programming?
Explain with examples and use cases across different fields.
Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization and
decision-making problems efficiently. It is widely used in various fields including computer science,
operations research, economics, biology, and artificial intelligence.
The main advantage of dynamic programming is its ability to solve problems that would otherwise
have exponential time complexity by breaking them into smaller, overlapping sub-problems and
solving each only once. Let's explore some key applications of Dynamic Programming with detailed
explanations:

1. 0/1 Knapsack Problem

Field of Application:

 Logistics
 Investment Portfolio Selection
 Inventory Management

Use Case:

A company has a limited-capacity truck and a list of goods, each with a weight and profit. The goal is
to choose the items that maximize total profit without exceeding the truck's capacity.

How DP is used:

Dynamic programming solves this by creating a 2D table, where each cell represents the best value
achievable with a given weight capacity and number of items. This avoids recalculating the same
combinations repeatedly.

2. Longest Common Subsequence (LCS)

Field of Application:

 Bioinformatics
 File comparison tools
 Version control systems (e.g., Git)

Use Case:

In bioinformatics, researchers compare DNA or protein sequences to find similarities. In version

control, finding differences between two files relies on identifying the LCS.

How DP is used:

The LCS is found by building a DP matrix that compares characters from two sequences. This helps
identify common subsequences in O(m × n) time.

3. Matrix Chain Multiplication

Field of Application:

 Compiler Optimization
  Mathematical Computation Systems
 Computer Graphics

Use Case:

When multiplying a chain of matrices, the order of multiplication can affect the number of
operations. The goal is to find the most efficient order of multiplications.

How DP is used:

DP helps find the minimum number of scalar multiplications needed. The solution involves
partitioning the problem and solving subproblems optimally.

4. Shortest Path Algorithms (Floyd-Warshall)

Field of Application:

 Network Routing
 Urban Transportation Systems
 Game AI Pathfinding

Use Case:

In computer networks or GPS systems, finding the shortest path between all pairs of nodes or cities
is essential for routing efficiency.

How DP is used:

Floyd-Warshall uses DP to iteratively improve estimates of shortest paths by considering

intermediate nodes. It has a time complexity of O(V³).

5. Edit Distance (Levenshtein Distance)

Field of Application:

 Natural Language Processing (NLP)

 Spell Checkers
 Plagiarism Detection

Use Case:

Determining how similar two strings are by calculating the minimum number of insertions, deletions,
or substitutions required to transform one into another.

How DP is used:

A DP table is built where each cell represents the minimum edit operations required up to that
character in both strings.
 6. Rod Cutting Problem

Field of Application:

 Revenue Optimization
 Manufacturing
 Pricing Strategy

Use Case:

A company wants to maximize revenue by cutting a rod into different lengths with assigned prices.

How DP is used:

DP considers all possible ways to cut the rod and stores intermediate results to avoid recalculations.

7. Coin Change Problem

Field of Application:

 Finance and Currency Systems

 Vending Machine Algorithms
 E-Wallet Systems

Use Case:

Given a set of coin denominations, determine the minimum number of coins needed to make a
given amount.

How DP is used:

DP builds a solution using previously computed answers to smaller amounts, ensuring the minimum
number of coins is used.

8. Decision-Making in AI (Markov Decision Processes)

Field of Application:

 Artificial Intelligence
 Robotics
 Game Theory

Use Case:

An AI robot navigating a grid must decide the optimal action at each step to reach the goal
efficiently.
How DP is used:

Dynamic Programming helps in policy iteration and value iteration to compute the best long-term
strategy.

9. Resource Allocation Problems

Field of Application:

 Operations Research
 Project Management
 Economics

Use Case:

Allocating a fixed budget across various projects to maximize total return or minimize cost.

How DP is used:

By dividing the total budget into smaller units, DP finds the optimal way to allocate resources across
multiple tasks.

10. Game Development (Pathfinding Algorithms)

Field of Application:

 Game Development
 Robotics Navigation
 Maze Solving Algorithms

Use Case:

Finding the shortest or safest route for a character or agent in a game map.

How DP is used:

Algorithms like A* or Dijkstra's with DP components are used to store and reuse path values.

4.3 Solution of Linear Programming Problem through Dynamic

Programming.

6Q) How can Linear Programming problems be solved using Dynamic

Programming? Explain the approach in detail with an example.
Steps to Solve LP using Dynamic Programming:

1. Identify Stages:

Break the decision-making process into stages. Each stage represents a variable in the LP model.

2. Define State Variables:

State variables represent the condition or resource left after a decision at a given stage (e.g.,
remaining capacity, remaining budget).

3. Determine Decision Variables:

These are the choices made at each stage (e.g., how much of a product to produce using remaining
resources).

4. Recursive Relation (Bellman Equation):

Establish a function that relates the current stage to the next using a recurrence relation.

5. Boundary Conditions:

Define the base cases or terminal conditions of the recursion.

6. Solve Using Forward or Backward Recursion:

Compute the optimal value using either bottom-up (tabulation) or top-down (memoization)
approaches.
When to Use DP for LP:

Dynamic Programming is preferred in LP problems where:

 The number of variables is small

 The problem has a multistage structure
 Integer or discrete decisions are required
 Recursive or sequential decision-making is involved

Real-World Examples:

1. Resource Allocation in Projects:

Where a limited budget must be allocated over multiple projects with varying returns.
2. Machine Scheduling:
Where a machine can perform different jobs in stages, and you want to maximize output or
minimize idle time.
3. Investment Portfolio Selection:
Allocate a fixed budget across investment options (stocks, funds) to maximize returns.
Advantages of Using DP in LP Problems:

 Handles multistage decisions naturally

 Allows for easier handling of integer and discrete values
 Easily adapts to constraints like "only one choice allowed per stage"

Limitations:

 Not efficient for large-scale LP problems

 Requires clear stage-based structure
 Needs discrete or finite decision sets for practical computation

7Q) Why is Dynamic Programming not commonly used to solve general

Linear Programming problems?

Answer:

Dynamic Programming (DP) is a powerful method for solving optimization problems, but it
is not typically used for general Linear Programming (LP) because of several limitations:

1. Inefficiency for Large-Scale Problems:

o LP problems with many variables and constraints are best handled by
specialized methods like the Simplex or Interior Point Methods. DP tends to
have a higher time and space complexity due to the exponential growth of
state spaces.
2. Requirement of Discrete Decision Variables:
o DP works best when decision variables are integers or discrete. However,
most LP models assume continuous decision variables, which are better
suited to traditional LP techniques.
3. Lack of Matrix-Based Structure:
o LP methods like Simplex are matrix-based and highly optimized. DP does not
naturally fit into matrix-based computations unless the problem is structured to
do so.
4. Recursive Complexity:
o As the number of stages or states increases, the recursion becomes deeply
nested and complex, leading to computational inefficiency.

Despite these limitations, DP is preferred in specific structured LP problems, such as

resource allocation, inventory planning, and stage-based decisions.

8Q) What type of Linear Programming problems are best suited for Dynamic
Programming approaches?

Answer:

Dynamic Programming is ideal for LP problems that can be structured into a sequence of
decisions, typically with the following characteristics:
 1. Multistage Nature:
o The problem can be broken down into stages, where each stage involves
making a decision based on previous outcomes.
2. Recursive Structure:
o The optimal solution at any stage depends only on the state resulting from the
previous decision — this is known as the optimal substructure property.
3. Integer or Discrete Variables:
o Problems where variables take on discrete values, such as 0, 1, 2, … (e.g.,
items in a knapsack, investment units, number of products), are better suited
for DP.
4. Resource Allocation Problems:
o Examples include capital budgeting, project selection, or knapsack-type
problems where a fixed resource must be divided among competing activities.
5. Sequential or Time-based Decisions:
o Problems involving inventory planning, maintenance scheduling, or stage-
wise production over time are perfect for DP approaches.

9Q) Compare the Dynamic Programming approach with the Simplex Method in solving LP problems.

So while the Simplex Method dominates in solving general LP problems efficiently,

Dynamic Programming offers better insights for specific structured or integer-based
decision problems.

10Q) Explain with an example how Dynamic Programming helps in multi-

period resource allocation problems.
Answer:

Example Scenario:
A company has a $10 million budget to invest over 3 years in 2 projects. The return depends
on the investment made each year.

Stage-wise breakdown:

 Stage 1 (Year 1): Decide how much to invest in Project A and Project B.
 Stage 2 (Year 2): Reinvest profits or allocate unused budget.
 Stage 3 (Year 3): Final investments based on prior returns.

Dynamic Programming Approach:

 State Variable: Remaining budget or accumulated return.

 Decision Variables: Investment in Project A or B each year.

where s' is the new state after the decision, and R is the return.

Outcome:
DP calculates the maximum cumulative return by recursively evaluating investment
combinations at each stage, storing the best outcomes at each state.

11Q) What are the limitations of solving LP problems using Dynamic

Programming?

Answer:

Some key limitations include:

1. High Computational Complexity:

The number of states and stages can grow rapidly, making DP computationally
expensive for problems with many variables.
2. Storage Requirements:
DP needs to store results of subproblems, which can cause memory overflow in large
LP models.
3. Problem Structuring Requirement:
Not all LP problems can be structured into stages. Those without a clear recursive
structure are not suitable for DP.
4. Scalability Issues:
Solving large-scale LP problems with DP becomes impractical as the number of
stages and states increases.
 5. Floating Point and Precision Issues:
When dealing with fractional variables, especially in continuous LP, DP may face
numerical precision errors.

Despite these limitations, DP remains invaluable in niche areas such as inventory control,
multistage decision-making, and resource management.

4.4 Basics of Queuing theory.

12Q) What is Queuing Theory? Explain its basic components, assumptions, and
applications in real life.

Queuing Theory is the mathematical study of waiting lines, or queues. It is a branch of

operations research that focuses on analyzing and predicting queue behavior using models
based on probability theory and statistics. The objective is to determine the optimal service
process and reduce waiting time, service costs, or congestion.

Basic Components of a Queuing System:

1. Arrival Process (Input):

o Describes how customers arrive at the queue.
o Often modeled using a Poisson distribution for random arrivals.
o Rate of arrival is denoted by λ (lambda).
2. Service Mechanism:
o Describes how customers are served.
o Service times may follow exponential distribution.
o Service rate is denoted by μ (mu).
3. Number of Servers (Channels):
o Can be a single server or multiple servers.
o Affects how quickly the queue moves.
4. Queue Discipline:
o Rule that determines the order of service.
o Common disciplines include:
 FIFO (First In First Out)
 LIFO (Last In First Out)
 SIRO (Service in Random Order)
 Priority Queuing
5. System Capacity:
o Total number of customers that can be in the system (both in queue and in
service).
o Can be finite or infinite.
6. Customer Behavior:
o Includes phenomena like balking (refusal to enter a queue), reneging (leaving
after joining), or jockeying (switching queues).

Basic Assumptions of Queuing Models:

 Arrivals are independent and follow a known distribution (commonly Poisson).

  Service times are independent and identically distributed (often exponential).
 The system follows a known queue discipline.
 Infinite population size (customers).
 Queue length may be infinite unless stated otherwise.

Kendall's Notation (for Queue Models):

The standard form is A/S/c/K/N/D, where:

 A = Arrival time distribution (e.g., M for Markovian/Poisson)

 S = Service time distribution (e.g., M for exponential)
 c = Number of servers
 K = Capacity of the system (optional)
 N = Population size (optional)
 D = Service discipline (optional)

Example: M/M/1 = Poisson arrivals, exponential service time, 1 server

Applications of Queuing Theory:

1. Telecommunications:
o Managing data traffic in networks, call centers, and internet service providers.
2. Banking and Retail:
o Reducing customer wait times, optimizing the number of tellers or checkout
lanes.
3. Healthcare:
o Scheduling in hospitals and clinics to minimize patient waiting time.
4. Manufacturing:
o Assembly lines and machine servicing processes.
5. Transportation:
o Managing queues at toll booths, airports, or public transport systems.
6. IT Services:
o Resource allocation in cloud computing, load balancing in web servers.

13Q) Explain the different types of Queuing Models. Highlight their

significance with examples.
Queuing models are classified based on the arrival and service patterns, number of servers,
system capacity, and population size. The most widely used classification system is
Kendall’s Notation.

1. M/M/1 Queue:

 Description: Poisson arrivals, exponential service times, 1 server.

 Characteristics:
 o Infinite queue length and population.
o FIFO discipline.
 Example: A single cashier at a supermarket.
 Performance Metrics:

2. M/M/c Queue:

 Description: Multiple servers (c), Poisson arrivals, exponential service.

 Example: Multiple tellers in a bank or agents in a call center.
 Usage: When service demand is high and multiple channels are needed.

3. M/M/1/K Queue:

 Description: Single server, finite capacity (K), Poisson arrivals.

 Example: Limited seating in a restaurant or finite parking spots.

4. M/G/1 Queue:

 Description: Poisson arrivals, general service time distribution, 1 server.

 Significance: Useful when service times do not follow an exponential distribution.
 Example: Help desk where time to resolve issues varies significantly.

5. G/G/1 Queue:

 Description: General arrival and service times, single server.

 Significance: The most flexible and complex model, but harder to analyze.
 Example: Highly variable systems like job processing in tech support.

6. Priority Queues:

 Description: Customers are served based on priority levels.

 Example: Emergency patients in hospitals or VIP customers in service centers.