# Computer Algorithm (2710201)

## Teaching Scheme (in Hours)

Theory Tutorial Practical Total
3 2 2 5

Subject Credit :  5

Theory
ESE (E)
Theory
PA (M)
Practical
ESE Viva (V)
Practical
PA (I)
Total
0

## Syllabus Content

###### Unit-1:  Unit-1

From problems to programs, set theory, functions and relations Insertion sort, analyzing algorithms, designing algorithms, asymptotic notation.

###### Unit-2:  Unit-2

Divide and conquer, Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion tree method for solving recurrences, master method.

###### Unit-3:  Unit-3

Dynamic programming, Making Change, The principal of optimality, the knapsack problem, Floyd’s algorithm for shortest paths.

###### Unit-4:  Unit-4

Greedy Algorithms, making change, Knapsack problem, Shortest Path – Dijkstra’s algorithm, Huffman codes.

###### Unit-5:  Unit-5

Amortized analysis- aggregate analysis, accounting method, potential method.

###### Unit-6:  Unit-6

Single source shortest paths. Bellman Ford, directed acyclic graphs, Floyd Warshall algorithm.

###### Unit-7:  Unit-7

Number theoretic algorithms, Greatest common dividor, Modular arithmetic.

###### Unit-8:  Unit-8

String matching, the naïve string matching, Rabin Karp algorithm,Boyer Moore pattern matching, Knuth Moriss Pratt algorithm.

###### Unit-9:  Unit-9

Introduction to NP completeness, The class P and NP, polynomial reductions, NP complete problems.

###### Unit-10:  Unit-10

Heuristic algorithm – the travelling salesperson, approximate algorithms-knapsack problem.

## Reference Books

Sr. Title Author Publication Amazon Link
1 Introduction to Algorithms Thomas Cormen, Charles Leiserson, Ronald Rivest PHI
2 Fundamentals of Algorithms Gilles Brassard,Paul Bratley. Prentice-Hall
3 Advanced Data Structure Peter Brass Cambridge University Press
4 Data structures and Algorithms Allfred Aho, Jeffrey Ullman, John Hopcroft Pearson
5 Data Structures and Algorithms G.A.V. Pai TMH
6 Fundamentals of Computer Algorithms Ellis Horowitz, Sartaj Sahni and Sanguthevar Universities Press
7 Classic Data Structures D. Samanta PHI
8 Design and Analysis of Computer Algorithms Aho, Hopcraft, Ullman Pearson
9 Introduction to the Design and Analysis of Algorithms Goodman, Hedetniemi TMG
10 Design and Analysis of Algorithms E. Horowitz, S. Sahani Galgotia
11 Data Structures and Algorithms in C++ Adam Drozdek Cengage

## Course Outcome

After learning the course the students should be able to:

• Perform best case and worst case analysis of algorithm.
• Solve recurrence problem.
• Find optimal solution by applying various methods.
• Apply pattern matching algorithms to find particular pattern.
• Differentiate polynomial and nonpolynomial problems.
• Find shortest path for directed and undirected graph.

### ME (CE) ⇒ Semester: 1

Darshan Institute of Engineering & Technology is a leading institute offering undergraduate (B.E.), postgraduate (M.E.) and Diploma programs in engineering.

## Our Contacts

At Hadala, Rajkot - Morbi Highway,
Gujarat-363650, INDIA

(+91) 97277 47310
(+91) 97277 47311