BITM Data Structure and Algorithm with Java
bitmsemester 4
Data Structure and Algorithm with Java
Subject Code: IT218
Course Title: Data Structure and Algorithm with Java
Course No: IT218
Nature of Course: Theory & Practical
Full Marks: 60 + 40
Pass Marks: 30 + 20
Credit Hours: 3
Course Description
The course contains Complexity Analysis, Linked Lists, Stacks and Queues, Recursion, Binary Trees, Multiway Trees, Graph, Sorting, Hashing.
Course Objective
This course aims to provide a systematic introduction to data structures and algorithms for constructing efficient computer programs. The course emphasizes on data abstraction issues (through ADTs) in the program development process, and on efficient implementation of chosen data structures and algorithms. Laboratory work is essential in this course.
Course Contents
| Course Contents | Teaching Methodology | Teaching Hours |
|---|---|---|
| Unit 1: Complexity Analysis (4 Hrs.) | ||
| Computational and Asymptotic Complexity. | Lecture/Lab | |
| Big-O Notation. | ||
| Properties of Big-O Notation Ω and Q. | ||
| Possible Problems. | ||
| Examples of Complexities. | ||
| Finding Asymptotic Complexity: Examples. | ||
| The Best, Average, and Worst Cases. | ||
| Amortized Complexity. | ||
| NP-Completeness. | ||
| Unit 2: Linked Lists (5 Hrs.) | ||
| Singly Linked Lists: Insertion, Deletion, Search. | Lecture/Lab | |
| Doubly Linked Lists: Circular Lists, Skip Lists, Self-Organizing Lists. | ||
| Sparse Tables. | ||
| Case Study: A Library. | ||
| Unit 3: Stacks and Queues (4 Hrs.) | ||
| Stacks, Queues, Priority Queues. | Lecture/Lab | |
| Case Study: Existing a Maze. | ||
| Unit 4: Recursion (4 Hrs.) | ||
| Recursive Definitions. | Lecture/Lab | |
| Method Calls and Recursion Implementation. | ||
| Anatomy of a Recursive Call. | ||
| Tail Recursion. | ||
| Nontail Recursion. | ||
| Indirect Recursion. | ||
| Nested Recursion. | ||
| Excessive Recursion. | ||
| Backtracking. | ||
| Unit 5: Binary Trees (9 Hrs.) | ||
| Trees, Binary Trees, and Binary Search Trees. | Lecture/Lab | |
| Implementing Binary Trees. | ||
| Searching a Binary Search Tree. | ||
| Tree Traversal. | ||
| Breadth-First Traversal. | ||
| Depth-First Traversal. | ||
| Insertion, Deletion, Deletion by Merging, Deletion by Copying. | ||
| Balancing a Tree. | ||
| The DSW Algorithm. | ||
| AVL Trees. | ||
| Self-Adjusting Trees. | ||
| Self-Restructuring Trees, Splaying. | ||
| Heaps: Heaps as Priority Queues, Organizing Arrays as Heaps, Polish Notation and Expression Trees. | ||
| Operations on Expression Trees. | ||
| Case Study: Computing Word Frequencies. | ||
| Unit 6: Multiway Trees (5 Hrs.) | ||
| The Family of B-Trees. | Lecture/Lab | |
| B-Trees, B*-Trees, B+-Trees. | ||
| Case Study: Spell Checker | ||
| Unit 7: Graphs (6 Hrs.) | ||
| Graph Representation. | Lecture/Lab | |
| Graph Traversals, Shortest Paths, All-to-All Shortest Path Problem, Cycle Detection. | ||
| Spanning Trees. | ||
| Connectivity. | ||
| Connectivity in Undirected Graphs, Connectivity in Directed Graphs. | ||
| Topological Sort, Networks. | ||
| Unit 8: Sorting (6 Hrs.) | ||
| Elementary Sorting Algorithms: Insertion Sort, Selection Sort, Bubble Sort. | Lecture/Lab | |
| Efficient Sorting Algorithms: Heap Sort, Quicksort, Mergesort, Radix Sort. | ||
| Case Study: Adding Polynomials. | ||
| Unit 9: Hashing (5 Hrs.) | ||
| Hash Functions: Division, Folding, Mid-Square Function, Extraction. | Lecture/Lab | |
| Collision Resolution: Open Addressing, Chaining, Bucket Addressing, Deletion. | ||
| Case Study: Hashing with Buckets. |
Text Books
1. Drozdek Adam, Data Structures and Algorithms in Java, 3rd edition
Reference Books
1. Duncan A. Buell, Data Structures Using Java
2. Main Michael, Data Structures and Other Objects Using Java, Prentice Hall (4th edition)
3. Robert Lafore, Data Structures and Algorithms in Java, Sams Publishing
4. Narasimha Karumanchi, Data Structures And Algorithms Made Easy In Java, CareerMonk Publications