Savitribai Phule Pune University

[Link]. Computer Science (2023)

CS-554-MJP : Lab Course on CS-551-MJ (Design and Analysis of
Algorithms)
No. of Credits: 2 Teaching Scheme Examination Scheme
Theory: 4 Hrs/Week Continuous Evaluation: 15 Marks
End Semester : 35 Marks
Prerequisite
 Basic knowledge of algorithms and programming concepts
 Data Structures and Advanced Data Structures
 Basic Knowledge of Graphs and Algorithms
 Basic knowledge of C/C++/ Java
Objectives
● To design the algorithms
● To learn basic Algorithm Analysis techniques and understand the use of asymptotic
notation
● To Understand different design strategies
● To Understand the use of data structures in improving algorithm performance
● To critically analyze the efficiency of alternative algorithmic
● To understand different algorithm design techniques.
● To provide foundation in algorithm design and analysis
● To develop the ability to understand and design algorithms in the context of space and time
complexity.
Course Outcomes
On Completion of this course, student will be able to -
CO1: Analyze worst-case running times of algorithms using asymptotic analysis.
CO2: Compare between different data structures. Pick an appropriate data structure for a design
situation.
CO3: Ability to design algorithms using standard paradigms like: Greedy, Divide and Conquer,
Dynamic Programming and Backtracking.
CO4: Able to Explain the major graph algorithms and Employ graphs to model engineering
problems, when appropriate.
CO5: Able to Compare between different data structures and pick an appropriate data structure
for a design situation.
Assign Name of Practical Assignment
No.
1 Write programs in C/C++/ Java to sort a list of n numbers in ascending order using
selection sort, insertion sort, heap sort, radix sort. Determine the time required to sort
and compare on basis of time complexity for different values of n.
2 Write a program in C/C++/ Java to sort a given set of elements using the Quick sort
method and determine the time required to sort the elements. Repeat the experiment

SPPU [Link]. Computer Science Syllabus 2023-24 51

 for different values of n, the number of elements in the list to be sorted. The elements
can be read from a file or can be generated using the random number generator.
3 Write a program in C/C++/ Java to implement a Merge Sort algorithm to sort a given
set of elements and determine the time required to sort the elements. Repeat the
experiment for different values of n, the number of elements in the list to be sorted.
The elements can be read from a file or can be generated using the random number
generator.
4 Write a program in C/C++/ Java to implement Strassen‟s Matrix multiplication
5 Write a program in C/C++/ Java to find Minimum Cost Spanning Tree of a given
undirected graph using Kruskal‟s algorithm
6 Write a program in C/C++/ Java to find Minimum Cost Spanning Tree of a given
undirected graph using Prim‟s algorithm
7 Write a program in C/C++/ Java to from a given vertex in a weighted connected
graph, find shortest paths to other vertices using Dijikstra‟s algorithm
8 Write a program in C/C++/ Java to implement Knapsack problems using Greedy
method
9 Write a program in C/C++/ Java to implement optimal binary search tree and also
calculate the best case and worst case complexity.
10 Write a program in C/C++/ Java to implement huffman Code using greedy methods
and also calculate the best case and worst case complexity.
11 Write a program in C/C++/ Java to find Minimum number of multiplications in
Matrix Chain Multiplication
12 Write a Program in C/C++/Java to find only length of Longest Common
Subsequence.
13 Write programs in C/C++/ Java to implement DFS and BFS. Compare the time
complexity
14 Write a program in C/C++/ Java for finding Topological sorting for Directed Acyclic
Graph (DAG)
15 Write a program in C/C++/ Java to determine if a given graph is a Hamiltonian cycle
or not
16 Write a Java Program in C/C++/ Java to implement Traveling Salesman Problem
using nearest neighbor algorithm
17 Write a program in C/C++/ Java a to implement Graph Coloring Algorithm
18 Write a program in C/C++/ Java to implement Sum of Subset by Backtracking
19 Write a program in C/C++/ Java to solve N Queens Problem using Backtracking
20 Write a program in C/C++/ Java to solve 4 Queens Problem using Backtracking
21 Write a program in C/C++/ Java to show board configuration of 4 queens problem
22 Write a program in C/C++/ Java to find out longest common subsequence from the
given strings
23 Write a program in C/C++/ Java to find out live node, E node and dead node from a
given graph
24 Write a program in C/C++/ Java to find out solution for travelling salesman problem
using LCBB from a given matrix.
25 Write a program in C/C++/ Java to find out solution for 0/1 knapsack problem

SPPU [Link]. Computer Science Syllabus 2023-24 52