INSTITUTE VISION

To be an organization with potential for excellence in engineering and management for

the advancement of society and human kind.

INSTITUTE MISSION

To excel in academics, practical engineering, management and to

commence research endeavours.

To prepare students for future opportunities.

To nurture students with social and ethical responsibilities.

VISION OF DEPARTMENT
To create proficient graduates with technical knowledge and social value.

MISSION OF DEPARTMENT
To improvise teaching and learning process through modern tool
usage.

To encourage participation between department and industry

through internships and interactions.

To cater ethical and value based education by addressing social

needs.
This is to certify that Mr. / Ms. __________________________________________________

of Semester ________ Branch ____________ Roll No. _________

has performed and successfully completed all the practicals in the subject of
______________________________________________ for the academic year 2021 to 2022 as
prescribed by University of Mumbai.

DATE :- ____________.

Prof. Shraddha Shrivastava Prof. Shraddha Shrivastava

Practical Incharge Internal Examiner

Prof. Mandar Ganjapurkar ________________________

Head of Department External Examiner

Department of Computer Engineering

Course Lab Name Credit

Name
 CSL401 Analysis of Algorithms 1
Lab

Prerequisite: Basic knowledge of programming and data structure

Lab Objectives:

1 To introduce the methods of designing and analyzing algorithms

2 Design and implement efficient algorithms for a specified application

3 Strengthen the ability to identify and apply the suitable algorithm for the given real-
world problem.

4 Analyze worst-case running time of algorithms and understand fundamental algorithmic

problems.

Lab Outcomes: At the end of the course, the students will be able to

1 To implement various searching and sorting techniques on linear/nonlinear data structures to

solve various computing problem
2 Apply sorting algorithms like quick sort and merge sort for information searching.

3 Demonstrate real world scenarios like resource allocation using knapsack algorithm

4 Apply greedy approach to solve different problems to find optimal solution

5 Analyze the complexities of various algorithms.

6 Compare the complexity of the algorithms for specific problem

Description

Implementation can be in any language.

Suggested Practical List:

Sr Suggested Experiment List

No

1 Introduction

1. Selection sort, Insertion sort

1

2 Divide and Conquer Approach

2. Finding Minimum and Maximum, Merge sort, Quick sort, Binary search
1

3 Greedy Method Approach

 3. Single source shortest path-
1 Dijkstra

Fractional Knapsack problem

Job sequencing with deadlines

Minimum cost spanning trees-Kruskal and Prim’s algorithm

4 Dynamic Programming Approach

4. Single source shortest path- Bellman

1 ford

All pair shortest path- Floyd Warshall

0/1 knapsack

Travelling salesperson problem

Longest common subsequence

5 Backtracking and Branch and bound

5. N-queens problem
1 Sum of subsets

Graph coloring

6 String Matching Algorithms

6. The Naïve string-matching

1 Algorithms The Rabin Karp
algorithm

The Knuth-Morris-Pratt algorithm

Term Work:

Term work should consist of 10 experiments.

Journal must include at least 2 assignments on content of theory and practical of “Analysis of
Algorithms”

The final certification and acceptance of term work ensures that satisfactory performance of
laboratory work and minimum passing marks in term work.

Total 25 Marks (Experiments: 15-marks, Attendance Theory& Practical: 05-marks,

Assignments: 05-marks)

Oral & Practical exam

Based on the entire syllabus of CSC402: Analysis of Algorithms
 Program Outcomes

Engineering Graduates will be able to:

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering
fundamentals, and an engineering specialization to the solution of complex engineering
problems.

2. Problem analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of
mathematics, natural sciences, and engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems

and design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
considerations.

4. Conduct investigations of complex problems: Use research-based knowledge and

research methods including design of experiments, analysis and interpretation of data, and
synthesis of the information to provide valid conclusions.

5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and
modern engineering and IT tools including prediction and modeling to complex engineering
activities with an understanding of the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to
assess societal, health, safety, legal and cultural issues and the consequent responsibilities
relevant to the professional engineering practice.

7. Environment and sustainability: Understand the impact of the professional engineering

solutions in societal and environmental contexts, and demonstrate the knowledge of, and
need for sustainable development.

8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of the engineering practice.

9. Individual and team work: Function effectively as an individual, and as a member or

leader in diverse teams, and in multidisciplinary settings.

10. Communication: Communicate effectively on complex engineering activities with the

engineering community and with society at large, such as, being able to comprehend and
write effective reports and design documentation, make effective presentations, and give and
receive clear instructions.

11. Project management and finance: Demonstrate knowledge and understanding of the
engineering and management principles and apply these to one’s own work, as a member and
leader in a team, to manage projects and in multidisciplinary environments.

12. Life-long learning: Recognize the need for, and have the preparation and ability to
engage in independent and life-long learning in the broadest context of technological change.
 Department of Computer Engineering

Subject: Analysis of Algorithms Lab Class:S.E/Sem IV

CODE LAB OUTCOMES

CSL401.1 To implement various searching and sorting techniques on linear/nonlinear

data structures to solve various computing problem.

CSL401.2 Apply sorting algorithms like quick sort and merge sort for information
searching.

CSL401.3 Demonstrate real world scenarios like resource allocation using knapsack
algorithm

CSL401.4 Apply greedy approach to solve different problems to find optimal solution

CSL401.5 Analyze the complexities of various algorithms.

CSL401.6 Compare the complexity of the algorithms for specific problem

 RUBRICS OF PRACTICAL
Maximum
Rubrics
Marks 15 - 12 12-9 9-6 6-0
Description
Weight

Successful Few errors in

completion Output correct the output Incorrect
Implementation
5 with accurate not precise output
(R1) output (3-2)
(4-3) (2-0)
(5-4)

Understand
Understand
experiment
experiment but Improper No
Understanding and drawn
5 conclusion less conclusion conclusion
correct
(R2) accurate
conclusion (3-2) (2-0)
(4-3)
(5-4)

Submission
Submission Submission
Punctuality and Submission after three
within a after two
discipline 5 after a week weeks or
week weeks
more
(R3) (3-2)
(5-4) (3-2)
(2-0)
 TABLE OF CONTENTS

Date of Date of
Sr. Pg
Name of Experiment Grade Sign
No No
Performance Submission

1. Implement and analyze Insertion sort.

2. Implement and analyze Selection sort.

3. Implement and analyze Merge sort .

4. Implement and analyze Binary search .

5. Implement fractional knapsack problem

using greedy method.

6. A company trying to lay cable in a new

neighborhood. If it is constrained to
bury the cable only along certain paths
(e.g. roads), then there would be a graph
containing the points (e.g. houses)
connected by those paths. Some of the
paths might be more expensive, because
they are longer, or require the cable to
be buried deeper; these paths would be
represented by edges with larger
weights. Write a program to find
minimum spanning tree to get subset of
those paths that has no cycles but still
connects every house: Prim’s and
Kruskal’s algorithm.

7. Implement Single source shortest path

using Greedy Strategy- Dijkstra
algorithm.

8. Implement Job sequencing with

deadlines.

9. Implement single source shortest path

using Dynamic Programming Approach:
 Bellman Ford

10. Implement Travelling salesperson problem

11. Assignment

Total Grade / Marks :-

Avg. marks of Experiments Avg. marks of Assignments

(A) (B) Total Marks

(A+B)

Obtained Out of Obtained Out of

Practical In-charge Date

 EXPERIMENT NO.________

Aim of the Experiment :-

__________________________________________________________
_____

__________________________________________________________
_____

Lab Outcome :-
__________________________________________________________
_____

__________________________________________________________
_____

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________
Practical Incharge
 EXPERIMENT NO.: 1

1. TITLE: INSERTION SORT

2. LEARNING OBJECTIVES:
• To understand the insertion sort method of sorting
3. AIM:
• Sort a given set of n integer elements using Insertion Sort method.

• The elements can be read from a file or can be generated using the
random number generator.
• Demonstrate using C how the sorting method works

4.THEORY :

Insertion sort is a simple sorting algorithm that works similar to the way you sort
playing cards in your hands. The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed at the correct position in
the sorted part.

5.Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements
before. Move the greater elements one position up to make space for the swapped
element.

Example:

Another Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move
one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one
position ahead of their current position.
5, 6, 11, 12, 13

6. PROGRAM:
7. OUTPUT:

8. RESULTS

9. LEARNING OUTCOMES:
Students are able to implement Insertion sort method of sorting which is based on
simple approach.

10. APPLICATION AREAS:

Insertion sort is used when number of elements is small.
Also useful when input array is almost sorted, only few elements are misplaced in
complete big array.

11. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment :-

__________________________________________________________

__________________________________________________________

Lab Outcome :-
__________________________________________________________

__________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 2

1. TITLE: SELECTION SORT

2. LEARNING OBJECTIVES:
● To study and implement selection sort algorithm.
3. AIM:
● To write a program to implement Selection Sort.

Shivajirao S
Jondhale College of
Engineering,
Dombivli (E)
Department of
Computer
Engineering
AOA Lab/ IV 1
Experiment
Number 1
Aim:

Shivajirao S
Jondhale College of
Engineering,
Dombivli (E)
Department of
Computer
Engineering
AOA Lab/ IV 1
Experiment
Number 1
Aim
4.THEORY:
The algorithm divides the input list into two parts: the sublist of items already
sorted,which is built up from left to right at the front (left) of the list, and the sublist
of items remaining to be sorted that occupy the rest of the list. Initially, the sorted
sublist is empty and the unsorted sublist is the entire input list. The algorithm
proceeds byfinding the smallest (or largest, depending on sorting order) element in
the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in
sorted order),and moving the sublist boundaries one element to the right.

5.ALGORITHM

Step 1: For i = 1 to n-1

Step 2: Set min = arr[i]
Step 3: Set position = i
Step 4: For j = i+1 to n-1 repeat:
if (min > arr[j])
Set min = arr[j]
Set position = j
[end of if]
[end of loop]
Step 5: swap a[i] with arr[position]
[end of loop]
Step 6: END
6.PROGRAM

7.OUTPUT:

8.RESULT:

9. LEARNING OUTCOMES:
Students are able to implement Selection sort method of sorting which is based on
simple approach.
10. APPLICATION AREAS:
● The selection sort is used when a small list is to be sorted

● cost of swapping does not matter

● checking of all the elements is compulsory
● cost of writing to a memory matters like in flash memory (number of
writes/swaps is O(n) as compared to O(n2) of bubble sort)

11.REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment :-

__________________________________________________________

__________________________________________________________

Lab Outcome :-
__________________________________________________________
__________________________________________________________

Date of Performance :- ______________________

Date of Submission :- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 3

1. TITLE: MERGE SORT

2. LEARNING OBJECTIVES:
• To understand the merge sort method of sorting which is based on
divide and conquer approach.
3. AIM:
• Sort a given set of n integer elements using Merge Sort method

• The elements can be read from a file or can be generated using the
random number generator.
• Demonstrate using C how the divide-and- conquer method works

4.THEORY:
Merge sort is an application of divide and conquer technique which sorts a given
array by dividing into two halves and sorting each of them recursively and then
merging the two smaller sorted arrays into a single sorted one.

Example:
5.Algorithm:
MERGE(A, p, q,r)
//Merges A[p . . q] and A[q + 1 . .r].
1 n1 ← q − p + 1; n2 ← r − q
2 create array L[1 . . n1 + 1] and R[1 . . n2 + 1]
3 for i ← 1 to n1 do L[i] ← A[p + i − 1]
4 for j ← 1 to n2 do R[ j] ← A[q + j]
5 L[n1 + 1] ← ∞; R[n2 + 1] ← ∞
6 i ← 1, j ← 1
7 for k ← p to r do
8 if L[i] <=R[ j] then A[k] ← L[ j]; i++ ;
9 else A[k] ← R[ j]; j++

MERGE-SORT(A, p,r)
Sorts A[p . .r].
1. if p < r then
2. q ← b(p + 1)/2c
3. MERGE-SORT(A, p, q);
4. MERGE-SORT(A, q + 1,r)
5.MERGE(A, p, q,r);

6.PROGRAM
7.OUTPUT

8. RESULTS

9. LEARNING OUTCOMES:
Students are able to implement merge sort method of sorting which is based on
divide and conquer approach.

10. APPLICATION AREAS:

• Merge Sort provides a quick solution to sort the linked list elements.

• Inversion Count Problem: This is a problem where the degree of sorting of

elements is calculated in a list of array.

11.REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment :-

__________________________________________________________

__________________________________________________________

Lab Outcome :-
__________________________________________________________

__________________________________________________________

Date of Performance :- _________________

Date of Submission :- __________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO. 4

1. TITLE: Binary Search

2. LEARNING OBJECTIVES:
• To understand and apply the binary search algorithm for searching a sorted
list
3. AIM:
• In binary search, on a sorted array of numbers, we divide (decrease) the
array of numbers(search space), conquer the sub problems by recursively
looking at the middle point for our target and splitting until we find our target
the base case condition. Note binary search works on a sorted collection of
elements.
• Demonstrate using C/Java/Python how the divide-and- conquer method works
4. THEORY:
Divide and Conquer is probably the best known general algorithm design technique.
A divide and conquer algorithm works by recursively breaking down a problem into
two or more sub-problems of the same (or related) type, until these become simple
enough to be solved directly. The solutions to the sub-problems are then combined to
give a solution to the original problem.
Given a sorted array arr[] of n elements, write a function to search a given element x
in arr[].
A simple approach is to do a linear search. The time complexity of the above
algorithm is O(n). Another approach to perform the same task is using Binary
Search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in
half. Begin with an interval covering the whole array. If the value of the search key is
less than the item in the middle of the interval, narrow the interval to the lower half.
Otherwise, narrow it to the upper half. Repeatedly check until the value is found or
the interval is empty.

Example :
5. Algorithm:

-- Precondition: S is a sorted list

index binsearch(number n, index low, index high,
const keytype S[], keytype x)
if low ≤ high then
mid = (low + high) / 2
if x = S[mid] then
return mid
elsif x < s[mid] then
return binsearch(n, low, mid-1, S, x)
else
return binsearch(n, mid+1, high, S, x)
else
return 0
end binsearch

6.PROGRAM

7.OUTPUT:

8. RESULTS

9. LEARNING OUTCOMES:
Students are able to implement binary search method of sorting which is based on
divide and conquer approach.

10. APPLICATION AREAS:

● Implementing routing table in router.
● Data compression code.
● Implementation of Expression parsers and expression solvers.
● To solve database problem such as indexing.
● Expression evaluation.

11. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment: -

__________________________________________________________

__________________________________________________________

Lab Outcome:-
__________________________________________________________

__________________________________________________________

Date of Performance:- ______________________

Date of Submission:- _______________________

Implementation Understanding Punctuality & Total Marks

Discipline
(05) (05) (15)
(05)

______________________________________
Practical Incharge
 EXPERIMENT NO.: 5

1. TITLE: FRACTIONAL KNAPSACK PROBLEM

2. LEARNING OBJECTIVES:
• To apply greedy method

• Solve the Fractional Knapsack Problem using Greedy Method

3. AIM:
Implement, the Fractional Knapsack problem using Greedy method.

4. THEORY:
Given a knapsack with maximum capacity W,and a set S consisting of N items.
Each item i has some weight wi and benefit value bi (all wi and W are integer
values)
Problem: How to pack the knapsack to achieve maximum total value of packed
items? i.e.,to find

max∑bisubject to∑wi≤W

i∈T i∈T

● There are N items in the store

● Weight of ith item wi>0wi>0

● Profit for ith item pi>0pi>0 and
● Capacity of the Knapsack is W

The problem is called a “0-1” problem, because each item must be entirely
accepted or rejected .There are different ways to solve 0/1 Knapsack Problem
using Greedy Method.

Here we use profit/weight ratio to solve using greedy method

5. Algorithm:
Greedy Knapsack(m,n)
//p[1..n]and w[1..n] contains the profits and weights respectively of the n objects
//ordered such that p[i]/w[i]>=p[i+1/w[i+1]
//m is the Knapsack size and x[1:n]is the solution vector
{
for i:= 1 to n do x[i] := 0.0; //Initialize x
U := m;
 for i:= 1 to n do x[i] := 0.0;
{
if w[i]>U then break;
x[i] := 1; U := U-w[i]
}
if(i<=n) then x[i] := U/w[i];
}

6. RESULTS & CONCLUSIONS:

7. LEARNING OUTCOMES:
● Students are able to implement fractional knapsack problem using greedy
programming approach

8. APPLICATION AREAS:
● Hard-real time systems-cache memory management, dynamic storage
management.

8. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment:-

__________________________________________________________

__________________________________________________________

Lab Outcome:-
__________________________________________________________

__________________________________________________________

Date of Performance:- ____________________

Date of Submission:- _____________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 6

1. TITLE: PRIM’S AND KRUSKAL'S ALGORITHM

2. LEARNING OBJECTIVES:
• To understand the minimum cost spanning tree.

• To implement minimum cost spanning tree using Kruskal's algorithm.

3. AIM: To find minimum cost spanning tree of a given undirected graph using
Prim’s and Kruskal’s algorithm

4. THEORY:

Kruskal's algorithm finds the minimum spanning tree for a weighted connected graph
G=(V,E) to get an acyclic subgraph with |V|-1 edges for which the sum of edge
weights is the smallest. Consequently the algorithm constructs the minimum
spanning tree as an expanding sequence of subgraphs, which are always acyclic but
are not necessarily connected on the intermediate stages of algorithm.

The algorithm begins by sorting the graph’s edges in non decreasing order of their
weights. Kruskal's algorithm finds the minimum spanning tree for a weighted
connected graph G=(V,E) to Then starting with the empty subgraph, it scans the
sorted list adding the next edge on the list to the current subgraph if such an inclusion
does not create a cycle and simply skipping the edge otherwise.

Prim’s Algorithm is preferred when the graph is dense i.e. when there are large
number of edges in the graph like E = O(V 2) because we do not have to pay much
attention to the cycles by adding an edge as we primarily deal with the vertices in
Prim’s Algorithm.

5.Algorithm:
Kruskal(G,w)
// Kruskal’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G=(V,E)
//Output: ET,the set of edges composing a minimum spanning tree of G
{
Sort E in non decreasing order of the edge weights w(ei1)<=…….>= w(ei |E|))
ET ← ∅ ; ecounter ← 0 //Initialize the set of tree edges and its size
k ← 0 //initialize the number of
processed edges while ecounter <|
V|-1 do
{
k ← k+1
if ET U {eik} is acyclic
ET ← ET U {eik}; ecounter ← ecounter+1
}
return ET
}

Prim(G,w,r)
// Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G=(V,E)
//Output: ET,the set of edges composing a minimum spanning tree of G
{
for each u € G,V
u,key = ∞
u,π = NIL
r.key = 0
Q = G.V
while Q ≠ NULL
u = EXTRACT-MIN(Q)
for each v € G.Adj[u]
if v € Q and w(u,v)<v.key
v. π = u
v,key = w(u,v)
}

6. RESULTS & CONCLUSIONS:

7. APPLICATION AREAS:
• Clustering Analysis

• Traveling Salesman Problem Approximation

6. LEARNING OUTCOMES:
Students are able to implement program to find minimum cost spanning tree using
Kruskal and Prim’s algorithm.

9. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment:-

______________________________________________

__________________________________________________________

Lab Outcome:-
____________________________________________________

__________________________________________________________

Date of Performance:- ______________________

Date of Submission:- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 7

1. TITLE: DIJKSTRA'S ALGORITHM

2. LEARNING OBJECTIVES:
• Learn about Single Shortest Path Problem is to find the distances from source
vertex to all other vertices in a given weighted connected graph((directed or
undirected).
• Learn about Dijkstra’s algorithm for Single Source Shortest Paths Problem.

3. AIM:
Write C/Java/Python programs to Implement Single Source Shortest Paths
problem using Dijkstra’s algorithm.

4. THEORY

Dijkstra’s algorithm finds a shortest path tree from a single source node, by building
a set of nodes that have minimum distance from the source.

The graph has the following:

● vertices, or nodes, denoted in the algorithm by vv or uu;

● weighted edges that connect two nodes: (u,vu,v) denotes an edge,

and w(u,v)w(u,v) denotes its weight. In the diagram on the right, the weight
for each edge is written in gray.
This is done by initializing three values:
● distdist, an array of distances from the source node ss to each node in the
graph, initialized the following way: distdist(ss) = 0; and for all other
nodes vv, distdist(vv) = \infty∞. This is done at the beginning
because as the algorithm proceeds, the distdist from the source to
each node vv in the graph will be recalculated and finalized when the shortest
distance to vv is found
● QQ, a queue of all nodes in the graph. At the end of the algorithm's
progress, QQ will be empty.
● SS, an empty set, to indicate which nodes the algorithm has visited. At the end
of the algorithm's run, SS will contain all the nodes of the graph.

5. Algorithm

1. While QQ is not empty, pop the node vv, that is not already in SS,
from QQ with the smallest distdist (vv). In the first run, source node ss will be
chosen because distdist(ss) was initialized to 0. In the next run, the next node
with the smallest distdist value is chosen.
2. Add node vv to SS, to indicate that vv has been visited
3. Update distdist values of adjacent nodes of the current node vv as follows: for
each new adjacent node uu,

● if distdist (vv) + weight(u,v)weight(u,v) < distdist (uu), there is a new minimal

distance found for uu, so update distdist (uu) to the new minimal distance
value;
● otherwise, no updates are made to distdist (uu).
The algorithm has visited all nodes in the graph and found the smallest distance to
each node. distdist now contains the shortest path tree from source ss.

6. RESULTS & CONCLUSIONS:

7. LEARNING OUTCOMES:
• Students are able to develop program based on Dijkstra’s algorithm for
Single Source Shortest Paths Problem.

9. APPLICATION AREAS:
• Shortest path algorithms are applied to automatically find directions
between physical locations, such as driving directions on web mapping
websites like google maps.
• Other applications include robotics, VLSI design

9. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment:-

______________________________________________

__________________________________________________________

Lab Outcome:-
____________________________________________________

__________________________________________________________

Date of Performance:- ______________________

Date of Submission:- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 8

1. TITLE: Job Sequencing Problem with Deadline

2. LEARNING OBJECTIVES:
• Learn about Job Sequencing Problem with Deadline Problem
3. AIM:
Write C/Java/Python programs to Implement Sequencing Problem with Deadline
Problem.

6. THEORY
This problem consists of n jobs each associated with a deadline and profit and our
objective is to earn maximum profit. We will earn profit only when job is
completed on or before deadline. We assume that each job will take unit time to
complete.

● In this problem we have n jobs j1, j2, … jn each has an associated deadline
d1, d2, … dn and profit p1, p2, ... pn.
● Profit will only be awarded or earned if the job is completed on or before
the deadline.
● We assume that each job takes unit time to complete.

● The objective is to earn maximum profit when only one job can be
scheduled or processed at any given time.

Consider the following 5 jobs and their associated deadline and profit.

index 1 2 3 4 5

JOB j1 j2 j3 j4 j5

DEADLINE 2 1 3 2 1

PROFIT 60 100 20 40 20

Sort the jobs according to their profit in descending order

If two or more jobs are having the same profit then sort them as per their entry in
the job list.

index 1 2 3 4 5

JOB j2 j1 j4 j3 j5

DEADLINE 1 2 2 3 1
 PROFIT 100 60 40 20 20

Find the maximum deadline value

Looking at the jobs we can say the max deadline value is 3.
So, dmax = 3

As dmax = 3 so we will have THREE slots to keep track of free time slots. Set the
time slot status to EMPTY

time slot 1 2 3

status EMPTY EMPTY EMPTY

Total number of jobs is 5.

So we can write n = 5

If we look at job j2, it has a deadline 1. This means we have to complete job j2 in
time slot 1 if we want to earn its profit.

Similarly, if we look at job j1 it has a deadline 2. This means we have to complete

job j1 on or before time slot 2 in order to earn its profit.

Similarly, if we look at job j3 it has a deadline 3. This means we have to complete

job j3 on or before time slot 3 in order to earn its profit.

Our objective is to select jobs that will give us higher profit.

7. Algorithm

for i = 1 to n do
Set k = min(dmax, DEADLINE(i)) //where DEADLINE(i) denotes deadline of
ith job

while k >= 1 do
if timeslot[k] is EMPTY then
timeslot[k] = job(i)
break
endif

Set k = k - 1

endwhile

endfor

7. RESULTS & CONCLUSIONS:

8. LEARNING OUTCOMES:
Students are able to Implement Sequencing Problem with Deadline Problem.

9. REMARKS:
 EXPERIMENT NO.________

Aim of the Experiment:-

______________________________________________

__________________________________________________________

Lab Outcome:-
____________________________________________________

__________________________________________________________

Date of Performance:- ______________________

Date of Submission:- _______________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO.: 9

1. TITLE: BELLMAN FORD'S ALGORITHM

2. LEARNING OBJECTIVES:
• Learn about Single Shortest Path Problem is to find the distances from source
vertex to all other vertices in a given weighted connected graph((directed or
undirected).
• Learn about Bellman Ford’s algorithm for Single Source Shortest Paths
Problem.

3. AIM:
Write C/Java/Python programs to Implement Single Source Shortest Paths
problem using Bellman Ford’s algorithm.

4.THEORY
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the
general case in which edge weights may be negative. Given a weighted, directed
graph G (V, E) with source s and weight function W:E R, the Bellman-Ford
algorithm returns a boolean value indicating whether or not there is a negative-
weight cycle that is reachable from the source. If there is such a cycle, the
algorithm indicates that no solution exists. If there is no such cycle, the algorithm
produces the shortest paths and their weights. The algorithm relaxes edges,
progressively decreasing an estimate :d on the weight of a shortest path from the
source s to each vertex v € V until it achieves the actual shortest-path weight
δ(s,v).The algorithm returns TRUE if and only if the graph contains no negative-
weight cycles that are reachable from the source.

5.Algorithm

Bellman-Ford algorithm(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
d[s] ← 0
for each v ∈ V – {s}
do d[v] ← ∞
for i ← 1 to |V| – 1
do for each edge (u, v) ∈ E
do if d[v] > d[u] + w(u, v)
then d[v] ← d[u] + w(u, v)
for each edge (u, v) ∈ E
do if d[v] > d[u] + w(u, v)
then report that a negative-weight cycle exists
6.PROGRAM:
7.OUTPUT

8. RESULTS
9. LEARNING OUTCOMES:
• Students are able to develop program based on Bellman Ford’s
algorithm for Single Source Shortest Paths Problem.

9.APPLICATION AREAS:
• Shortest path algorithms are applied to automatically find directions
between physical locations, such as driving directions on web mapping
websites like google maps.
• Other applications include robotics, VLSI design

10. REMARKS:

EXPERIMENT NO.________
Aim of the Experiment:-
__________________________________________________________

__________________________________________________________

Lab Outcome:-
__________________________________________________________

__________________________________________________________

Date of Performance:- ___________________

Date of Submission:- ____________________

Implementation Understanding Punctuality & Discipline Total Marks

(05) (05) (05) (15)

______________________________________

Practical Incharge
 EXPERIMENT NO. 10

1. TITLE: Travelling Salesman Problem

2. LEARNING OBJECTIVES:
• To understand the Travelling Salesman Problem.

• To implement Travelling Salesman Problem.

3. AIM: To understand and implement Travelling Salesman Problem

4. THEORY:

In the TSP, given a set of cities and the distance between each pair of cities, a
salesman needs to choose the shortest path to visit every city exactly once and return
to the city from where he started.
Let’s take an example to understand the TSP in more detail:

Here, the nodes represent cities, and the values in each edge denote the distance
between one city to another. Let’s assume a salesman starts the journey from the
city . According to TSP, the salesman needs to travel all the cities exactly once and
get back to the city by choosing the shortest path. Here the shortest path means the
sum of the distance between each city travelled by the salesman, and it should be less
than any other path.
With only cities, the problem already looks quite complex. As the graph in the
example is a complete graph, from each city, the salesman can reach any other cities
in the graph. From each city, the salesman needs to choose a route so that he doesn’t
have to revisit any city, and the total distance travelled should be minimum.

5.Algorithm:
6. RESULTS & CONCLUSIONS:

7.LEARNING OUTCOMES:
Students are able to understand and implement Travelling Salesman Problem

8.REMARKS: