DATA STRUCTURES

GANPAT UNIVERSITY

FACULTY OF ENGINEERING & TECHNOLOGY

Programme

Bachelor of Technology

Branch/Spec.

Computer Engineering,

Information Technology,

Computer Engineering (Artificial Intelligence)

Semester

III

Version

2.0.0.1

Effective from Academic Year

2023-24

Effective for the Batch admitted in

July 2022

Course Code

2CEIT304

Course Name

Data Structures

Teaching Scheme

Examination Scheme (Marks)

(Per week)

Lecture (DT)

Practical (Lab.)

Total

CE

SEE

Total

L

TU

P

TW

Credit

3

0

2

-

5

Theory

40

60

100

Hours

3

0

4

-

7

Practical

30

20

50

Pre-requisites

Course on Programming for Problem Solving.

Course Outcomes

On successful completion of the course, the students will be able to:

CO1

Explain the basics of data structures and its relevance to real world application.

CO2

analyze and apply the suitable linear data structures according to scope of the problem.

CO3

analyze and design the solution of  real world problem using appropriate Non-linear data structures

CO4

examine, test and compare the appropriate sorting and searching techniques on real time data.

Theory Syllabus

Unit

Content

Hrs.

1

Introduction to data structure:

Basic concepts C languages: Introduction to Structures and Pointers. Importance and applications of data structures, Types of data structures, Algorithms and Asymptotic notations.

03

2

Stack:

Definition & Concepts, Operations on Stacks (Push, Pop, Peep, Change -Algorithm & Implementation), Applications of Stack, Polish expressions, Reverse Polish Expression and conversions, Recursion, Tower of Hanoi problem.

06

3

Queue:

Queue and its sequential representation, Simple Queue, Circular Queue, Double Ended Queue, Priority Queue, Applications of Queue.

04

4

Linked List:

Sequential Allocation method Vs linked Allocation method, Dynamic Data structure Vs Static Data structure, Pointers and Linked Allocation, Singly Linked List Storage Structures & Basic Operations, Circular Linked List & Basic Operations, Doubly Linked List & Basic Operations, Applications of Linked List.

08

5

Tree:

Definitions and concepts, Terminology, Binary trees, Binary Tree Representations, Binary Tree Traversals, Binary Search Tree, Insertion and Deletion in BST, Threaded binary Trees, AVL Tree, B-Tree, Introduction to B+ Tree, Applications of Tree.

10

6

Graph:

Definition and concepts, Graph Representation, Graph Terminology, Graph Traversals – Depth First Search and Breadth First Search, Shortest Path- Dijkstra’s Algorithm.

06

7

Sorting and Searching: 

Introduction to Sorting, Types of Sorting(Internal and External, Stable and Un-stable Sorting) Elementary sorts: Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort, Heap Sort, Radix sort, Sequential Search, Binary search, Best case and worst case behaviour.

06

8

Hashing:

The symbol table, Hashing Functions, Fundamentals of Collision-Resolution Techniques.

02

Practical Content

Practical, assignments and tutorials are based on the syllabus. Few practicals will be performed in C++.

Text Books

1

An Introduction to Data Structures with Application, By Jean-Paul Tremblay ,Paul G. Sorenson.

Reference Books

1

Data Structures using C & C++ -By Ten Baum Publisher – Prentice-Hall International.

2

Fundamentals of Computer Algorithms By Horowitz, Sahni, Galgotia

3

Fundamentals of Data Structures in C++ By Sartaj Sahani,

ICT/MOOCs Reference

1

https://nptel.ac.in/courses/106102064/

2

https://nptel.ac.in/courses/106103069/

Mapping of CO with PO and PSO:

PO1

PO2

PO3

PO4

PO5

PO6

PO7

PO8

PO9

PO10

PO11

PO12

PSO1

PSO2

PSO3

CO1

3

3

2

3

1

0

0

0

1

1

1

2

3

2

1

CO2

3

3

3

3

3

0

0

0

2

1

3

2

2

3

1

CO3

3

3

3

2

2

0

0

0

2

1

1

2

2

2

2

CO4

3

3

3

2

2

0

0

0

2

1

2

2

2

2

1