Syllabus - Data Structure (CSIT303)

Computer Science & Information Technology

Data Structure (CSIT303)

III-Semester

Unit 1

Introduction

Data, data type, data object. Types of data structure – primitive & non-primitive , linear & non-linear. Operations on data structures – traversing, searching , inserting , deleting. Complexity analysis – worst case, best case, average case. Time – space trade off , algorithm efficiency, asymptotic notations – big oh , omega , theta.

Unit 2

Arrays & Structure

Introduction , declaration of arrays , operations on arrays – inserting , deleting , merging of two arrays , 1 dimensional & 2 dimensional arrays, row & column major representation , address calculation in array , storing values in arrays , evaluation of polynomial – addition & representation. Searching & sorting – Introduction , sequential search, binary search , Fibonacci search , indexed sequential search, hashed search. Types of sorting with general concepts – bubble, heap , insertion , selection, quick , heap , shell , bucket , radix and merge sort.

Unit 3

Stacks & Queues

Basic concept of stacks & queues, array representation of stacks, operation on stacks – Push , Pop , Create , getTop , empty , linked representation of stack , multiple stack. Application of stack – Conversion: infix , prefix , postfix and evaluation of arithmetic expression. Linked representation of queue, operations on queue – insertion & deletion. Types of queue with functions – circular , deque , priority queue. Applications of queues – Job scheduling , Josephus problem.

Unit 4

Linked List

Introduction – basic terminology, memory allocation & deallocation for linked list. Linked list variants – head pointer , head node , types linked list – linear & circular linked list. Doubly linked list , creation of doubly list, deletion of node from doubly linked list, insertion of a node from doubly linked list, traversal of doubly linked list. Circular linked list – singly circular linked list , circular linked list with header node , doubly circular linked list. Applications of linked list – polynomial representation & garbage collection.

Unit 5

Trees

Basic terminology – general tree , representation of general tree, types of trees, binary tree- realization and properties , traversal in binary trees – inorder , preorder , postorder , applications of trees. Graph- Basic Terminologies and representations, Graph search and traversal algorithms.

Course Objective

The main objectives of this course are: CSIT303 Data Structure 1. To introduce the concepts of linear, non-linear data structures , the operations performed on them and the applications of various data structures. 2. To introduce various algorithms of searching and sorting. 3. To understand the basic concepts of stacks, queues, linked lists, trees and graphs 4. To enable students to write algorithms for solving various problems using data structures.

Course Outcome

On completion of the course: 1. For a given search problem (linear search and binary search) student will be able to implement it. 2. For a given problem of stacks, queues and link lists, students will be able to implement it and analyze the same to determine the time and computation complexity 3. Students will be able to write an algorithm for selection sort, insertion sort, quick sort, merge sort, heap sort, bubble sort and compare their performance 4. Students will be able to implement tree, graph search and traversal algorithms

Practicals

  • Write a program to search an element in the array using Linear and Binary Search.

  • Write a program to perform the following operation in Matrix: 1. Addition 2. Subtraction 3. Multiplication 4. Transpose

  • Write a program to perform the following operation on strings using string functions: 1. Addition 2. Copying 3. Reverse 4. Length of String

  • Write program for implementing the following sorting methods to arrange a list of integers in ascending order: a) Quick sort b) Selection sort c) Insertion sort d) Merge sort

  • Write a program that uses stack operations to convert a given infix expression into its postfix equivalent.

  • Write a program to merge two sorted array into one sorted array.

  • Write a program to implement stack using array and linked list.

  • Write a program to implement queue and circular queue using array.

  • Write a program to insert an element in the beginning and end of singly linked list.

  • Write a program to insert an element at any position in singly and doubly linked list.

  • Insert and delete a node at any position in doubly linked list.

  • Write a program of Tower of Hanoi.

  • Write a program that uses functions to perform the following: a) Create a binary search tree of integers. b) Traverse the above Binary search tree non recursively in in order.

Reference Books

  • Varsha H. Patil “Data Structure Using C++” Oxford.

  • Rajesh K. Shukla “Data Structures Using C & C++” Wiley India.

  • Reema Thareja “ Data Structure Using C ” Oxford.

  • Aho, Hopcroft, Ullman, “Data Structures and Algorithms”, Pearson Education.

  • Kushwaha and Mishra “Data Structure: A programming Approach with C”, PHI Learning.

  • A. K Sharma “Data Structure Using C” Pearson.

  • Ellis Horowitz, Sartaj Sahni, “Fundamentals of Data Structures”, Computer Science Press