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