Unit 1
Introduction to software design
principles, modularity abstract data types, data
structures and algorithms, Linear data
structures-Stacks, arrays, lists, queues and
linked representations; Pre-fix in-fix
and post-fix expressions; Recursion; Set
operations; Hashing and hash
functions; Binary and other trees, traversal algorithms,
Huffman codes; Search trees, priority
queues, heaps and balanced trees.
Unit 2
Models of computation. Algorithm
analysis, order arithmetic, time and space
complexities and average and worst
case analysis, lower bounds.
Unit 3
Algorithm design techniques: divide
and conquer, search and traversals. Dynamic
programming. backtracking. branch and
bound.
Unit 4
Sorting and searching algorithms,
combinatorial algorithms, string processing
algorithms. Algebraic algorithms, set
algorithms. Hard problems and approximation
algorithms.
Unit 5
Problem classes P, NP, NP-hard and
NP-complete, deterministic and
nondeterministic polynomial time
algorithms., Approximation algorithms for some NP
complete problems.
Reference books::
1. D.E.Knuth, The Art of Computer
Programming, Vols. 1 and 3, Addison Wesley
2.V Aho, JE Hopcroft, JD Ullman, Design
& Analysis of Algorithms, Addison Wesley
3. Horowitz, S. Sahni, Fundamentals of
Computer Algorithms, Galgotia Publishers
4. K.Mehlhorn, Data Structures and
Algorithms, Vols. 1 and 2, Springer Verlag,
5. Purdom, Jr.and C. A. Brown,
Analyses of Algorithms, Holt Rinechart and Winston,
No comments:
Post a Comment