Data Structure and Algorithms



Introduction to Data Structures, Purposes of data structure, 

Array: Insertion, Deletion, Matrix representation of arrays, Multidimensional arrays, Pointers arrays, Record structures, Parallel arrays, Sparse matrices. 

Linked List: Types of Linked Lists, Basic Operations on Linked List (Insertion, Deletion and Traverse). 

Stack: Basic Stack Operations (Push and Pop), Infix, Postfix and Prefix Notation of Arithmetic Expressions, Conversions and Evaluations of Arithmetic Expressions Using Stack, 

Recursion: Direct and indirect recursion, Simulation of recursion, Depth of recursion, Removal of recursion. Problem of Towers of Hanoi. 

Queue: Typesof Queue, Basic Queue Operations (Insertion and Deletion). 

Searching: Sequential Searching, Binary Searching, 

Basic Sorting: Quick Sort, Merge Sort, Selection Sort, Inserting Sort, Radix Sort, Counting Sort, External Sort, 

Binary Tree: Binary tree representation, Traversal of Binary Tree (Inorder, Preorder and Postorder), Application of Binary Trees. Binary Search Tree, 

Heap – Max and Min Heap, Operations on Heap (Insertion and Deletion), Heapsort, Priority Queue , 

General Tree: Representation of General Tree, Conversion Algorithm (General Tree to Binary Tree), 

Balanced Tree: Basic Concepts of 2-3 Tree, 2-3-4 Tree, AA Tree and AVL Tree, B-Tree and Basic Operations on B-Tree, Huffman Codes and Compression Algorithm, Disjoint Set and Operations and Disjoint set forests, 

Graphs: Graph Representation, Basic Operations on Graph (Node/ Edge Insertion and Deletion), 

Hashing: Hash Function and Overflow Handling, Open Hashing and Close Hashing, Linear Probing, Quadratic Probing, Double Hashing, randomize hash. 

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

Algorithms: The role of algorithms in computing. 

Complexity Analysis: Growth of a function, Asymptotic notation and Runtime analysis of Algorithms. 

Recurrence Relation: Methods to solve recurrences, Substitution method, Recursion tree method, Master method. 

Graph related algorithms: Breadth First search, Depth First Search, Topological sort, Strongly connected components, Euler Path, Articulation Point. 

Shortest Path: Dijkstra’s shortest path algorithm, The Bellman-Ford algorithm for single source shortest path, The Floyd-Warshall algorithm for all-pair shortest path. 

Divide and Conquer: basic idea, properties, Applications, Counting Inversions, Closest pair of points, etc. 

Dynamic Programming: Basic idea, Comparison with Divide and Conquer, Memorization. Application of Dynamic programming: Coin related problems, Longest Increasing Sequence (LIS), Longest Common Subsequence (LCS), 0/1 Knapsack problem, Matrix Chain Multiplication, etc. 

Greedy method: Elements of greedy method basic control structure, Comparison with dynamic programming and Divide and Conquer. Application of Greedy method: Minimum spanning tree: The algorithms of Prim & Kruskal, Job sequencing with deadline. 

Backtracking: Basic idea behind backtracking, control structure. Application of backtracking: Permutation & Combination Generation, Graph coloring problem, n-queens problems, Hamiltonian Cycle etc. Branch and Bound. 

Network Flow: Flow networks, The Ford-Fulkerson method, maximum bipartite matching, Maxflow-Mincut Theorem. Lower bound Theory for sorting, Exhaustive Search. 

Number Theoretic Algorithms: Extended Euclid’s Theorem, Solving modular linear equations, The Chinese remainder theorem, The RSA public key encryption. 

Computational Geometry related Algorithms: Line segment intersection, Inclusion in a polygon, Finding Convex Hull: Grahams scan, Jervis’s March. 

String Matching Algorithms: Naive string matching algorithm, String matching with finite automata, The Boyer-More algorithm for string matching, Knuth-Morris-Pratt algorithm. 

NP-Completeness: Polynomial time, Polynomial Time verification, NP-completeness and reducibility, NP-Completeness proofs, NP Complete problems. 

Approximation Algorithms: Introduction, Approximation Ratio, Approximation algorithms for Vertex-Cover Problem, TSP Problem

Post a Comment

Previous Post Next Post