BITM Data Structure and Algorithms
Data Structure and Algorithms
Subject Code: IT238
Course Title: Data Structure and Algorithms
Course No: IT238
Nature of Course: Theory & Practical
Full Marks: 60
Pass Marks: 30
Credit Hours: 3
Course Description
Course Objective
Course Contents
| Course Contents | Teaching Methodology | Teaching Hours |
|---|---|---|
| Unit 1: Introduction to data structure and algorithms (4 Hrs.) | ||
| Data types | Lecture/Lab | |
| Data structure and Abstract date type (ADT) | ||
| Operations performed in data structure | ||
| Introduction to Algorithms | ||
| Computational complexity | ||
| Asymptotic notations: Big-O, Big-Ω and Big-Ө Notation | ||
| Properties of Big-O, Ω and Ө Notation | ||
| Finding Asymptotic Complexity: Examples | ||
| The Best, Average, and Worst-Case analysis | ||
| Unit 2: Linked Lists (7 Hrs.) | ||
| Basic Concept | Lecture/Lab | |
| List and ADT | ||
| Array Implementation of Lists | ||
| Linked List | ||
| Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List | ||
| Basic operations in Linked List: Node Creation, Node Insertion and Deletion from Beginning, End and Specified Position | ||
| Skip List | ||
| Lists in java.util: LinkedList, ArrayList | ||
| Unit 3: Stack (4 Hrs.) | ||
| Basic Concept of Stack | Lecture/Lab | |
| Stack as an ADT | ||
| Stack Operations | ||
| Stack Implementation (Array and Linked List) | ||
| Stack Applications | ||
| Conversion from infix to postfix/prefix expression | ||
| Evaluation of postfix/prefix expressions | ||
| Stacks in java.util | ||
| Unit 4: Queues (4 Hrs.) | ||
| Basic Concept of Queue | Lecture/Lab | |
| Queue as an ADT | ||
| Primitive Operations in Queue | ||
| Linear Queue | ||
| Queue Implementation (Array and Linked List) | ||
| Circular Queue | ||
| Priority Queue | ||
| Queue Applications | ||
| Unit 5: Recursion (2 Hrs.) | ||
| Recursive Definitions | Lecture/Lab | |
| Method Calls and Recursion Implementation | ||
| Direct Recursion | ||
| Indirect Recursion | ||
| Tail Recursion | ||
| Nested Recursion | ||
| Excessive Recursion | ||
| Factorial | ||
| Fibonacci Sequence | ||
| GCD | ||
| Tower of Hanoi (TOH) Problem | ||
| Recursion Vs Iteration | ||
| Unit 6: Trees (9 Hrs.) | ||
| Introduction of Trees | Lecture/Lab | |
| Applications of Tree | ||
| Tree as an ADT | ||
| Binary Trees, and Types of Binary Trees | ||
| Implementing Binary Trees | ||
| Tree Traversal: in-order Pre-order, Post-order | ||
| Binary Search Tree Operation: Insertion, Deletion, Searching | ||
| AVL Trees | ||
| Expression Trees | ||
| Operations on Expression Trees | ||
| Heap | ||
| Huffman Algorithm | ||
| Self-Adjusting Trees | ||
| Multiway Search Tree: B-Tree | ||
| Unit 7: Graphs (7 Hrs.) | ||
| Introduction of graph | Lecture/Lab | |
| Graph as an ADT | ||
| Graph Representation | ||
| Graph Traversals: BFT, DFT | ||
| Greedy Algorithm | ||
| Shortest Path Problem: Dijkstra Algorithm | ||
| All-to-All Shortest Path Problem: Floyd Warshall Algorithm | ||
| Spanning Trees and Minimum Spanning Tree: Kruskal and Prims Algorithm | ||
| Topological Sort | ||
| Unit 8: Sorting (6 Hrs.) | ||
| Introduction | Lecture/Lab | |
| Internal and External Sorting | ||
| Sorting Algorithms: Bubble Sort, Insertion Sort, Selection Sort, Heap Sort, Quicksort, Mergesort, Radix Sort | ||
| Efficiency of sorting algorithms | ||
| Sorting in java.util | ||
| Unit 9: Searching and Hashing (5 Hrs.) | ||
| Introduction | Lecture/Lab | |
| linear search | ||
| binary search | ||
| efficiency of searching algorithms | ||
| Hashing | ||
| Hash Functions: Division, Folding, Mid-Square Function, Extraction | ||
| Collision Resolution technique | ||
| Hashing in java.util |
Text Books
1. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, “Data Structures and Algorithms in Java”, Wiley publication, Sixth Edition, 2014.
2. Drozdek Adam, “Data Structures and Algorithms in Java”, Cengage Learning Asia, Third Edition, 2010.
3. Duncan A. Buell, “Data Structures Using Java” Jones & Bartlett Publishers, 2011
4. Robert Lafore, “Data Structures and Algorithms in Java”, Sams Publishing;
5. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”, Pearson Education Inc, 2015
Lab Works
The laboratory work consists of implementing the algorithms and data structures studied in the course. Lab work will be implemented on Java. Student should implement at least following concepts:
Array and Linked List implementation of List
Stack operations and Queue operations
Recursion
Linked List implementation of Stack and Queues
Binary Search Tree
Graph Representation
Spanning Tree and Shortest Path Algorithms
Sorting, Searching and Hashing algorithms