Data Structure and Algorithms

Course Title: Data Structure and Algorithms

Course No: CSIT.121

Nature of the Course: Theory + Lab

Semester: 2

Full Marks: 60 + 40

Pass Marks: 24 + 20

Credit Hours: 3

Course Description

Study of basic data structure vocabulary and the concept of an algorithm.

Course Objectives

To introduce, fundamental data structures and problem solving paradigms. To introduce time complexity analysis of problems. To study the representation, implementation & applications of data structures. To compare alternative implementations of data structures. To choose the appropriate data structure for modeling a given problem.

Course Contents

1. Introduction to data structures

3 hrs

1.1. Preliminary data type and Abstract data type

1.2. Data structure, Need and Types of Data Structure

1.3. Comparison between ADT and Data Structure

1.4. Review of Array, Structure and Pointer

2. Algorithm analysis

2 hrs

2.1. Algorithm – definition, characteristics

2.2. Algorithm vs. Program

2.3. Space complexity, time complexity

2.4. Asymptotic notations (Big O, Omega Ω, Big Θ)

3. Array Data Structure

8 hrs

3.1. Introduction to Arrays - array representation

3.2. Advantages and Drawbacks of Arrays

3.3. Sorting algorithms with efficiency

Bubble sort

Selection sort

Insertion sort

Merge sort

Quick Sort

Heap Sort

Radix sort

Bucket Sort

Concept of stable and unstable sorting

3.4. Searching Algorithms

Linear Search

Binary Search

4. Linked List

10 hrs

4.1. Introduction to Linked List Data Structure

4.2. Implementation of List – static & dynamic representation

4.3. Types of Linked List

Singly Linked List

Circular Linked List

Doubly Linked List

Doubly circular Linked List

4.4. Operations on List

Insertion

Deletion

Searching

Merging

4.5. Applications of Linked List – polynomial manipulation

4.6. Generalized linked list – concept & representation

5. Stacks

7 hrs

5.1. Introduction: Definition, Stack as ADT

5.2. Operations on stack

5.3. Implementation of Stack

Using Arrays

Using Linked List

5.4. Application

Infix to postfix & prefix

Postfix evaluation

Bracket matching

Recursion

5.5. Concept of Multiple stacks

6. Queues

6 hrs

6.1. Introduction: Definition, Queue as ADT

6.2. Operations on Queue

6.3. Implementation of Queue

Using Arrays

Using Linked List

6.4. Applications- Printing, Scheduling etc

6.5. Circular queue, Dequeue, Priority Queues

6.6. Concept of Multiple Queues

7. Trees

6 hrs

7.1. Concept & Terminologies

7.2. Binary tree, Binary Search Tree

7.3. Implementation of Trees

Static

Dynamic

7.4. Operations on BST

Create

Insert

Delete

Traversals (preorder, inorder, postorder)

Counting leaf, non-leaf & total nodes

7.5. Balanced Trees

AVL trees and Rotations

Red Black Trees

7.6. Applications: Expression tree

8. Graph

6 hrs

8.1. Concept & terminologies

8.2. Graph Representation

8.3. Traversals – BFS & DFS

8.4. Minimum Spanning Trees: Kruskals Algorithm

8.5. Shortest Path Algorithms: Dijkstra Algorithm

Laboratory Works

Students will have to complete the assigned practical work throughout the semester and Practical examination will be conducted at the end of academic semester. The practical exam will be graded on the basis of the following marking scheme: In-Semester Evaluation 25%, Final Exam Written 50%, Final Exam Oral 25%.

1.Sorting Algorithms
2.Stack Implementation
3.Queue Implementation
4.Linked Lists
5.Polynomial Addition
6.Binary Tree Traversal
7.Graph Operations
8.Dijkstra Algorithm
9.Matrix Conversion

Text Books

1.Horowitz Sahani, Fundamentals of Data Structures, Galgotia Publication
2.Data Structure Using C & C++, Langsam Yedidyah, Augenstein Moshe J., Tennenbaum Aaron M., PHI
3.ISRD Group, Data Structures using C, Tata McGraw Hill
4.Nitin Upadhyay, SK, The Design and Analysis of Algorithm, Kataria & Sons
5.Ashok Kamthane, Introduction to Data Structures using C
6.Bandopadhyay & Dey, Data Structures using C, Pearson

Notes:

This syllabus follows the official CSIT curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://cdc.fwu.edu.np/faculties.html

Data Structure and Algorithms

Data Structure and Algorithms

Select University

Select Program

TabFlux . Data Structure and Algorithms . FWU . BSc. CSIT