Course Code: BCA212 |
Course Title: Data Structure and Algorithm (4 Credits) |
Course Contents
Unit – 1: Data Structures Basics: Structure and Problem Solving, Data structures, Data structure Operations, Algorithm: complexity, Time- space tradeoff.
Unit – 2: Linked List: Introduction, Linked lists, Representation of linked lists in Memory, Traversing a linked list, Searching a linked list, Memory allocation and Garbage collection, insertion into linked list, Deletion from a linked list, Types of linked list.
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 – Unweighted Shortest Paths – Dijkstra’s Algorithm, Minimum spanning tree- Prim’s Algorithm, Introduction to NP-Completeness.
Unit – 8: Searching Techniques: Sequential Searching, Binary Searching, Search Trees, Hash- Table Methods.
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: Complexity of Algorithms: Notations for the Growth Rates of Functions; Classification of Problems; Reduction, NP-Complete and NP-Hard Problems, Establishing NP-Completeness of Problems.