Data Structures

GANPAT UNIVERSITY 

FACULTY OF ENGINEERING & TECHNOLOGY

Programme

Bachelor of Technology

Branch/Spec.

Computer  Science & Engineering (CBA/CS/BDA)

Semester

III

Version

1.1.1.1

Effective from Academic Year

2022-23

Effective for the batch Admitted in

June 2021

Subject  code

2CSE302

Subject 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

0

5

Theory 

40

60

100

Hours

3

0

4

0

7

Practical

60

40

100

Pre-requisites:

C Programming 

Learning Outcome:

After completion of the course, student will be able to:

• Learn different types of Linear data structures
• Understand different types of Non Linear data structures
• Apply appropriate data structure for solving typical computing problems

• Apply sorting and searching algorithms on small and large data sets

Theory syllabus

Unit

Content

Hrs.

1

LINEAR DATA STRUCTURES

Array: Operations, RMO and CMO  representation, Stack:  Concepts and representation, Operations, Applications. Polish Expression, Reverse Polish Expression And Their Compilation, Recursion, Tower of Hanoi, Queue, Operations, Types viz. Applications of queue. Linked List: Concept and Representation,Operations,  Types of Linked lists

15

2

NONLINEAR DATA STRUCTURES

Tree: Definitions and Concepts, Representation of binary tree, Binary tree traversal (Inorder, postorder, preorder), Threaded binary tree, Binary search trees, Conversion of General Trees To Binary Trees, Applications Of Trees- Some balanced tree mechanism, e.g. AVL trees, 2-3 trees

10

3

GRAPH

Basic Concept of Graph Theory and its Properties, Matrix Representation Of Graphs, Elementary Graph operations, Breadth First Search, Depth First Search, Spanning Trees, Minimum spanning tree- Prims and Kruskal Algorithm

6

4

SORTING & SEARCHING

Performance Analysis and Management - Time and space analysis of algorithms – Average, best and worst case analysis. Sorting – Bubble Sort, Selection Sort, Quick Sort, Merge Sort, Insertion sort, Heap Sort. Searching – Sequential Search and Binary Search

8

5

HASHING : 

Hashing function, Collision Resolution Techniques.

6

Self-Study

Conversion of General Trees To Binary Trees, Heap Sort

Practical content

Practicals will be based on topics such as arrays, strings, stacks, queues, linked lists, graphs, trees, sorting and searching.

Mooc Course

Course Name: Programming, data structures and algorithms using Python

Link: https://www.mygreatlearning.com/academy/learn-for-free/courses/data-structures-in-c

Text Books

1

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

2

Data Structure Using C by ReemaThareja, Oxford Higher Education

Reference Books

1

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

2

Fundamentals of Computer Algorithms by Horowitz, Sahni,Galgotia Pub

3

Data Structures: A Pseudo-code approach with C -By Gilberg & Forouzan Publisher- Thomson Learning

4

An Introduction to Data Structures with Applications. by Jean-Paul Tremblay & Paul G. Sorenson Publisher-Tata McGraw Hill

Course Outcomes:

COs

Description

CO1

Learn different types of Linear data structures

CO2

Understand different types of Non Linear data structures

CO3

Apply appropriate data structure for solving typical computing problems

CO4

Apply sorting and searching algorithms on small and large data sets.

Mapping of CO and PO: