Lecture Plan Subject: Algorithm Analysis & Design Paper Code: etcs-204



Download 34.03 Kb.
Date05.08.2017
Size34.03 Kb.
#27037
Lecture Plan

Subject: Algorithm Analysis & Design Paper Code:ETCS-204

S.NO.

Topics to be Covered

No. of Lectures


First Term

1.

Introduction to algorithms, algorithm design, analysis, validation.

1


2.

Review of growth of function with numerical problems

2

3.

Recurrence: substitution method, iteration method

2

4.

Recurrence: Recursion tree method

1

5.

Recurrence : Master’s method with proof

2

6.

Incremental Approach: Insertion Sort

1

7.

Divide and conquer approach:

Merge Sort

Quick Sort


2

8.

Median and order Statistics

2

9.

Data structure for Disjoint sets

2

10.

Strassen’s algorithms for matrix multiplications

1

11.

Dynamic programming:

Elements of Dynamic programming



1

Matrix Chain multiplication

2

Longest Common Subsequence

1

Optimal Binary Search Tree

2

Second Term

12.

Greedy algorithms:

Elements of Greedy Strategy
1

Activity Selection problem

1

Knapsack Problem

1

Huffman Coding

1

Task Scheduling Problem

1

13.

Graph Algorithms:

Representation of graphs
1

Breadth First Search

1

Depth First Search

1

Topological sort & connected Components

1

14.

Spanning Tree Problem:

Kruskal’s Algorithm

Prim’s Algorithm


2

15.

Shortest Path problem:

Dijkstra’s Algorithm

Bellman Ford Algorithm


2

16.

All Pair Shortest path problem:

Floyd Warshall algorithm
2

17.

String Matching Problems:

Naïve String Matching algorithms
1

Rabin Karp string Matching

1

String Matching With Finite Automata

1

Knuth-Morris Pratt Algorithm

1

Third Term

18.

NP-Complete Problem:





Polynomial time Verification

1

NP-Completeness & reducibility

1

NP-Completeness Proof

2

NP-Completeness Problems

2

TEXT BOOKS:

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, “Introduction to Algorithms”, 2nd Ed., PHI, 2004.



REFERENCES BOOKS:

1. A. V. Aho, J. E. Hopcroft, J. D. Ullman, “The Design and Analysis of Computer Algorithms”, Addition Wesley, 1998.



2. Ellis Horowitz and Sartaz Sahani, “Computer Algorithms”, Galgotia Publications, 1999.

3. D. E. Knuth, “The Art of Computer Programming”, 2nd Ed., Addison Wesley, 1998

Download 34.03 Kb.

Share with your friends:



The database is protected by copyright ©ininet.org 2024
send message
    Main page
Guide
Instructions
Report
Request
Review