w.e.
f Academic Year 2012-13
G Scheme
Course Name
: Computer Engineering Group
Course Code
: CO/CM/IF/CD/CW
Semester
: Third
Subject Title
: Data Structure Using C
Subject Code
: 17330
Teaching and Examination Scheme:
Teaching Scheme
Examination Scheme
TH
TU
PR
PAPER
HRS
TH
PR
OR
TW
TOTAL
04
--
04
03
100
50#
--
25@
175
NOTE:
Two tests each of 25 marks to be conducted as per the schedule given by MSBTE.
Total of tests marks for all theory subjects are to be converted out of 50 and to be entered in
mark sheet under the head Sessional Work. (SW)
Rationale:
Data structure is a subject of primary importance to the discipline of Computer Science &
Engineering. Data structure is a logical & mathematical model of storing & organizing data in a
particular way in a computer. After learning this subject student will be able to identify the
problem, analyze different algorithms to solve the problem & choose most appropriate data
structure to represent the data.
General Objectives:
The student will be able to:
Know the fundamentals of data structure
Classify data structures.
Select the appropriate data structure.
Apply the different searching and sorting techniques.
Apply different algorithms to solve the real world problem.
MSBTE Final Copy 14/01/2013
17330
w.e.f Academic Year 2012-13
G Scheme
Learning Structure:
Application
Procedure
Principles
Concepts
Programming (System & Application)
Searching
Sorting
Searching
Algorithms
Sorting
Algorithms
Linear
Binary
Facts
MSBTE Final Copy 14/01/2013
Data Access
Techniques
Bubble,
Selection,
Insertion,
Quick Sort,
Merge Sort,
Radix Sort.
FIFO
LIFO
Data Retrival
Data Storage
Techniques
Arrays, Stack,
list, Queue,
Graph
Insert, Delete,
Push, Pop,
Front, Rear,
Node, Pointers,
Data Storage
Identifiers, Data types, Data
17330
w.e.f Academic Year 2012-13
G Scheme
Contents: Theory
Topic
Content
Introduction to Data Structure
Specific Objective:
To understand data structure organization & classification
To understand operations on data structure.
To understand approaches to design an algorithm.
Knowing the complexity of an algorithm
1.1 Basic Terminology
Elementary data structure organization
Classification of data structure
1.2 Operations on data structures
Traversing, Inserting, deleting
Searching, sorting, merging
1.3 Different Approaches to designing an algorithm
Top-Down approach
Bottom-up approach
1.4 Complexity
Time complexity
Space complexity
1.5 Big O Notation
Sorting and Searching
Specific Objective:
To understand and apply sorting algorithms on data.
To understand and apply searching algorithms on data.
2.1 Sorting Techniques
Introduction
Selection sort
Insertion sort
Bubble sort
Merge sort
Radix sort ( Only algorithm )
Shell sort ( Only algorithm )
Quick sort ( Only algorithm )
2.2 Searching
Linear search
Binary search
Stacks
Specific Objective:
To understand and apply the knowledge of the data structure
stack in the application programs.
3.1 Introduction to stack
Stack as an abstract data type
Representation of stack through arrays
3.2 Applications of Stack
Reversing a list
Polish notations
Conversion of infix to postfix expression
Evaluation of postfix expression
MSBTE Final Copy 14/01/2013
Hours
Marks
06
08
10
16
12
18
17330
w.e.f Academic Year 2012-13
G Scheme
Converting an infix into prefix expression
Evaluation of prefix expression
Recursion
Queues
Specific Objective:
To understand and apply the knowledge of the data structure
Queue in the application programs.
4.1 Introduction
Queues as an abstract data type
Representation of a Queue as an array
4.2 Types of Queue
Circular Queue
Double Ended Queue
Priority Queue
Dequeues
4.3 Applications of Queue
Linked List
Specific Objective:
To understand and apply the knowledge of the data structure
Linked List in the application programs.
5.1 Introduction
Terminologies: node, Address, Pointer,
Information, Next, Null Pointer, Empty list etc.
5.2 Type of lists
Linear list
Circular list
Doubly list
5.3 Operations on a singly linked list ( only algorithm)
Traversing a singly linked list
Searching a linked list
Inserting a new node in a linked list
Deleting a node from a linked list
Trees
Specific Objective:
To understand and apply the knowledge of the data structure
Trees on data.
6.1 Introduction
Terminologies: tree ,degree of a node, degree of a tree, level of
a node, leaf node, Depth / Height of a tree, In-degree & outDegree, Directed edge, Path, Ancestor & descendant nodes.
6.2 Type of Trees
General tree
Binary tree
Binary search tree (BST).
6.3 Binary tree traversal ( only algorithm )
In order traversal
Preorder traversal
Post order traversal
6.4 Expression tree
MSBTE Final Copy 14/01/2013
08
12
08
12
12
18
17330
w.e.f Academic Year 2012-13
G Scheme
Graph and Hashing
Specific Objective:
To understand and apply the knowledge of graph and
hashing function on data.
7.1 Introduction
Terminologies: graph, node (Vertices), arcs (edge), directed
graph, in-degree, out-degree, adjacent, successor, predecessor,
relation, weight, path, length.
7.2 Representations of a graph
Array Representation
Linked list Representation
7.3 Traversal of graphs
Depth-first search (DFS).
Breadth-first search (BFS).
7.4 Applications of Graph
7.5 Hashing
Hash function
Collision resolution techniques
Total
08
16
64
100
Practical:
Skills to be developed:
Intellectual Skills:
1.
2.
3.
4.
Classify data structures.
Select the appropriate data structure.
Apply the different searching and sorting techniques.
Apply different algorithms to solve the real world problem.
Motor Skills:
1. Operate the computer system
List of Practical:
1. Perform insertion & deletion operation on one dimensional array.
2. Implement the searching of the given number in one dimensional array using linear
search and binary search methods.
3. Write a program to sort the given list represented using array in ascending order by
sorting techniques like bubble sort, insertion sort and selection sort.
4. Understand the concept of stack and implement PUSH and POP operations on stack
using array.
5. Understand the concept of Queue and implement insertion and deletion operation on
Queue using array.
6. Understand the concept of Link list and implement operations on Singly Link list.
MSBTE Final Copy 14/01/2013
10
17330
w.e.f Academic Year 2012-13
G Scheme
7. Understand how to create a Binary Tree.
8. Understand and create a graph of n vertices using an adjacency list.
9. Understand the concept of Hashing and write a program to search an element using
Hashing techniques
10. Seminar on mini study project.
Learning Resources:
1
Books:
Sr. No.
Author
1
ISRD Group New Delhi
Publisher
Tata McGraw Hill
Reema Thareja
Data Structure Using C
OXFORD University Press
Ashok Kamthane
Introduction to data structures
in C
Pearson
C & data structures
Dreamtech press
Data structures &
Algorithms Using C
Vikas
4
5
Title
Data structure Using C
Prof. P.S. Deshpande,
Prof D.G. kakde
Amitava Nag & Jyoti
Prakash Singh
Websites:
http://www.oupinheonline.com/book/thareja-data-structures-using-c/9780198065449
www.vikaspublishing.com/teachersmannual.aspx
www.pearsoned.co.in/prc
www.phindia.com/learningresources.aspx
3.
Mini Project:
Use any resources for mini projects in Data Structure.
MSBTE Final Copy 14/01/2013
11
17330
