Vidyavardhaka College of Engineering

Gokulam III stage, Mysuru – 570 002

Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

Semester – IV
: Design and Analysis
Course Name Course Code : 20CS42
of Algorithms
No. of Lecture Hours /
: 03 CIE Marks : 50
Week
No. of Tutorial / Practical
: 00 SEE Marks : 50
Hours / Week
Total No. of Lecture +
: 40 SEE Duration : 03 Hrs.
Tutorial / Practical Hours
L:T:P : 3:0:0 Credits : 03
Course Overview
Design and Analysis of Algorithms is very important for designing algorithms to solve different
types of problems in the branch of Computer Science and Information Technology. As a
fundamental subject, this course equips the students with theory and hands on with respect to
mathematical analysis of algorithms and problem-solving skills.
Course Learning Objectives (CLO)
 To describe various methods of algorithm analysis
 To explain various computational problem-solving techniques
 To analyse the computational complexity of different algorithms
 To design algorithms using various strategies
TEACHING
MODULES
HOURS
MODULE 1
Introduction: What is an Algorithm? Fundamentals of algorithmic problem
solving, The Analysis Framework, Asymptotic notations and Basic efficiency
classes, Mathematical analysis of Non-recursive algorithms, Mathematical 08
analysis of recursive algorithms.
SLE: Important problem types
Textbook1: Ch. 1.1,1.2,1.3, 2.1,2.2,2.3,2.4
MODULE 2
Divide and Conquer: Recurrence equation for divide and conquer, Binary
search, Mergesort, Quicksort, Multiplication of large integers and Strassen’s
08
Matrix Multiplication, Topological Sort.
SLE: Properties of binary trees
Textbook1: Ch.4.2,5.1,5.2, 5.4 Textbook2: Ch.3.2

5
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

MODULE 3
Greedy Technique: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra's
Algorithm. Optimal Tree problem: Huffman Trees and Codes. Knapsack
08
Problem, Job sequencing with deadlines.
SLE: Heap sort
Textbook 1: Ch. 9.1-9.4 Textbook 2: Ch. 4.3,4.5
MODULE 4
Dynamic Programming: Floyd's Algorithm, The Knapsack problem and
memory functions, Bellman-Ford Algorithm, The Travelling Salesperson
08
problem.
SLE: Warshall’s Algorithm
Text Book 1: Ch. 8.2,8.4 TextBook 2: 5.3,5.4,5.9
MODULE 5
Backtracking, Branch and Bound solution: Backtracking, N-Queens Problem,
subset problem, Assignment problem, Knapsack problem, P, NP and NP-
08
complete problems.
SLE : Graph Coloring
Textbook1: Ch. 11.3 , 12.1, 12.2
Text Books
1. Introduction to the Design and Analysis of Algorithms, Anany Levitin: 3rd Edition,
2017, Pearson.
2. Computer Algorithms/C++, Ellis Horowitz, Satraj Sahni and Rajasekaran, 2nd Edition,
2017, Universities Press.
Reference Books
1. Algorithm Design, John Kleinberg, Eva Tardos, 1st Edition, 2013, Pearson.
2. Algorithms, S. Dasgupta, C.H. Papadimitrou and U. Vazirani, Indian Edition, 2017,
McGraw-Hill Education.
COURSE OUTCOMES (COs)
At the end of the course, students will be able to
CO1 Describe computational solutions to well-known problems
CO2 Apply the appropriate design strategies for problem solving
CO3 Analyze the computational complexity of various algorithms
CO4 Explore various algorithms and design strategies for a given problem

6
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

CO – PO – PSO MAPPING
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO 1 2 1
CO 2 2 3
CO 3 2 2
CO 4 1
Avg. 2 2 1 2 2

7
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

Semester – IV
: Design and Analysis of
Course Name Course Code : 20CS47
Algorithms Laboratory
No. of Lecture Hours /
: 00 CIE Marks : 50
Week
No. of Tutorial / Practical
: 02 SEE Marks : 50
Hours / Week
Total No. of Lecture +
: 12 + 24 = 36 SEE Duration : 03 Hrs.
Tutorial / Practical Hours
L:T:P : 1:0:2 Credits : 02
Course Overview
After the students have gone through a course on discrete structures, where they learn formal
and abstract representations of data and its manipulation, and another course on data structures,
where they learn concrete implementations and usage of such discrete structures, a first course
on algorithm design and analysis should teach the students how to design an efficient algorithm
for a given computational task using one or more of such data structures, analyze performance
of a given algorithm and provide performance guarantees.
Course Learning Objectives (CLO)
 Performance analysis of Algorithms using asymptotic and empirical approaches
 Demonstrate familiarity with algorithms and data structures
 Construct efficient algorithms for common computer engineering design problems
PART – A
1. Sort a given set of elements using the quick sort method and determine the time required to
sort the elements. Repeat the experiment for different values of n, the number of elements in
the 1st to be sorted and plot a graph of the time taken versus n. The elements can be read from
a file or can be generated using the random number generator.
2. 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 and plot a graph of the time taken versus n. The elements can
be read from a file or can be generated using the random number generator.
3. Implement transitive closure using Warshall's algorithm for the given directed graph.
4. From a given source vertex in a weighted connected graph, find shortest paths to other
vertices using Dijkstra’s algorithm.
5. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.
6. Implement 0/1 Knapsack problem using Greedy Technique

20
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

7. Implement 0/1 Knapsack problem using Dynamic Programming.

8. Implement a subset concept for a given set S = {sl, s2,.....,sn} of n positive integers whose sum
is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two
solutions {1, 2, 6} and {1,8}.A suitable message is to be displayed if the given problem
instance doesn't have a solution.
9. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
10. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.
PART – B

Open Ended Enquiry problems

Students have to solve a problem*(either given by the staff or student may come up with their
own problem) using the design techniques such as
1. Divide and Conquer
2. Decrease and Conquer
3. Dynamic Programming
4. Greedy Technique
5. Back Tracking
*The problem may be (not limited to)
1. Finding the maximum and minimum in the given set of elements
2. Sorting
3. To count the number of nodes or leaf nodes in a binary tree.
4. To find the shortest path.
COURSE OUTCOMES (COs)
At the end of the course, students will be able to
Demonstrate the knowledge of algorithms and data-structures corresponding to each
CO1
algorithm design paradigm
Analyze the Performance of various Algorithms using asymptotic and empirical
CO2
approaches
CO3 Design and Develop an algorithm to solve a given problem

Type of Experiment Program-No Weightage

Demonstration 5 10%
Exercise 1,2,3,9 40%
Structured Enquiry 4,6,7,10 40%
Open ended enquiry 8 10%

21
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Department of Computer Science & Engineering
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

CO – PO – PSO MAPPING
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO 1 2 2
CO 2 3 3
CO 3 1 1
CO 4 2 3 1 2
Avg. 2 2 1 2 2

22
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
Semester – III
Course Name : Data Structures Course Code: 20CS32

No. of Lecture Hours / Week : 03 CIE Marks: 50

No. of Tutorial / Practical
: 00 SEE Marks: 50
Hours / Week
Total No. of Lecture + Tutorial
: 40 SEE Duration: 03 hr.
/ Practical Hours
L:T:P : 3:0:0 Credits: 03
Course Overview
In this course, we will study several basic algorithms and data structures and learn how to implement them in
C. Some of the data structures we will encounter include linked lists, stacks, queues, trees, heaps, hash tables
and graphs. We will study and analyse algorithms for searching, traversing trees, hashing, manipulating
priority queues and finding shortest paths in graphs.
Course Learning Objectives (CLOs)
• Understand the foundations of data structure and how different data structures are used for effective
data access and data manipulation
• Investigate various data structures such as stacks, queues, link lists, trees, and graphs
• Understand the context of problem definition and implement a suitable data structure to solve it
Teaching
MODULE Hours
MODULE 1
Introduction: Data structures, pointers and dynamic memory allocation, data abstraction.
Arrays: Dynamically allocated arrays, Sparse matrix and polynomial representation.
String Processing & Pattern matching Algorithms: Naive Pattern Searching, KMP Algorithm. 08
Sorting Techniques : Insertion Sort , Radix Sort
SLE : String Operations
Text Book 1 : Ch.1-1.2,1.4,Ch.2-2.2,2.4,2.5,2.7.3 Text Book 2 : Ch.1-1.4,Ch.3-3.7,Ch. 9-9.3,9.7
MODULE 2
Stacks: Introduction, Array representation, Applications of stacks: Infix to Postfix, Evaluation
of Postfix, Recursion, Tower of Hanoi 08
Queues: Introduction, Circular queues, Deques, Priority queue
SLE: Multiple stacks and queues
Textbook 1: Ch. 3- 3.4,3.6 Textbook 2: Ch. 6-6.1 to 6.3,6.5, 6.7, 6.8, 6.10, 6.12,6.13
MODULE 3
Linked Lists: Introduction, Representation of linked list in memory, traversing and searching
linked list, insertion, deletion from the linked list, header linked list, two-way linked list,
Linked list representation of stacks and queues, Circular linked list 08
SLE: Addition and concatenation of two lists
Textbook 1: Ch.4 - 4.4.4
Textbook 2: Ch. 5 - 5.1 to 5.4, 5.7 to 5.10 Ch.6 – 6.4, 6.11

4
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
MODULE 4
Trees: Introduction, Binary Trees, Binary tree Traversal, Additional binary tree operations,
Threaded Binary trees, Binary search Trees 08
SLE: Expression trees, Heaps
Textbook 1: Ch. 5- 5.1 to 5.5, 5.7
MODULE 5
Trees: Selection Trees, Forest, Representation of Disjoint Sets, Counting binary tree
Efficient Binary Search trees: AVL trees, Red-Black Trees, Splay tree
Graphs: ADT, Elementary graph operations: BFS, DFS 08
Hashing: Introduction, Static Hashing, Dynamic Hashing.
SLE: Optimal Binary Search trees
Textbook 1: Ch. 5 - 5.8 to 5.11, Ch.6 – 6.1 to 6.2 ,Ch.8- 8.1 to 8.3, Ch.10 - 10.2 to 10.4
Textbooks
5. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in C, 2nd Edition, Universities Press,
reprint 2018
6. Seymour Lipschutz, Data Structures Schaum's Outlines, Revised 1st Ed, McGraw Hill, 2014
Reference Books
6. Programming and Data Structure by Jackulin C Salini etal., Ane books publishers, 2019
7. Learning JavaScript data structures and algorithms hone your skills by learning classic data structures by
Loiane Groner, Pack T publishing, 2019
8. Data structures and program design in C by Robert Kruse, Tondo C L, Bruce Leung, Pearson education
publishers, 2017
9. Introduction to Algorithms by Thomas H Cormen, 2nd Edition, MIT Press,2009
Course Outcomes (COs)
At the end of the course, students will be able to
CO1 Explain the fundamentals of basic data structures
CO2 Implement the various data structures and its applications
CO3 Analyze the various operations on data structures
Design appropriate solution by implementing suitable data structure for a given problem in a
CO4
team. (Additional CO - PO9)

CO – PO – PSO Mapping
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO1 2 1
CO2 3 2
CO3 3 1
CO4 2 1
Avg. 2.5 3 2 1.5 1

5
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
Semester – III
Course Name : Data Structures Lab Course Code: 20CS37

No. of Lecture Hours / Week : 01 CIE Marks: 50

No. of Tutorial / Practical
: 02 SEE Marks: 50
Hours / Week
Total No. of Lecture +
: 42 SEE Duration: 03hr.
Tutorial / Practical Hours
L:T:P : 1:0:2 Credits: 02
Course Overview
The laboratory course aims at introducing the concepts of data structure to the students using C. The
students will be able to enhance their analytical and problem-solving skills by implementing suitable data
structure. This course is designed to encourage the students in solving open ended problems
Course Learning Objectives (CLOs)
This laboratory course enables the students to gain practical experience in design, development,
implementation, analysis and evaluation/testing of
● Linear data structures and their applications such as stacks, queues and lists
● Non-linear data structures and their applications such as trees and graphs
● Pattern Matching algorithms
Part A
(Demonstration)
1. Design, Develop and Implement a Program in C for the following operations on Strings
1. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
2. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with REP if PAT
exists in STR. Report suitable messages in case PAT does not exist in STR.
3. Pattern Matching Algorithm: Brute Force
4. Support the program with functions for each of the above operations. Don't use Built-in functions
5. Check the following test cases.
Test Case 1: STR = “VVCE MYSURU”, PAT=” MYSURU”, REP=” KARNATAKA”, OUTPUT=” VVCE
KARNATAKA”
Test Case 2: STR = “COMPUTER SCIENCE”, PAT=” COMPUTER”, REP=” BASIC”, OUTPUT=” BASIC
SCIENCE”
(Demonstration)
2. Design, Develop and Implement a Program in C for the following operations on expression.
a. Read infix expression String (INFIX)
b. Convert the infix expression (INFIX) to a postfix expression using stacks.
c. Evaluate the postfix expression using stacks.
d. Check the following test cases.
Test Case 1: Infix = “(1+ (2-3) *4)”, Postfix=”123-4*+”, Result = -3
Test Case 2: Infix = “4/2-2+3*3-4*2”, Postfix=”42/233*42*-+-”, Result = -1
Note: Program should support for both parenthesized and free parenthesized expressions with the
operators: +, -, *, /, % (Remainder), ^ (Power) and alphanumeric operands.

15
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
(Exercise)
3. Design, Develop and implement menu driven program to simulate processing of batch jobs by a computer
system. The scheduling of these jobs should be handled using a priority queue.
Note:
● The Program should allow users to add or remove items from the queue.
● It should also display current status i.e. the total number of items in the queue. (Exercise)

4. Design, Develop and implement c program using singly linked list for the following scenario
a. There are two linked list A and B containing the following data:
A: 3,7,10,15,16,09,22,17,32 and B: 16,02,09,13,37,08,10,01,28
b. Create a linked list C that contains only those elements that are common in linked list A and B
c. Create a linked list D which contains all elements of A as well as B ensures that there is no repetition of
elements.

(Structured Enquiry)
5. Design, Develop and implement C program for the following operations on doubly linked list.
a. Create doubly linked list of N nodes with integer data by adding each node at the front.
b. Delete the node of a given data if it is found, otherwise display appropriate message.
c. Insert a node to the left of the node whose key value is read as input.
d. Display the contents of the list.

(Exercise)
6. Design, Develop and Implement a menu driven Program in C for the following operations on Binary
Search Tree (BST) of Integers.
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in In-order, preorder, post-Order, zigzag order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Display the height of binary trees
e. Exit

(Structured Enquiry)
7. Design, develop a program in C to implement AVL tree operations.

16
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)
(Structured Enquiry)
8. Design, Develop a program in C to implement various operations on Red-Black Tree.

(Structured Enquiry)
9. Design, Develop and Implement a Program in C for the following operations on Graph (G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using the DFS / BFS method

(Exercise)
10. Given a File of N employee records with a set K of Keys (4-digit) which uniquely determine the records in
file F.
a. Assume that file F is maintained in memory by a Hash Table (HT) of M memory locations with L as the
set of memory addresses (2-digit) of locations in HT.
b. Let the keys in K and addresses in L are Integers. Design and develop a Program in C that uses Hash
Function H: K%L as I (remainder method), and implement hashing techniques to map a given key K to
the address space L.
c. Resolve the collision (if any) using linear probing
Part B
Open ended Problems

1. Design and Develop C program to implement following

a. Shell sort
b. Heap sort
c. Merge sort
d. Quick sort
e. Bucket sort

17
 Vidyavardhaka College of Engineering
Gokulam III stage, Mysuru – 570 002
Autonomous Institute under Visvesvaraya Technological University (VTU)
Accredited by NBA (2020- 2023) & NAAC with ‘A’ Grade (2018 - 2023)

2. Design and Develop C program to implement following search algorithms

a. Jump Search.
b. Interpolation Search.
c. Exponential Search.
d. Sub list Search (Search a linked list in another list) Fibonacci Search.
e. The Ubiquitous Binary Search.

Weightages:
Type of Experiment Program Numbers Weightage
Demonstration 1&2 16%
Exercise 3,4,5 & 10 33.33%
Structured Enquiry 6,7,8,9 33.33%
Open Ended 10%

Course Outcomes (COs)

At the end of the course, students will be able to
CO1 Demonstrate the various data structures and its operations
CO2 Design and Develop C programs to implement data structure and its applications
CO3 Implement searching and sorting algorithms in a collaborative environment

CO – PO – PSO Mapping
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
CO1 2
CO2 2 2 2 2
CO3 2 2
Avg. 2 2 2 2 2 2

18