GANPAT UNIVERSITY

FACULTY OF ENGINEERING & TECHNOLOGY

Programme Bachelor of Technology Branch/Spec. Computer Engineering,
Information Technology,
Computer Engineering (Artificial
Intelligence)
Semester IV Version 2.0.0.1
Effective from Academic Year 2023-24 Effective for the Batch admitted in July 2022
Course Code 2CEIT402 Course Name Design and Analysis of Algorithms
Teaching Scheme Examination Scheme (Marks)
(Per week) Lecture (DT) Practical (Lab.) Total CE SEE Total
L TU P TW
Credit 3 0 1 - 4 Theory 40 60 100
Hours 3 0 2 - 5 Practical 30 20 50
Pre-requisites
Knowledge of basic programming and data structures.
Course Outcomes
On successful completion of the course, the students will be able to:
CO1 determine the best algorithm out of various alternatives.
CO2 demonstrate various problems on divide and conquer, greedy and dynamic programming.
CO3 compute the time and space requirements for various algorithms and represent it using various
mathematical notations and recurrence relations.
CO4 analyse the performance of the algorithms for the best, average and worst case.
CO5 develop various algorithms for the same problem using different classes of problems.
Theory Syllabus
Unit Content Hrs.
1 Introduction: 02
Definition and characteristics of an algorithm, problems & instances, best, average and worst-
case analysis, need to look for efficiency
2 Analysis of Algorithms: 07
Performance analysis (time & space complexity), Growth of functions, asymptotic notations
(Big-oh, small-oh, Big Omega, little Omega and Theta), Sorting Algorithms and analysis
(Bubble sort, Selection sort, Insertion sort), Sorting in linear time: Radix sort and Counting
sort
3 Solving Recurrences: 09
Iteration method, homogeneous recurrences, inhomogeneous recurrences, change of variable,
recurrence trees, master method & master theorem
4 Divide and Conquer: 06
Characteristics, the general template, applications: binary search, merge sort, quick sort,
randomized quick sort, counting inversions, min-max problem
5 Graph Algorithms: 04
Depth-first search, breadth-first search, topological ordering & sorting, backtracking,
applications of backtracking, knapsack problem, graph colouring problem, branch & bound,
application: the assignment problem
6 Greedy Algorithms: 07
General characteristics of greedy algorithms and examples, applications: making change
problem, Kruskal’s and Prim’s algorithms, shortest path problem, knapsack problem,
scheduling problem, Huffman coding, optimal merge pattern
7 Dynamic Programming: 07
General characteristics and examples, Fibonacci sequence, all pairs shortest path problem,
subset sum problem, longest common subsequence problem, principle of optimality,
optimal binary search tree applications: binomial coefficients, making change, knapsack
problem, chained matrix multiplication, bellman ford algorithm.
8 Computational Complexity: 03
Introduction, information-theoretic arguments: complexity and sorting, complexity and
algorithmic, introduction to NP completeness, the classes P and NP, polynomial reductions,
NP complete problems
Practical Content
Practical, assignments and tutorials are based on the syllabus.
Text Books
1 Introduction to Algorithms by Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford
Stein, MIT Press/McGraw-Hill.
2 Fundamentals of Computer Algorithms by Ellis Horowitz, SartajSahni ,SanguthevarRajasekaran,
Computer Science Press
Reference Books
1 Fundamentals of Algorithms by Brassard & Bratley, Prentice Hall of India
2 Ellis Horowitz, SartajSahni, Fundamentals of computer algorithms, Computer Science Press
3 Algorithm Design: Foundations, Analysis and Internet Examples by Michael T Goodrich and
Roberto Tamassia, Wiley
4 Algorithm Design by Jon Kleinberg and ÉvaTardos, Pearson
ICT/MOOCs Reference
1 https://onlinecourses.nptel.ac.in/noc18_cs20/
2 https://nptel.ac.in/courses/106101060/
3 https://nptel.ac.in/courses/106106131/

Mapping of CO with PO and PSO:

P P P P P P
P P P P P P P P P
O O O S S S
O O O O O O O O O
1 1 1 O O O
1 2 3 4 5 6 7 8 9
0 1 2 1 2 3
CO1 3 2 2 2 1 0 1 0 2 0 2 2 2 2 2
CO2 3 3 2 2 3 0 2 0 2 0 2 2 3 2 2
CO3 3 3 3 2 2 0 3 0 3 0 2 2 3 2 2
CO4 3 3 2 2 2 0 2 0 2 0 2 2 2 2 2
CO5 3 3 2 2 2 0 2 0 2 0 2 2 2 2 2