Data Structures

Asymptotic notation. Introduction to Algorithm Analysis Methodologies Review of Data Structures: Linear Data Structures – Linked Lists: – Singly LL, Doubly LL,Circular LL. Implementation–Applications. Stacks:-Implementation using Arrays and Linked Lists –Applications in Recursion. Queues -Implementation and Applications. Binary Trees – Basic tree traversals – Binary tree -Priority queues -Binary search tree. AVL trees.

Graphs -Data Structures for Graphs, Types of Graphs: Directed Graphs, Weighted Graphs, etc.. Basic definitions and properties of Graphs, Graph Traversal –Breadth First Search and their applications, Spanning trees, Shortest Paths. Hashtables – Collision using Chaining – Linear Probing – Quadratic Probing – Double Hashing.

Algorithms

Review of sets and relations, and matrices. Logic. Series, counting principles. Basic sorting and searching algorithms

Algorithm Analysis: Recurrence Relations and their solutions. Recursion tree method, substitution method and Master theorem. Introduction to Amortized Analysis. Introduction to Divide and Conquer technique. Mergesort, Quicksort and binary search

Introduction to Greedy Algorithms – Fractional Knapsack – Scheduling Algorithms. Introduction to: DP Algorithms – Matrix Chain – Subsequence Problems – 0-1 Knapsack.

Course Outcome

Data Structures

• Michael T Goodrich and Roberto Tamassia and Michael H Goldwsasser, “Data Structures and Algorithms in Python++”, John Wiley publication, 2013.

Data Structures

• Michael T Goodrich and Roberto Tamassia, “Algorithm Design Foundations – Analysis and Internet Examples”, John Wiley and Sons, 2007.
• Dasgupta S, Papadimitriou C and Vazirani U, “Algorithms”, Tata McGraw-Hill, 2009.