Data Structure and Algorithm

Course Title: Data Structure and Algorithm

Course No: CMP 176

Nature of the Course: Theory + Lab

Semester: 2

Full Marks: 50 + 50

Pass Marks: 23 + 23

Credit Hours: 3

Course Description

This course offers a thorough examination of the core principles of data structures and algorithms, crucial for computer science students. It starts with an introduction to data structures and advances through abstract data types, algorithm analysis, and design techniques. Topics covered include recursion, stacks, queues, linked lists, trees, sorting, searching, hashing, and graph algorithms, with in-depth explanations and practical examples. Through hands-on exercises, students gain proficiency in designing, implementing, and analyzing these structures and algorithms, with a focus on understanding their efficiency and real-world applications. Upon completion, students are equipped with the essential knowledge and skills to address intricate problems and develop efficient software solutions.

Course Objectives

Provide a comprehensive understanding of fundamental data structures and algorithms. Equip students with proficiency in designing, implementing, and analyzing data structures and algorithms. Foster a deep comprehension of the efficiency and practical implications of different algorithms. Prepare students to tackle complex problems and develop effective software solutions.

Course Contents

1. Introduction to data Structure

3 hrs

1.1. introduction

1.2. Definition

1.3. Classification of data structure

1.4. Abstract Data Type

1.5. Comparison between Data structure and ADT

1.6. Algorithm

1.7. Analysis algorithm

1.8. Design algorithm

Incremental approach

Divide and conquer

1.9. Performance analysis and measurement

Space complexity

Time complexity

2. Recursion

4 hrs

2.1. Introduction to Recursion

2.2. Principle of Recursion

2.3. Types of Recursions

Direct

Indirect

Linear

Tail recursion

2.4. Recursion Examples

Fibonacci Series

2.5. Application of Recursion

3. Stacks

4 hrs

3.1. Introduction

3.2. Operation stack

3.3. Stack terminology

3.4. Algorithm for POP and PUSH

3.5. Stack Applications

Stack frame

Reverse string

Calculation of postfix expression

A notation conversion

3.6. Algorithm for converting infix expression to postfix from

4. Queue

4 hrs

4.1. Introduction

4.2. Queue terminology

4.3. Algorithm for insertion queue

4.4. Algorithm for deletions in queue

4.5. Limitation of simple queue

4.6. Variation in a queue

A circular queue

Priority of queue

4.7. Application of queue

5. Linked List

5 hrs

5.1. Introduction

5.2. Linked List

Advantage and disadvantage

5.3. Key term

Data field

Linked field

5.4. Representation liner linked list

5.5. Operation of linked list

Creation

Insertion

Deletion

Traversing

Searching

Concatenation

Display

5.6. Types of linked list

Single linked list

Double linked list

Circular linked list

Circular double linked list

5.7. Create single linked list

5.8. Insertion of single linked list at specific position

5.9. Deletion of single linked list at specific position

5.10. Application: addition of two polynomials

6. Trees

7 hrs

6.1. Introduction

6.2. Tree terminology

6.3. Binary tree

Strictly binary tree

Complete binary tree

Extended binary tree

6.4. Binary tree representation

Array representation of binary tree

Linked list representation of binary tree

6.5. Create binary tree

6.6. A traversal of a binary tree

Preorder traversal

Inorder traversal

Post order traversal

6.7. Binary search tree

Insertion

Deletion

6.8. Tree Height, Level and Depth

6.9. Balanced Tree: AVL Balanced Trees

6.10. The Huffman Algorithm

6.11. B-Tree

7. Sorting

7 hrs

7.1. Introduction

7.2. Internal & External Sort

7.3. Common sorting algorithm

Bubble sort

Insertion

Selection Sort

Quick Sort

Merge Sort

Shell Sort

Binary Sort

7.4. Efficiency of Sorting, Big 'O' Notation

8. Searching

5 hrs

8.1. Introduction

8.2. Searching Technique

Sequential Search

Binary Search

Tree Search

8.3. Hashing

Hash functions

Hash tables and application

8.4. Collision resolution techniques

8.5. Hashing with open addressing

Linear probing

Quadratic probing

Double hashing

8.6. Hashing with chaining

8.7. Rehashing

8.8. Efficiency comparison of different search technique

9. Graph

7 hrs

9.1. Introduction

9.2. Graph terminology

9.3. Types of Graphs

Undirected graph

Directed graph

9.4. Graph representation

9.5. Graph Traversal

Breath first search

Depth first search

9.6. Spanning tree and Minimum spanning tree

Kruskal's algorithm

Prime algorithm

9.7. Shortest Path problem

Dijkstrs's Algorithm

9.8. Application graph

10. Growth Functions

2 hrs

10.1. Introduction to Asymptotic Notations

10.2. Big Oh notation

10.3. Omega notation

10.4. Theata notation

10.5. Limatitation of big Oh notation

Laboratory Works

It builds the foundation on how to write a program using any high-level language. Hence, this course requires a lot of programming practice so that students will be able to develop good logic building and program developing capability which is essential throughout the course.

1.Stack Operations
2.Queue Operations
3.Recursion
4.Singly Linked List Operations
5.Trees
6.Merge Sort
7.Searching Techniques
8.Graph Traversal
9.Hashing

Text Books

1.Langsam, Y., Augenstein, M. J., & Tanenbaum, A. M. (2019). Data Structures using C and C++. PHI

Reference Books

1.Rowe, G. W. (1997). Introduction to Data Structures and Algorithms with C and C++. PHI
2.Lafore, R. (2002). Data Structures and Algorithms in Java. Sams Publishing
3.Baluja, G. S. (2016). Data Structures through C. Dhanpat Rai & Co

Data Structure and Algorithms

Data Structure and Algorithms

Select University

Select Program

TabFlux . Data Structure and Algorithm . PoU . BCSIT