P25CA207 - DATA STRUCTURES AND ALGORITHMS

Core VII: DATA STRUCTURES AND ALGORITHMS

SEMESTER: II                                        CODE: P24CA207

CREDITS: 4                               HOURS/WEEK: 4

                                Syllabus

UNIT I - Introduction to Data Structures         

• Introduction and Overview: Definitions – Concept of Data Structures – Overview of Data Structures – Implementation of Data Structures.
• Linked Lists: Definition – Single Linked List – Circular Linked List – Double Linked List – Circular Double Linked List – Application of Linked Lists.
• Stacks: Introduction – Definition – Representation of Stack – Operations on Stacks – Application of Stacks.
• Queues: Introduction – Definition – Representation of Queues – Various Queue Structures– Application of Queues.

UNIT II - Tree and Binary Tree

• Trees: Basic Terminologies
• Binary Tree: Representation of Binary Tree – Operations on Binary Tree.
• Types of Binary Trees: Expression Tree – Binary Search Tree – Heap Tree – Threaded Binary Tree – Height Balanced Tree.

UNIT - III - Graphs and Algorithm Analysis

• Graphs: Introduction – Graph Terminologies – Representation of Graphs – Operations on Graphs.
• Applications of Graph Structures: Shortest Path Problem – Topological Sorting – Minimum Spanning Tree.
• Algorithm: Introduction – Algorithm Specification - Performance Analysis.

UNIT IV - Divide and Conquer and Greedy Method

• Divide and Conquer: General Method – Binary Search – Finding the Maximum and Minimum – Merge Sort – Quick Sort.
• Greedy Method: General Method – Knapsack Problem – Job Sequencing with Deadlock – Minimum Cost Spanning Trees: Kruskal’s Algorithm – Prim’s Algorithm.

UNIT V - Dynamic Programming and Backtracking

• Dynamic Programming: General Method – All Pairs Shortest Paths – 0/1 Knapsack Problem – The Traveling Salesperson Problem.
• Backtracking: The General Method – The 8-Queen’s Problem – Graph Coloring – Hamiltonian Cycles.