210242: Fundamentals of Data Structures

Credit 03

Unit I Introduction to Algorithm and Data Structures
Introduction: From Problem to Data Structure (Problem, Logic, Algorithm, and Data Structure).
Data Structures: Data, Information, Knowledge, and Data structure, Abstract Data Types (ADT), Data
Structure Classification (Linear and Non-linear, Static and Dynamic, Persistent and Ephemeral data
structures)
Algorithms: Problem Solving, Introduction to algorithm, Characteristics of algorithm, Algorithm design
tools: Pseudo-code and flowchart
Complexity of algorithm: Space complexity, Time complexity, Asymptotic notation- Big-O, Theta and
Omega, Finding complexity using step count method, Analysis of programming constructs-Linear,
Quadratic, Cubic, Logarithmic.
Algorithmic Strategies- Introduction to algorithm design strategies- Divide and Conquer, and Greedy
strategy.
#Exemplar/Case Studies Multiplication technique by the mathematician Carl Friedrich Gauss and Karatsuba algorithm for fast multiplication.

Mapping of Course Outcomes for Unit I CO3, CO5, CO6

Unit II Linear Data Structure Using Sequential Organization
Concept of Sequential Organization, Overview of Array, Array as an Abstract Data Type, Operations
on Array, Merging of two arrays, Storage Representation and their Address Calculation: Row major
and Column Major, Multidimensional Arrays: Two-dimensional arrays, n-dimensional arrays. Concept
of Ordered List, Single Variable Polynomial: Representation using arrays, Polynomial as array of
structure, Polynomial addition, Polynomial multiplication. Sparse Matrix: Sparse matrix
representation using array, Sparse matrix addition, Transpose of sparse matrix- Simple and Fast
Transpose, Time and Space tradeoff.
#Exemplar/Case Studies Study use of sparse matrix in Social Networks and Maps. Study how Economists use polynomials to model economic growth patterns, how medical researchers use them to describe the behaviour of Covid-19 virus.

Mapping of Course Outcomes for Unit II CO1, CO2, CO3

Unit III Searching and Sorting
Searching: Search Techniques-Sequential Search/Linear Search, Variant of Sequential Search- Sentinel
Search, Binary Search, Fibonacci Search, and Indexed Sequential Search.
Sorting: Types of Sorting-Internal and External Sorting, General Sort Concepts-Sort Order, Stability,
Efficiency, and Number of Passes, Comparison Based Sorting Methods-Bubble Sort, Insertion Sort,
Selection Sort, Quick Sort, Shell Sort, Non-comparison Based Sorting Methods-Radix Sort, Counting
Sort, and Bucket Sort, Comparison of All Sorting Methods and their complexities.
#Exemplar/Case Studies Use of Fibonacci search in non-uniform access memory storage and in Optimization of Unimodal Functions. Timsort as a hybrid stable sorting algorithm

Mapping of Course Outcomes for Unit III CO1, CO3, CO4

Unit IV Linked List
Introduction to Static and Dynamic Memory Allocation, Linked List: Introduction, of Linked Lists,
Realization of linked list using dynamic memory management, operations, Linked List as ADT, Types
of Linked List: singly linked, linear and Circular Linked Lists, Doubly Linked List, Doubly Circular Linked
List, Primitive Operations on Linked List-Create, Traverse, Search, Insert, Delete, Sort, Concatenate.
Polynomial Manipulations-Polynomial addition. Generalized Linked List (GLL) concept, Representation
of Polynomial using GLL.
#Exemplar/Case Studies Garbage Collection
Mapping of Course Outcomes for Unit IV CO1, CO2, CO5

Unit V Stack
Basic concept, stack Abstract Data Type, Representation of Stacks Using Sequential Organization,
stack operations, Multiple Stacks, Applications of Stack- Expression Evaluation and Conversion, Polish
notation and expression conversion, Need for prefix and postfix expressions, Postfix expression
evaluation, Linked Stack and Operations. Recursion- concept, variants of recursion- direct, indirect,
tail and tree, Backtracking algorithmic strategy, use of stack in backtracking.
#Exemplar/Case Studies Android- multiple tasks/multiple activities and back-stack, Tower of Hanoi, 4 Queens problem.

Mapping of Course Outcomes for Unit V CO1, CO2, CO5, CO6

Unit VI Queue
Basic concept, Queue as Abstract Data Type, Representation of Queue using Sequential organization,
Queue Operations, Circular Queue and its advantages, Multi-queues, Linked Queue and Operations.
Deque-Basic concept, types (Input restricted and Output restricted), Priority Queue- Basic concept,
types(Ascending and Descending).
#Exemplar/Case Studies Priority queue in bandwidth management
Mapping of Course Outcomes for Unit VI CO1, CO2, CO5, CO6

Learning Resources

Text Books:
1. Horowitz and Sahani―Fundamentals of Data Structures in C++, University Press, ISBN 10:
0716782928 ISBN 13: 9780716782926.
2. Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, Data Structures and
Algorithms in Python, Wiley Publication, ISBN: 978-1-118-29027-9
Reference Books:
1. Brassard & Bratley ―Fundamentals of Algorithmic Prentice Hall India/Pearson Education, ISBN
13-9788120311312.
2. Allen Downey, Jeffery Elkner, Chris Meyers-How to think like a Computer Scientist: Learning
with Python, Dreamtech Press, ISBN:9789351198147.
3. R. Gillberg, B. Forouzn ―Data Structures: A Pseudo code approach with C, Cenage Learning,
ISBN: 9788131503140.
4. M. Weiss―Data Structures and Algorithm Analysis in C++, 2nd edition, Pearson Education,
2002, ISBN-81-7808-670-0.