SEMESTER II

Course Code Course Name L T P C

CSEG1043
Data Structures and Algorithms 4 0 1 5
Total Units to be Covered: 6 Total Contact Hours: 90
Prerequisite(s): Programming in C-CSEG 1025 Syllabus version: 1.0

Course Objectives
1. Provide a clear understanding of the importance of data structures in organizing
and manipulating data efficiently.
2. To introduce students to fundamental data structures and the properties,
memory management, and basic operations of each data structure.
3. To offer practical experience in implementing data structures, common sorting,
and searching algorithms.
4. Emphasize the use of data structures as tools for algorithmic problem-solving
and apply their knowledge of data structures to solve real-world problems.

Course Outcomes

Upon completion of the course, the students will be able to

CO 1. State the significance and properties of the fundamental data structures.

CO 2. Implement common data structures while ensuring proper memory
management and error handling.
CO 3. Illustrate expertise in understanding the common sorting and searching
techniques with their complexities and implement them.
CO 4. Analyse real-world problems by understanding the trade-offs involved in
identifying the appropriate data structure(s) based on problem
requirements and using them to solve the problems efficiently.

CO-PO Mapping

Program
Outcomes
Course PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3
Outcomes

56
CO 1 1 - 2 1 - - - - - - - 1 - - -
CO 2 1 1 2 1 - - - - - - - - - - -
CO 3 1 1 2 1 - - - - - - - 2 - - -
CO 4 1 2 2 2 - - - - - - - 2 - - -
- - - - - - - - - -
Average 1 1 2 1.25 1.25

1 Weakly Mapped (Low) 2 Moderately Mapped (Medium)

3 Strongly Mapped (High)

Syllabus

Unit I: INTRODUCTION 12 Lecture Hours

Overview, classification, and Importance of data structures in Programming/problem-

solving, Basic terminology, and concepts: elements, operations, storage, memory
allocation, garbage collection, and compaction. Iterative & Recursive approaches.
Basic analysis of algorithms: Amortized analysis and Asymptotic Analysis. Array:
Memory representation (1D and 2D), Array operations: insertion, deletion, searching.
Applications of Array. Structure: Nested Structure, Function pointer as member of a
structure, Self-referential structure. Anonymous Unions, ADTs.

Unit II: LINKED LIST 10 Lecture Hours

Singly-Linked List, Doubly-Linked List, Circular Linked List, Header List, and its
operations. Sentinel node. Generalized Linked List. Skip List. Applications of Linked
Lists: polynomial manipulation, implementation of other data structures.

Unit III: STACK & QUEUE 10 Lecture Hours

Stack data structure and operations. Queue data structure and operations.
Implementation of Stack and Queue using Array and Linked List. Circular Queue.
Deque and its types. Priority Queue. Applications: Stacks (Conversion of Infix to

57
Prefix/Postfix, Expression evaluation, a note on DFS in graph), Queues (Job
scheduling, a note on BFS in graph).

Unit IV: TREE 10 Lecture Hours

Introduction to Tree data structure and its terminologies, Binary Tree: properties,
traversal algorithms (level-order, in-order, pre-order, post-order). Threaded Binary
Tree. Binary Search Trees (BST): properties, operations (insertion, deletion,
searching). Balanced BSTs. AVL Tree: properties, rotations, operations (insertion,
deletion). Red-Black Tree. Multi-way search Tree: properties. B-Tree: properties,
operations (search, insertion, and deletion). Applications of AVL Tree and B-Tree.
Binary Heaps: properties, heapify operations, Heap sorting.

Unit V: HASH TABLE & GRAPH 10 Lecture Hours

Hashing and hash functions. Hash table data structure: structure, collisions, collision
resolution techniques, maintaining load factor. Applications of hash tables:
dictionaries, symbol tables.
Introduction to graph data structure and its terminologies. Graph representations:
adjacency matrix, adjacency list. Graph traversal algorithms: depth -first search,
breadth-first search (BFS). Connected Components. Minimum spanning tree. Shortest
path.

Unit VI: SORTING & SEARCHING 8 Lecture Hours

Stability and In-place properties, Internal and external sorting. Simple comparison -
based sorting algorithms: bubble sort, selection sort, insertion sort. Lower bound for
comparison-based sorting algorithms. Recursive implementation of merge sort,
quicksort, and binary search. Complexities of common sorting and searching
algorithms.

Total lecture Hours 60

58
References*

Textbooks 1. S. Lipschutz, "Data Structures with C",

Schaum's Outline Series, McGraw-Hill
Education (India) Pvt. Limited, 2017.
2. Y. P. Kanetkar, "Data structures through
C", 4rd Edition, New Delhi: BPB, 2022.
Reference books 1. A. V. Aho, J. E. Hopcroft, and J. D.
Ullman, "Data Structures and Algorithms",
New Delhi: Pearson Education, 2003.
2. E. Horowitz, and S. Sahni,
"Fundamentals of Data Structures in C",
2nd Edition, Hyderabad: University Press,
2008.
Web Resources
Journals
MOOCs, online courses

Modes of Evaluation: Quiz/Assignment/ presentation/ extempore/ Written

Examination etc.
Examination Scheme
Components IA MID SEM End Sem Total
Weightage (%) 50 20 30 100

59
 Data Structures and Algorithms Lab

List of Experiments

Experiment 1: Basic Data Structure

To demonstrate the use of array, structure, and union along with dynamic memory
allocation.
Experiment 2: Link List Data Structure and its Applications
To experiment with the concept of pointers, structure, and dynamic memory allocation
to realize linked lists, their types, and application.
Experiment 3: Stack Data Structure
To use arrays and linked lists to implement Stack and its applications.
Experiment 4: Queue Data Structure
To demonstrate the use of arrays and linked lists to implement different variants of
Queue and its applications.
Experiment 5: Trees
To demonstrate the creation of a binary tree and working with tree traversal.
Experiment 6: Heaps
To create a heap data structure and implement its operations, and its applications.
Experiment 7: Hash Tables
To implement a hash table using various collision resolution techniques, and its
applications.
Experiment 8: Graphs
To demonstrate the creation of graphs and working with graph traversal algorithms.
Experiment 9: Sorting algorithms
To implement common sorting algorithms.
Experiment 10: Searching algorithms
To implement various search algorithms on data structures.

Total Lab hours 30

60
References*

Textbooks 1. S. Lipschutz, "Data Structures with C",

Schaum's Outline Series, McGraw-Hill
Education (India) Pvt. Limited, 2017.
2. Y. P. Kanetkar, "Data structures through
C", 4rd Edition, New Delhi: BPB, 2022.
Reference books 1. A. V. Aho, J. E. Hopcroft, and J. D.
Ullman, "Data Structures and Algorithms",
New Delhi: Pearson Education, 2003.
2. E. Horowitz, and S. Sahni,
"Fundamentals of Data Structures in C",
2nd Edition, Hyderabad: University Press,
2008.
Web Resources
Journals
MOOCs, online courses

Modes of Evaluation: Quiz/Assignment/ presentation/ extempore/ Written

Examination etc.
Examination Scheme: Continuous Assessment

Components Quiz & Viva Performance & Lab Report

Weightage (%) 50 50

61