Algorithm Analysis & Design

GANPAT UNIVERSITY

FACULTY OF ENGINEERING & TECHNOLOGY

Programme

Bachelor of Technology

Branch/Spec.

Computer Science & Engineering

(CBA/CS/BDA)

Semester

V

Version

1.1.1.2

Effective from Academic Year

2022-23

Effective for the batch Admitted in

June 2020

Subject code

2CSE503

Subject Name

ALGORITHM ANALYSIS & DESIGN

Teaching scheme

Examination scheme (Marks)

(Per week)

Lecture(DT)

Practical(Lab.)

Total

CE

SEE

Total

L

TU

P

TW

Credit

3

0

2

0

5

Theory

40

60

100

Hours

3

0

4

0

7

Practical

60

40

100

Pre-requisites:

Data Structures and programming

Learning Outcome:

After completion of the course, student will be able to:

• Understand the fundamentals of algorithms and finding time and space complexities
• Learn polynomial and non-polynomial problems
• Analyze and compare various algorithms and its application
• Apply appropriate Algorithm Design technique to a specific problem

Theory syllabus

Unit

Content

Hrs

1

Fundamental of Algorithms

Requirement of algorithms, Why to analyze algorithms, Problems & instances, efficiency of algorithms, time and space complexity, average & worst case analyses, asymptotic notation, Types of algorithms: Iterative v/s Recursive, analyzing control structures, amortized analysis, Complexity analysis of sorting algorithms

8

2

Solving Recurrences

Generating recurrence relations from algorithms, homogeneous recurrences, inhomogeneous recurrences, change of variable, range transformations, asymptotic recurrences, substitution method, iteration method, recurrence trees, master theorem.

6

3

Divide and Conquer

Characteristics, applications: binary search, merge sort, quick sort, matrix multiplication, counting inversion, Closest Pair of Points, MinMax.

4

4

Greedy Algorithms

General characteristics of greedy algorithms and examples, applications: Kruskal’s and Prim’s algorithms, introduction to shortest path problem variants, single source shortest path problem, knapsack problem, scheduling problem, Huffman code.

7

5

Dynamic Programming

General characteristics and examples, principle of optimality, applications: binomial coefficients, making change, knapsack problem, Floyd’s algorithm, chained matrix multiplication, Longest Common Subsequence (LCS) problem, memory functions.

8

6

Graph Algorithms

Directed acyclic graph, topological ordering & sorting, backtracking, application of backtracking: knapsack problem, Queen’s problem, Branch & bound and its application.

7

7

Computational Complexity

Polynomial (P) and Non Polynomial (NP) problems, NP Hard and NP Completeness, SAT problem, Traveling Salesman Problem.

5

Self-Study Topics :

• String Matching Algorithms

Practical content

Practicals will be based on Sorting Algorithm, Searching Algorithm, Greedy Algorithms. Dynamic Programming Algorithms. Graph Algorithms, Backtracking Algorithms.

Mooc Course

Course Name: Design and analysis of algorithms

Link: https://onlinecourses.nptel.ac.in/noc21_cs22/preview

Text Books

1

Introduction to Algorithms by Cormen, Leiserson, Rivest, Prentice Hall of India

Reference Books

1

Fundamentals of Algorithmics by Brassard &Bratley, Prentice Hall of India

2

Ellis Horowitz, SartajSahni, Fundamentals of computer algorithms, Computer Science Press

3

Design and Analysis of Algorithms, Pearson.

Course Outcomes:

COs

Description

CO1

Understand the fundamentals of algorithms and finding time and space complexities

CO2

Learn polynomial and non-polynomial problems

CO3

Analyze and compare various algorithms and its application

CO4

Apply appropriate Algorithm Design technique to a specific problem

Mapping of CO and PO: