Curriculum for Second Year of Computer Engineering (2019 Course), Savitribai Phule Pune University

Savitribai Phule Pune University

Home
Second Year of Computer Engineering (2019 Course)
210242: Fundamentals of Data Structures
Teaching Scheme Credit Scheme Examination Scheme and Marks
Lecture: 03 Hours/Week 03 Mid_Semester(TH): 30 Marks
End_Semester(TH): 70 Marks
Prerequisite Courses : 110005: Programming and Problem Solving
Companion Course : 210247: Data Structures Laboratory
Course Objectives:
The course is intended to provide the foundations of the practical implementation and usage of Data
Structures and Algorithms to ensure that the learner evolves into a competent programmer capable
of designing and analyzing implementations of data structures and algorithms for different kinds of
problems.
 To understand the standard and abstract data representation methods.
 To acquaint with the structural constraints and advantages in usage of the data.
 To understand various data structures, operations on it and the memory requirements
 To understand various data searching and sorting methods.
 To understand various algorithmic strategies to approach the problem solution.
Course Outcomes:
On completion of the course, learner will be able to–
CO1: Design the algorithms to solve the programming problems, identify appropriate algorithmic
strategy for specific application, and analyze the time and space complexity.
CO2: Discriminate the usage of various structures, Design/Program/Implement the appropriate
data structures; use them in implementations of abstract data types and Identity the
appropriate data structure in approaching the problem solution.
CO3: Demonstrate use of sequential data structures- Array and Linked lists to store and process
data.
CO4: Understand the computational efficiency of the principal algorithms for searching and
sorting and choose the most efficient one for the application.
CO5: Compare and contrast different implementations of data structures (dynamic and static).
CO6: Understand, Implement and apply principles of data structures-stack and queue to solve
computational problems.
Course Contents
Unit I Introduction to Algorithm and Data Structures (07 Hours)
Introduction: From Problem to Program (Problem, Solution, Algorithm, Data Structure and Program).
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 Multiplication technique by the mathematician Carl Friedrich Gauss and
Studies Karatsuba algorithm for fast multiplication.
*Mapping of Course CO1, CO2
Outcomes for Unit I

#11/87
http://collegecirculars.unipune.ac.in/sites/documents/Syllabus2020/Forms/AllItems.aspx
 Curriculum for Second Year of Computer Engineering (2019 Course), Savitribai Phule Pune University

Unit II Linear Data Structure Using Sequential (07 Hours)

Home
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 Study use of sparse matrix in Social Networks and Maps.
Studies 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 CO1, CO2, CO3
Outcomes for Unit II
Unit III Searching and Sorting (07 Hours)
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 Use of Fibonacci search in non-uniform access memory storage and in
Studies Optimization of Unimodal Functions. Timsort as a hybrid stable sorting
algorithm
*Mapping of Course CO1, CO2, CO4
Outcomes for Unit III
Unit IV Linked List (07 Hours)
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 Garbage Collection
Studies
*Mapping of Course CO1, CO2, CO3, CO5
Outcomes for Unit IV
Unit V Stack (07 Hours)
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 Android- multiple tasks/multiple activities and back-stack, Tower of Hanoi, 4
Studies Queens problem.
*Mapping of Course CO1, CO2, CO3, CO5, CO6
Outcomes for Unit V

#12/87
http://collegecirculars.unipune.ac.in/sites/documents/Syllabus2020/Forms/AllItems.aspx
 Curriculum for Second Year of Computer Engineering (2019 Course), Savitribai Phule Pune University

Unit VI Queue (07 Hours)

Home
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 Priority queue in bandwidth management
Studies
*Mapping of Course CO1, CO2, CO3, CO5, CO6
Outcomes for Unit VI
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. Steven S S. Skiena, “The Algorithm Design Manual”, Springer, 2nd ed. 2008 Edition, ISBN-
13: 978-1849967204, ISBN-10: 1849967202.
2. Allen Downey, Jeffery Elkner, Chris Meyers, “How to think like a Computer Scientist: Learning
with Python”, Dreamtech Press, ISBN: 9789351198147.
3. M. Weiss, “Data Structures and Algorithm Analysis in C++”, 2nd edition, Pearson Education,
2002, ISBN-81-7808-670-0.
4. Brassard and Bratley, “Fundamentals of Algorithmic”, Prentice Hall India/Pearson Education,
ISBN 13-9788120311312.
5. Yashwant Kanetkar & A. Kanetkar, “Let us Python”, BPB Publisher, ISBN: 9789389845006
e-Books:
 https://www.ebooks.com/en-us/book/95777110/Python-data-structures-and-algorithms/benjamin-baka/
 https://www.ebookphp.com/advanced-data-structures-epub-pdf/
 https://www.ebookphp.com/data-structures-and-algorithms-professional-edition-beginners-guide-epub-
pdf/
MOOC Links/Video Lectures available at:
 https://nptel.ac.in/courses/106/102/106102064/
 https://nptel.ac.in/courses/106/105/106105085
 https:// nptel.ac.in/courses/106/106/106106127
Other:
3. Know Thy Complexities! (https://www.bigocheatsheet.com/)
(https://github.com/RehanSaeed/.NET-Big-O-Algorithm-Complexity-Cheat-Sheet)
@The CO-PO Mapping Matrix
CO\PO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CO1 2 2 1 2 - - - - - - - -
CO2 1 2 2 1 - - - - - - - -
CO3 1 1 1 - - - - - - - - -
CO4 1 - 1 - - - - - - - - -
CO5 1 1 - 1 - - - - - - - -
CO6 1 1 1 1 1 - - - - - - -

#13/87
http://collegecirculars.unipune.ac.in/sites/documents/Syllabus2020/Forms/AllItems.aspx