Data Structures and Algorithms

Course Title: Data Structures and Algorithms

Course No: CT 232

Nature of the Course: Theory + Lab

Semester: 3

Full Marks: 20 + 20 + 60

Pass Marks: 0 + 0 + 0

Credit Hours: 3

Course Description

This course introduces the fundamental concepts of data structures and algorithms used in computer science and software development. It covers linear and non-linear data structures such as stacks, queues, linked lists, trees, and graphs, along with their implementation and applications. The course also explores recursion, algorithm analysis, sorting and searching techniques, and graph traversal methods. Through theoretical study and practical laboratory exercises, students will develop the skills required to design, implement, analyze, and optimize efficient data management and problem-solving solutions in computing systems.

Course Objectives

To acquaint students with different data structures like stacks, queues, linked lists, trees, and graphs along with their implementations. It also provides different sorting and searching algorithms and their analysis.

Course Contents

1. Introduction to Data Structures

2 hrs

1.1. Introduction

1.2. Types of Data Structures

1.3. Operations on Data Structures

1.4. Abstract data type

1.5. Algorithms and their types

1.6. Features of Algorithms

1.7. Time and Space Complexity

2. Stacks and Queues

6 hrs

2.1. Stacks

2.2. Array Representation of Stacks

2.3. Operations on Stacks

2.4. Converting Infix Expression into Postfix Expression

2.5. Evaluation of Infix Expression

2.6. Applications of Stacks

2.7. Queues

2.8. Array Representation of Queues

2.9. Operations on Queues

2.10. Linear and Circular Queues

2.11. Applications of Queues

3. Linked Lists

6 hrs

3.1. Introduction

3.2. Linked List Versus Arrays

3.3. Implementation of Linked Lists

3.4. Types of Linked Lists

3.5. Linked Stacks and Linked Queues

3.6. Polynomial Representation

4. Recursion

3 hrs

4.1. Introduction

4.2. Principles of Recursion

4.3. Types of Recursion

8 hrs

5.3. Binary Search Tree

5.9. Huffman Tree and its Application

2 hrs

5 hrs

7.10. Comparison of Sorting Algorithms

8. Searching

5 hrs

8.1. Introduction

8.2. Sequential Search

8.3. Binary Search

8.4. Introduction to Hashing

8.5. Hash Table and Hash Function

8.6. Different Hash Functions

8.7. Collisions

8.8. Collision Resolution Techniques

9. Graphs

8 hrs

9.1. Introduction

9.2. Graph Representations

9.3. Types of Graphs

9.4. Graph Traversal Algorithms

9.5. Transitive Closure of Graph

9.6. Warshall's Algorithm

9.7. Spanning Trees

9.8. Shortest Path Algorithms

9.9. Topological Sorting

9.10. Applications of Graphs

Laboratory Works

The laboratory component of this course shall include exercises on the following topics:

Array-based implementation of stacks.
Array-based implementation of queues, including linear and circular queues.
Implementation of linked lists, including singly linked lists and doubly linked lists.
Dynamic implementation of stacks and queues using linked structures.
Application of recursion through the Tower of Hanoi (TOH) problem.
Implementation of tree data structures and tree traversal techniques.
Implementation and analysis of sorting algorithms.
Implementation and analysis of searching algorithms.
Implementation of graph traversal algorithms.

1.Array Implementation of Stack
2.Array Implementation of Queue- Linear and Circular
3.Implementation of Linked Lists - Singly and Doubly Linked Lists
4.Dynamic Implementation of Stack and Queues
5.Application of Recursion - TOH
6.Implementation of trees - Tree Traversals
7.Implementation of Sorting Algorithm
8.Implementation of Searching Algorithm
9.Implementation of Graph Traversal

Reference Books

1.Data Structures Using C, Reema Thareja, Oxford University Press
2.Data Structure and Algorithm : The Complete Reference, Bal krishna Nyaupane, Heritage Publishers and Distributors Pvt. Ltd.
3.Data Structures Using C and C++, Y. Langsam, M.J. Augenstein, A.M. Tanenbaum, Prentice Hall India
4.Data Structures and Program Design in C, R.L. Kruse, B.P. Leung, C.L. Tondo, Prentice Hall India

Notes:

This syllabus follows the official BE Comp curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authorative.

Data Structure and Algorithms