## Data Structures and Algorithm Syllabus

 Course Code: BCA212 Course Title: Data Structure and Algorithm (4 Credits)

Back

Course Contents

Unit – 1: Data Structures Basics: Structure and Problem Solving, Data structures, Data structure Operations, Algorithm: complexity, Time- space tradeoff.

Unit – 3: Stack and Queue: Introduction, Array Representation of Stack, Linked List Representation of stack, Application of stack, Queue, Array Representation of Queue, Linked List Representation of Queue.

Unit – 4: Trees: Definitions and Concepts, Operations on Binary Trees, Representation of binary tree, Conversion of General Trees to Binary Trees, Sequential and Other Representations of Trees, Tree Traversal.

Unit –5: Graphs: Matrix Representation of Graphs, List Structures, Other Representations of Graphs, Breadth First Search, Depth First Search, Spanning Trees.

Unit - 6: Directed Graphs Types of Directed Graphs; Binary Relation As a Digraph; Euler’s Digraphs; Matrix Representation of Digraphs.

Unit -7 Applications of Graphs: Topological Sorting, Shortest-Path Algorithms – Weighted Shortest Paths – Dijkstra’s Algorithm, Minimum spanning tree- Prim’s Algorithm, Introduction to NP-Completeness.

Unit – 8: Searching and Sorting Techniques, Sorting Techniques: Bubble sort, Merge sort, Selection sort’, Heap sort, Insertion Sort. Searching Techniques: Sequential Searching, Binary Searching, Search Trees.

Unit 9 : Elementary Algorithms: Notation for Expressing Algorithms; Role and Notation for Comments; Example of an Algorithm; Problems and Instances; Characteristics of an Algorithm; Building Blocks of Algorithms; Procedure and Recursion – Procedure, Recursion; Outline of Algorithms; Specification Methods for Algorithms.

Unit 10: Mathematical Functions and Notations Functions and Notations; Modular Arithmetic / Mod Function; Mathematical Expectation in Average Case Analysis; Efficiency of an Algorithm; Well Known Asymptotic Functions and Notations; Analysis of Algorithms – Simple Examples; Well Known Sorting Algorithms – Insertion sort, Bubble sort, Selection sort, Shell sort, Heap sort.

Unit 11: Divide and Conquer Divide and Conquer Strategy; Binary Search; Max. And Min.; Merge sort; Quick sort.

Unit 12: Greedy Method Greedy Method Strategy; Optimistic Storage on Tapes; Knapsack Problem; Job Sequencing with Deadlines; Optimal Merge Pattern; Single Source Shortlist Paths.

Unit 13: Dynamic Programming Dynamic Programming Strategy; Multistage Graphs; All Pair Shortest Paths; Travelling Salesman Problems.

Unit 14: Backtracking Strategy, 8-Queens Problem, Sum of Subsets, Knapsack Problem.

Back