Data Structure and Algorithms

Course Title: Data Structure and Algorithms

Course No: ENCT 252

Nature of the Course: Theory + Lab

Semester: 4

Full Marks: 40 + 60 + 50

Pass Marks: 16 + 24 + 20

Credit Hours: 3

Course Description

This course imparts fundamental knowledge on the design and implementation of data structures for storing information. It also covers various algorithms used in computer science. Upon completion, students will be able to design and choose the appropriate data structure and efficient algorithm to achieve optimal performance.

Course Objectives

To impart fundamental knowledge on the design and implementation of data structures for storing information. To cover various algorithms used in computer science. Upon completion of this course, students will be able to design and choose the appropriate data structure and efficient algorithm to achieve optimal performance.

Course Contents

1. Introduction

4 hrs

1.1. Introduction to data structures

Need of data structures

Types of data structures and its characteristics

1.2. Abstract data type (ADT)

1.3. Basics of algorithm design techniques (Brute Force, divide and conquer, Greedy algorithms, branch and bound, backtracking, randomized, recursive, dynamic programming)

1.4. Algorithm analysis

Time and space complexity

Best, worst and average case analysis

Rate of growth

Asymptotic notations: Big Oh, Big Omega and Big Theta

2. Stack and Recursion

7 hrs

2.1. Definition of stack and its operations

2.2. Array implementation of stack ADT

2.3. Stack applications

Expression conversion: Infix to postfix and prefix expression

Expression evaluation: Infix and postfix expression evaluation

2.4. Recursion

Concept of recursion

Recursion and stack

Recursion vs iteration

Execution of recursive calls

Types of recursions

Applications of recursion: Tower of Hanoi

3. Queues

5 hrs

3.1. Definition of queue and its operations

3.2. Array implementation of queue ADT

3.3. Types of queue ADT: Linear, circular, double ended and priority queues

4. Linked List

6 hrs

4.1. Definition of list and its operations

4.2. Array implementation of list ADT

4.3. Static list and its limitations

4.4. Linked list: Definition and its operations

4.5. Types of linked list: Singly, doubly, circular

4.6. Application of linked list

Linked list implementation of stack and queue ADT

Solving polynomial equations using linked list

5. Tree

7 hrs

5.1. Definition and tree terminologies

5.2. Binary trees

Definition and types

Array and linked list representation

Traversal algorithms: Pre-order, in-order and post-order traversal

Application of full binary tree: Huffman algorithm

5.3. Binary search tree

Definition and operations on binary search tree: Insertion, deletion, searching and traversing

Construction of binary search tree

5.4. Balanced binary tree

Problem with unbalanced binary trees

Balanced binary search tree

AVL tree, definition and need of AVL tree, construction of AVL tree: Insertion, deletion on AVL tree and rotation operations

5.5. Introduction to red-black tree

5.6. B-Tree: Need, definition and construction of B-tree

6. Graphs

6 hrs

6.1. Definition, terminologies and types of graphs

6.2. Representation of graphs: Adjacency matrix, incidence matrix and adjacency list

6.3. Transitive closure and Warshall's algorithm

6.4. Graph traversals: Breadth-first search, depth-first search and topological sort

6.5. Minimum spanning tree: Kruskal's algorithm and prim's algorithm

6.6. Shortest-paths problems: Dijkstra's algorithm, Floyd-Warshall algorithm

7. Sorting Algorithms

5 hrs

7.1. Definition of sorting and its applications

7.2. Types of sorting: Internal/external sort, stable/unstable sort, in-place/not in-place sort, adaptive/non-adaptive sort

7.3. Sorting algorithms and its efficiency: Bubble, insertion, selection, shell, quick, merge, radix and heap sorting

8. Searching Algorithms

5 hrs

8.1. Definition of searching techniques and its applications

8.2. Different searching algorithms and its efficiency

Sequential search

Binary search

8.3. Hashing

Definition and its applications

Hash function

Hash table

Collision in hash table

Collision resolution techniques: Chaining method and open addressing method (Linear probing, quadratic probing and double hashing)

Laboratory Works

Practical sessions covering implementation of stacks, queues, linked lists, trees, graphs, sorting algorithms, and searching algorithms using arrays and linked structures.

1.Implementation of stack using array and its applications
2.Implementation of recursive algorithms
3.Implementations of linear queue and circular queue using arrays
4.Implementation of static list and linked list
5.Implementation of stack and queue using linked list and application of linked list
6.Implementation of in-order, pre-order and post-order tree traversals
7.Implementation of breadth-first and depth-first search to traverse a graph
8.Implementation of different sorting algorithms
9.Implementation of different searching algorithms

Text Books

1.Langsam, Y. Augenstein .M. J. and Tenenbaum A. M. (1996). Data Structures using C and C++. Prentice Hall Press.
2.Rowe, G. W. (1997). Introduction to data structures and algorithms with C++. Prentice-Hall, India.
3.Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to algorithms. MIT press.
4.Kruse, R. L., and Ryba, A. J. (1998). Data structures and program design in C++. Prentice Hall, India.
5.Thareja, R. (2014). Data Structures Using C. Oxford University Press.

Notes:

This syllabus follows the official BCE curriculum of Tribhuwan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://ioe.tu.edu.np/pages/computer-engineering-curriculum-structure-2635

Data Structure and Algorithms

Data Structure and Algorithms

Select University

Select Program

TabFlux . Data Structure and Algorithms . TU . BCT