Data Structure & Algorithm

Data Structures and Algorithm

EG 2105 CT

	Total:   7 hour /week
Year: II	Lecture:   3 hours/week
Semester: III	Tutorial: 1 hours/week
	Practical:  3 hours/week

Course Introduction

The purpose of this course is to provide the students with the basic concepts of data structures and algorithms. The main objective of the course is to teach the students how to select and design data structures and algorithms that are appropriate for problems that might occur. This course offers the students a mixture of theoretical knowledge and practical experience. Programming language C can be used for practical work.

Objectives   

On completion of this course the students will be enabled to:

•       Introduce data abstraction and data representation in memory

•       Discuss, design and use elementary data structures such as stack, queue, linked list, tree and graph.

•       Decompose complex programming problems into manageable sub-problems  Introduce theory of algorithms and their complexity

Course Contents

Units	Topics	Contents	Hours	Methods/ Media	Marks
1	Introduction to Data Structures and Algorithms	1.1 Data Structures: Definition and Types 1.2 Abstract Date Type 1.3 Dynamic Memory: malloc, calloc, realloc and free 1.4 Introduction to Algorithms: Definition and properties of algorithms 1.5 Asymptotic Notations: Big- O, Big-Ω and Big-θ	(5)
2	Stacks	2.1 Definition, Stack as ADT 2.2 Stack Operations: Concept and Algorithms 2.3 Stack Applications	(5)
3	Queues	3.1 Definition, Queue as ADT 3.2 Queue Operations: Concept and Algorithms 3.3 Queue Applications 3.4 Linear vs Circular Queue 3.5 Circular Queue Operations: Concept and Algorithms	(6)

Units	Topics	Contents	Hours	Methods/ Media	Marks
		3.6 Concept of Priority queue.
4	Recursion	4.1 Definition, Recursion vs Iteration 4.3 Factorial, Fibonacci sequence, and TOH 4.4 Applications and Efficiency of recursion	(4)
5	Linked lists	5.1 Definition, Linked List as ADT 5.2 Types of Linked List 5.3 Basic operations in Singly Linked List: creation, node insertion and deletion from beginning, end, and specified position 5.4 Linked List Implementation of Stack and Queue 5.5 Concept of other types of Linked Lists 5.6 Applications of Linked List	(8)
6	Trees	6.1 Concept and Definition: Concept of level, depth, number of nodes 6.2 Binary Tree and Binary Search Tree 6.3 Insertion, Deletion, and Traversal of BST 6.4 Applications of Tree, Concept of Balanced Trees	(5)
7	Graphs	7.1 Representation and Applications of Graph 7.2 Graph Traversal Algorithms: Depth First Traversal and Breadth First Traversal 7.3 Minimum Spanning Trees: Kruskal’s Algorithms	(5)
8	Sorting and Searching	8.1 Concept of Sorting and           Searching 8.2 Comparison Sorting: Bubble, Selection, and Insertion Sort and their complexity	(7)
Units	Topics	Contents	Hours	Methods/ Media	Marks
		8.3 Divide and Conquer Sorting: Merge, and Quick Sort and their Complexity 8.4 Searching Algorithms: Sequential, and Binary Search 8.5 Concept of Hash Data Structure and Hash Function
Laboratory Work  (45 hrs)			(45 hrs)
-       Write program to implement stack operations  -       Write program to implement linear queue operations -       Write program to implement circular queue operations  -       Write programs to implement recursive algorithms -       Write programs to implement linked list operations -       Write programs to implement linked stack and linked queue -       Write programs to implement Comparison Sorting algorithms -       Write programs to implement searching algorithms -       Write programs to implement BST operations -       Write programs to implement graph operations

Recommended Books

1.    Y Langsam , MJ , Augenstein and A.M , Tanenbaum ( 2007) Data Structures using C and C++ , Prentice Hall India, Second Edition

References

1.  G.W Rowe (2016), Introduction to Data Structure and Algroithms with C and C++ , prentice Hall  India, First Edition 

2.  G. S. Baluja, (2016), Data structure Through C, A Practical Approach, Fourth Edition,

DhanpatRai& Co, Second Edition, 2016