1. Introduction to Algorithms and Analysis : Overview and importance of algorithms and data structures. Fundamentals of algorithm analysis, Space and time complexity of an algorithm, Types of asymptotic notations and orders of growth, Algorithm efficiency - best case, worst case, average case, Analysis of non-recursive and recursive algorithms, Asymptotic analysis for recurrence relation - Recursive Tree Method. (Chapter - 1) 2. Linear Data Structures : Array - 1D and 2D array, Stack - Applications of stack : Expression Evaluation - Conversion of Infix to postfix and prefix expression, Tower of Hanoi. Queue - Types of Queue : Circular Queue, Double Ended Queue (deQueue), Applications - Priority Queue using Arrays, List - Singly linked lists - Doubly linked lists - Circular linked lists. (Chapter - 2) 3. Sorting and Searching Techniques, Hashing : Searching - Linear Search and binary search (divide and conquer technique), Applications - Sorting - Insertion sort - Selection sort - Bubble sort - Quick sort - Merge sort, Analysis of sorting algorithms. Hash functions, open hashing-separate chaining, closed hashing - linear probing, quadratic probing, double hashing. (Chapter - 3) 4. Divide and Conquer Algorithm : Introduction, Recurrence, and different methods to solve recurrence, multiplying large Integers Problem. (Chapter - 4) 5. Non-linear Data Structures - Trees : Tree - Terminology, Binary Tree - Terminology and Properties, Tree Traversals, Expression Trees - Binary Search Trees - operations in BST - insertion, deletion, finding min and max, Finding the kth minimum element in a BST, AVL tree. (Chapter - 5) 6. Non-linear Data Structures - Graphs : Graph - basic definition and Terminology - Representation of Graph - Graph Traversal : Breadth First Search (BFS), Depth First Search (DFS) (Chapter - 6) 7. Greedy Algorithm : General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm - Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem. (Chapter - 7) 8. Dynamic Programming : Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming - Calculating the Binomial Coefficient, Making Change Problem, Assembly Line - Scheduling, Knapsack problem, Matrix chain multiplication, Longest Common Subsequence. (Chapter - 8) 9. Backtracking and Branch and Bound : Introduction, The Eight queens’ problem, Knapsack problem, Travelling Salesman problem, Minimax principle. (Chapter - 9)
