DS - Data Structures using C Syllabus

 Semester: II

 Data Structures using C 

Content Hours

Unit - 1

Introduction to data structures: Definition; Types of data structures - Primitive & Non-primitive,

Linear and Non-linear; Operations on data structures.

Algorithm Specification, Performance Analysis, Performance Measurement

Recursion: Definition; Types of recursions; Recursion Technique Examples - Fibonacci numbers,

GCD, Binomial coefficient nCr, Towers of Hanoi; Comparison between iterative and recursive

functions.

10 Hrs

Unit - 2

Arrays: Basic Concepts – Definition, Declaration, Initialisation, Operations on arrays; Types of

arrays; Arrays as abstract data types (ADT); Representation of Linear Arrays in memory;

Traversing linear arrays; Inserting and deleting elements; Sorting – Selection sort, Bubble sort, Quick

sort, Selection sort, Insertion sort; Searching - Sequential Search, Binary search; Iterative and

Recursive searching; Multidimensional arrays; Representation of multidimensional arrays; Sparse

matrices. 10 Hrs

Unit - 3

Dynamic memory allocation: Static & Dynamic memory allocation; Memory allocation and de-

allocation functions - malloc, calloc, realloc and free.

Linked list: Basic Concepts – Definition and Representation of linked list, Types of linked lists -

Singly linked list, Doubly liked list, Header liked list, Circular linked list; Representation of Linked

list in Memory;

Operations on Singly linked lists – Traversing, Searching, Insertion, Deletion; Memory allocation;

Garbage collection,

12

Unit - 4

Stacks: Basic Concepts – Definition and Representation ofstacks; Operations on stacks; Applications

of stacks; Infix, postfix and prefix notations; Conversion from infix to postfix using stack; Evaluation

of postfix expression using stack; Application of stack in function calls.

Queues: Basic Concepts – Definition and Representation of queues; Types of queues - Simple

queues, Circular queues, Double ended queues, Priority queues; Operations on Simple queues;

10 Hrs

Unit - 5

Trees: Definition; Tree terminologies –node, root node, parent node, ancestors of a node, siblings,

terminal & non-terminal nodes, degree of a node, level, edge, path, depth;

Binary tree: Type of binary trees - strict binary tree, complete binary tree, binary search tree and

heap tree; Array representation of binary tree. Traversal of binary tree; preorder, inorder and

postorder traversal; Reconstruction of a binary tree when any two of the traversals are given.

10 Hrs

Text Books

1. Satraj Sahani: Fundamentals of Data Structures

References

1. Tanenbaum: Data structures using C (Pearson Education)

2. Kamathane: Introduction to Data structures (Pearson Education)

3. Y. Kanitkar: Data Structures Using C (BPB)

4. Kottur: Data Structure Using C

5. Padma Reddy: Data Structure Using C

6. Sudipa Mukherjee: Data Structures using C – 1000 Problems and Solutions (McGraw Hill

Education, 2007))

LAB SYLLABUS 

 Course Title: Data Structures Lab Course code: 21BSDSC2P

Total Contact Hours: 42 Course Credits: 02

Formative Assessment Marks: 25 Duration of SEE/Exam: 03 Hours

Summative Assessment Marks: 25

Programming Lab

Part A:

1. Write a C Program to find GCD using recursive function

2. Write a C Program to display Pascal Triangle using binomial function

3. Write a C Program to generate n Fibonacci numbers using recursive function.

4. Write a C Program to implement Towers of Hanoi.

5. Write a C Program to implement dynamic array, find smallest and largest element of the

array.

6. Write a C Program to create two files to store even and odd numbers.

7. Write a C Program to create a file to store student records.

8. Write a C Program to read the names of cities and arrange them alphabetically.

9. Write a C Program to sort the given list using selection sort technique.

10. Write a C Program to sort the given list using bubble sort technique.

Part B:

1. Write a C Program to sort the given list using insertion sort technique.

2. Write a C Program to sort the given list using quick sort technique.

3. Write a C Program to sort the given list using merge sort technique.

4. Write a C Program to search an element using linear search technique.

5. Write a C Program to search an element using recursive binary search technique.

6. Write a C Program to implement Stack.

7. Write a C Program to convert an infix expression to postfix.

8. Write a C Program to implement simple queue.

9. Write a C Program to implement linear linked list.

10. Write a C Program to display traversal of a tree.