Data Structures and Programming Methodology

Data Structures and Programming Methodology 

Objectives: This course should provide the students with a fairly good concept of the fundamentals of different types of data structures and also the ways to implement them. Algorithm for solving problems like sorting, searching, insertion & deletion of data etc. related to data structures should also be discussed. After completion of this subject student should be able to choose an appropriate data structure for a particular problem.

Introduction: Definition and brief description of various data structures, operations on data structures, Algorithm development, Complexity analysis, Big O notation, Time space trade-off.

Arrays: Linear and Multi-dimensional arrays and their representation, operations on arrays, Linear Search, Binary Search, Sparse matrices and their storage.

Stacks: Array Representation and Implementation of Stacks, Operations on Stacks, Application of stacks: Conversion of Infix to Prefix and Postfix Expressions, Evaluation of postfix expression using stack, Balanced parenthesis checking.

Recursion: Recursive definition and examples of recursion, Tower of Hanoi Problem, tail recur RecursionQueues: Sequential representation of queue, linear queue, circular queue, operations on linear and circular queue, deque, priority queue.

Linked Lists: Linear linked list, operations on linear linked list, doubly linked list, operations on doubly linked list, Circular Linked list, Garbage collection and Compaction, Linked representation of Stack, Linked representation of a Queue. 

Trees: Basic terminology, sequential and linked representations of trees, traversing a binary tree, brief

introduction to threaded binary trees, AVL trees and B-trees, Heap Trees.

Binary Search Trees: Binary Search Tree (BST), Insertion and Deletion in BST, Complexity of Search Algorithm.

Graphs: Basic terminology, representation of graphs (adjacency matrix, adjacency list),

traversal of a graph (breadth - first search and depth - first search). 

Sorting: Selection Sort, Insertion Sort, Bubble Sort, Quick Sort, Merge Sort, Heap Sort, Shell sort. Complexity

Hashing: Hashing Functions, Collision Resolution Techniques, Rehashing, Double hashing.