OBJECTIVE : To impart knowledge in fundamentals of programming elements with a view to developing professional software development skills.
PREREQUISITES : Introduction to Theory of Functions and knowledge on primitive data types.
UNIT I: Introduction to Data Structures [10]
Elementary Data Structures — Stacks, Queues, and Linked Lists with Applications Implementing Pointers and Objects, Representing Rooted Trees - Hash Tables — Direct Address Tables, Hash Tables, Hash Functions, Open Addressing — Binary Search Trees — Querying a Binary Search Tree, Insertion and Deletion.
UNIT II: Advanced Data Structures [10]
Red-Black Trees — Properties, Rotations, Insertion and Deletion - B-Trees — Definition, Basic Operations, Deleting a key from B-Tree — Graphs - Representations, Breadth-First and Depth-First
Searches - Data Structures For Disjoint Sets — Operations And Representations.
UNIT III: Introduction to Algorithms [10]
Algorithms — Definition, Complexity Concepts, Asymptotic Notations, Recurrences and Solutions — Design Strategies — Recursion, Divide-and-Conquer, Greedy and Dynamic Programming -
Complexity Analysis of Sorting Algorithms — Insertion, Selection, Bubble, Quick and Heap Sorting Techniques .— Searching Algorithms — Linear and Binary Search — Selection in Linear Time.
UNIT IV: Graph Algorithms [10]
Greedy Strategy — Elements of the Strategy, Explanation with Huffman Coding as Example — Minimum Spanning Trees — Kruskal’s and Prim’s Algorithms — Single-Source Shortest Paths — All- Pairs Shortest Paths — Topological Sort.
UNIT V: Selected Topics and Tractability [10]
Polynomials and FFT, Probabilistic Algorithms -- Introduction, Probabilistic Methods for Selection, Sorting and Searching — Algorithms for Random Number Generation — Basic Concepts of NP- Hard and NP-Complete Problems — Cook’s Theorem (Without Proof) — Reduction — Clique Decision Problem.
TEXT BOOKS:
1. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, Second Edition, 2001, PHI.
2. Ellis Horowitz, Sartaj Shani, and S.Rajasekaran, “Fundamentals Of Computer Algorithms”, 2000, Galgotia.
REFERENCES:
1. G.Brassard and P.Bratley, “Fundamentals of Algorithmics”, 1995, PHI.
2. E.Horowitz, S.Sahni, and S.Anderson, “Fundamentals of Data Structures in C,’ 1992, W.H.Freeman and Co.
3. M.A.Weiss and i.Thompson, “Data Structures and Algorithm Analysis”, Second Edition, 1991, Pearson Publishers.
