CA 711

DATA STRUCTURES AND ALGORITHMS

OBJECTIVE:
To introduce different data structures; searching and sorting techniques and their applications.
Linear data Structures – Arrays, Structures, Linked Lists – Singly, Doubly, Circular, XOR, VList, Skip, Jump List, Stack: Definition and examples, Representing Stacks - Queues: Definition and examples, priority queue, Deque, IRD, ORD – Applications of Stack, Queue and Linked Lists- Hashing


Non-Linear data Structures - Graphs – Representation – Linked representation of Graphs – Graph Traversals - Binary Trees – Binary Tree Representations – node representation, internal and external nodes, implicit array representation - Operations on binary trees – Binary tree Traversals - Representing Lists as Binary Trees


Advanced data structures –Data structures for disjoint sets- Red-black trees – insertion and deletion – B-trees – Definition, insertion, deletion – Splay tree, Binomial heaps – operations – Geometric data structures: segment trees, range trees, partition trees


Single-source shortest path algorithms – Bellman-Ford algorithm and Dijkstra's algorithm- Transitive closure -Topological sort
Basic sorting techniques – selection sort, bubble sort, insertion sort and merge sort – Basic Search Techniques – linear search and binary search –Search Trees – Tree searching


REFERENCES:
1. S. Lipschutz and G.A.V. Pai, “Data Structures”, Tata McGraw-Hill,2010.
2. M.A.Weiss, “Data Structures and Problem Solving using Java”, 4th Edition, Addison Wesley,2009.
3. P. Brass, “Advanced Data Structures”, Cambridge University Press,2008.
4. M.J.Augestein, Y.Langsam and A.M. Tenenbaum, “Data Structures using Java", Pearson Education, 2004.
5. R. Kruse and C.L. Tondo, “Data Structures and Program Design in C”, 2nd Edition, Prentice Hall,1996.
6. T.A.Standish, “Data structures, Algorithms and Software principles in C”, Addison Wesley, 1994.


COURSE OUTCOME:
Students will be able to
1. Use linear and nonlinear data structures to solve real-time problems
2. Apply basic searching and sorting techniques in different application domains
3. Use design strategies to solve complex problems