## Data Structures

**Course Code: **CSE 2201

**Year:** 2 **Semester:** 2 **Credits:** 3

**Description:**

Array: Insertion, Deletion, Matrix representation of arrays, Multidimensional arrays, Pointers arrays,

Record structures, Representation of records in memory; parallel arrays. Sparse matrices. Usefulness of

sparse matrices. Stack: Push and Pop operations. Arithmetic expression: polish notation implementation

using stack Queue: Insert and Delete operations. Double ended queue, Priority queue. Recursion: Direct

and indirect recursion, Simulation of recursion, Depth of recursion, Removal of recursion. Towers of Hanoi

using recursion. Linked lists: One way and two way linked lists. Traversing, Searching, Insertion and

Deletion operations. Concept of algorithm analysis. Sorting: Bubble sort, Quick sort Merge sort, Selection

sort, Inserting sort, Radix sort, Shell sort. Searching: Linear searching, Binary searching. Binary Trees.

Binary Search Trees: Traversing (inorder, preorder, postorder). Insertion and deletion operations in

Binary search trees. Threaded Binary Tree, Application of trees. Set representation, decision trees, game

trees and counting binary trees. B-tree and basic operations on B-tree. Binomial tree and binomial heap,

operation on binomial heaps. Fibonacci heaps and operations. Heap: Max Heap, Min Heap, Heap sort,

Heap applications. Huffman codes and compression algorithm. Disjoint set and operations and disjoint set

forests forests. Red black tree and operations. General trees. Graphs: Graph representation, Adjacency

matrix, Path matrix, Linked representation. Shortest paths: Warshall 's algorithm. Operations on graphs:

Insertion of an edge or a node. Deletion of an edge or a node. Traversing a graph: Breadth first, Depth first.

Posets: Topological sorting. Spanning trees and connected component. Finding minimum cost spanning

tree using Prim's algorithm. Critical paths, enumerating all paths. Symbol tables: Static and dynamic tree

tables. Hashing: Hash function and overflow handling, Open hashing ( Separate chaining) Close hashing

(Open addressing), Linear probing, Quadratic probing, Double hashing. Files: File queries sequential

organization. Indexing Technique: Cylinder + surface indexing, Hash indexes trees, Indexing-Btrees, Tree

indexing.

**References:**

N/A