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
إرسال تعليق