Algorithms: Problem Solving, Introduction to algorithm, Characteristics of algorithm, Algorithm design tools: Pseudo-code and flowchart

Algorithms: Problem Solving, Introduction to algorithm, Characteristics of algorithm,  

Algorithm design tools: Pseudo-code and flowchart.

 

 

 

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)

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)

Syllabus of FDS (2019 Course) w.e.f Academic Year 2020-2021

Savitribai Phule Pune University 

Second Year of Computer Engineering (2019 Course) 

210242: Fundamentals of Data Structures (Theory)

 Unit I Introduction to Algorithm and Data Structures

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 Studies
Multiplication technique by the mathematician Carl Friedrich Gauss and Karatsuba algorithm for fast multiplication.

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.

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.

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.

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.

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.

Learning Resources

 Text Books: 

• Horowitz and Sahani, “Fundamentals of Data Structures in C++”, University Press, ISBN 10: 0716782928 ISBN 13: 9780716782926. 

• 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.

Group A Python Program for Matrix Addition, Substraction, Multiplication and Transpose

Problem Statement: 

Write a python program to compute following computation on matrix: 

a) Addition of two matrices 

b) Subtraction of two matrices 

c) Multiplication of two matrices 

d) Transpose of a matrix 

-------------------------------------------------------------------------------

Analysis of a Problem Statement: 

1. Given :

  Matrices are given in a problem statement.

2. Entity: 

  Matrix is an entity or object with no of rows and no of columns attribute.

3. Input:

 You have to accept n x n matrix values from the user to perform operations on it.

4. Data Structure:

To store/organize the matrix element in memory we required LIST as a data structure. 

5. Output: 

5.1 Addition of two Matrices

5.2 Subtraction of two Matrices

5.3 Multiplication of two Matrices

5.4 Transpose of a Matrix 

SOURCE CODE:

 

OUTPUT:

Basic Matrix Operation using Python
Welcome all in assignment no:03 from Group A
For Matrix operation we require some input from you Please.
Enter no of rows in first matrix: 3
Enter no of cols in first matrix: 3
Enter no of rows in second matrix: 3
Enter no of cols in second matrix: 3
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:1
please enter the values for First Matrix:
Enter the value of matrix[0][0]:: 1
Enter the value of matrix[0][1]:: 2
Enter the value of matrix[0][2]:: 3
----------------------------
Enter the value of matrix[1][0]:: 4
Enter the value of matrix[1][1]:: 5
Enter the value of matrix[1][2]:: 6
----------------------------
Enter the value of matrix[2][0]:: 7
Enter the value of matrix[2][1]:: 8
Enter the value of matrix[2][2]:: 9
----------------------------
please enter the values for Second Matrix:
Enter the value of matrix[0][0]:: 1
Enter the value of matrix[0][1]:: 2
Enter the value of matrix[0][2]:: 3
----------------------------
Enter the value of matrix[1][0]:: 4
Enter the value of matrix[1][1]:: 5
Enter the value of matrix[1][2]:: 6
----------------------------
Enter the value of matrix[2][0]:: 7
Enter the value of matrix[2][1]:: 8
Enter the value of matrix[2][2]:: 9
----------------------------
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:2
The Value of First matrix is as follows:
1 2 3
4 5 6
7 8 9
The Value of Second matrix is as follows:
1 2 3
4 5 6
7 8 9
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:3
The addition of two matrices are as follows..
2 4 6
8 10 12
14 16 18
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:4
The subtraction of two matrices are as follows..
0 0 0
0 0 0
0 0 0
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:5
The Multiplication of two matrices are as follows..
30 36 42
66 81 96
102 126 150
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:6
Before Transpose of Matrix the elements in matrix are as follows:
1 2 3
4 5 6
7 8 9
After applying Transpose on matrix elements are as follows:
1 4 7
2 5 8
3 6 9
1. Accept two matrices from user:
2. Show the matrices values:
3. Addition of Two Matrices:
4. Subtraction of Two Matrices:
5. Multiplication of Two Matrices:
6. Transpose of Matrix
7. Exit
Enter your choice:7