BIT Data Structures and Algorithms

This course contains the concepts of different types of data structures and concepts of algorithms and their analysis.

This course aims to provide sufficient theoretical and practical knowledge of data structure and algorithms required to build efficient programs.

Course Content	Teaching Methodology	Teaching Hour
Unit 1: Background and Concept of Data Structures (2hrs)
Concepts of Data Types, Data Structure, Abstract Data Type and their uses. Background for Data Structure, Definition and use of ADT, Array as an ADT, Structure, Pointer	Lectures	2 hrs
Unit 2: Algorithms (2hrs)
Introduction to Algorithm and their properties, Concepts of Analysis of algorithm with asymptotic notations (Big Oh) and their properties, time and space complexities	Lectures	2 hrs
Unit 3: Stack (4hrs)
Definition and Primitive Operations, Stack as an ADT	Lecture/Lab	2 hrs
Stack Applications: Evaluation of Infix, Postfix and Prefix expressions, converting from infix to prefix and postfix.		2 hrs
Unit 4: Queue (3hrs)
Definition, Queue as an ADT and Primitive Operations of Linear and Circular Queue. Application and advantages of Linear, Circular Queue, and Priority Queue (Ascending and Descending Priority Queue)	Lecture/Lab	3 hrs
Unit 5: Recursion (2hrs)
Definition and Principle of Recursion, Application of Recursion, Recursion removal using stack, example of recursion for TOH. Factorial, Fibonacci Sequences, GCD, efficiency of above recursive algorithms	Lecture/Lab	2 hrs
Unit 6: List (9hrs)
List concepts, Definition and List as ADT, Static and Dynamic List Structure and implementation, Types of linked list, Operations on Linked List	Lecture/Lab	2 hrs
Singly linked list, Circular Linked List, Doubly Linked List, Doubly Circular Linked List, Inserting, traversing and deleting nodes at beginning, end and specified positions in these linked lists		6 hrs
Linked implementation of a stack and queue in singly linked list		1 hr
Unit 7: Tree (7hrs)
Definition and basic terminologies of tree, Binary Tree: Introduction, Types of Binary Tree, Level and depth, height balance tree (AVL)	Lecture/Lab	2 hrs
Operations in Binary Search Tree (BST): Insertion, Deletion, Searching		3 hrs
Tree Traversal: Pre-order traversal, In-order traversal (sorted list of Nodes), Post-order traversal, Applications of Binary Tree (Huffman tree, expression tree)		2 hrs
Unit 8: Sorting (6hrs)
Introduction and types of sorting. Algorithm and implementation of Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort. Comparison and Efficiency of sorting algorithms	Lecture/Lab	6 hrs
Unit 9: Searching (5hrs)
Introduction. Sequential Search, Binary Search and Tree Search. Comparison and Efficiency of Searching	Lecture/Lab	3 hrs
Hashing: hash function, hash table and collision resolution techniques		2 hrs
Unit 10: Graph (5hrs)
Definition, Representation of Graph, Types of Graph	Lecture/Lab	1 hr
Graph Traversal: Depth First Search, Breadth First Search. Spanning Tree, Prim's Algorithm, Kruskal's algorithm and Round Robin Algorithm		2 hrs
Shortest Path Algorithm, Greedy and Dijkstra's Algorithm		2 hrs

Data Structure and Algorithm is a highly practical oriented course. Each unit should include plenty of programming practices. Laboratory work should include implementation of Stack, Queue, Lists, Tree, Graphs, and Recursive functions as well as implementation of Sorting Algorithms and Searching Algorithms. Laboratory exercises can be implemented in high level programming languages like C or C++.