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
