Fundamentals of Data Structures Syllabus Semester SPPU

Fundamentals of Data Structures Syllabus Semester SPPU Computer Engineering

Unit - 1 Introduction to Algorithm and Data structures
1.1 Introduction From Problem to Data Structure Problem Logic Algorithm and Data Structure.
1.2 Data Structures Data Information Knowledge and Data structure Abstract Data Types ADT Data Structure Classification Linear and Nonlinear Static and Dynamic Persistent and Ephemeral data structures
1.3 Algorithms Problem Solving Introduction to algorithm Characteristics of algorithm Algorithm design tools Pseudocode and flowchart
1.4 Complexity of algorithm Space complexity Time complexity Asymptotic notation BigO Theta and Omega Finding complexity using step count method Analysis of programming constructs Linear Quadratic Cubic Logarithmic.
1.5 Algorithmic Strategies Introduction to algorithm design strategies Divide and Conquer and Greedy strategy.

Unit - 2 Linear Data Structure using Sequential Organization
2.1 Concept of Sequential Organization
2.2 Overview of Array
2.3 Array as an Abstract Data Type
2.5 Merging of two arrays
2.6 Advantages and Disadvantages of Arrays
2.7 Storage Representation and their Address Calculation Row major and Column Major
2.8 Multidimensional Arrays Twodimensional arrays ndimensional arrays.
2.9 Concept of Ordered List
2.10 Single Variable Polynomial Representation using arrays Polynomial as array of structure Polynomial addition Polynomial multiplication.
2.11 Sparse Matrix Sparse matrix representation using array Sparse matrix addition Transpose of sparse matrix Simple and Fast Transpose Time and Space tradeoff

Unit - 3 Searching and Sorting
3.1 Searching
3.2 Sentinel search
3.3 Binary search
3.4 Fibonacci search
3.5 Indexed sequential search
3.6 Types of SortingInternal and External Sorting
3.7 General Sort ConceptsSort Order Stability Efficiency and Number of Passes
3.8 Comparison Based Sorting MethodsBubble Sort Insertion Sort Selection Sort Quick Sort Shell Sort
3.9 Noncomparison Based Sorting MethodsRadix Sort Counting Sort and Bucket Sort
3.10 Comparison of All Sorting Methods and their complexities.

Unit - 4 Linked List
4.1 Introduction to Static and Dynamic Memory Allocation
4.2 Linked List Introduction
4.3 Types of Linked Lists
4.4 Realization of linked list using dynamic memory management
4.5 Linked List as ADT
4.6 Basic primitive operations on linked list
4.7 Generalized Linked List
4.8 Polynomial Representation using Generalized Linked List

Unit - 5 Stack
5.1 Basic concept
5.2 Stack as Abstract Data Type
5.3 Representation of Stacks Using Sequential Organization
5.4 Stack operations
5.5 Multiple Stacks
5.6 Applications of Stack Expression Evaluation and Conversion
5.7 Polish notation and expression conversion
5.8 Need for prefix and postfix expressions
5.9 Postfix expression evaluation
5.10 Linked Stack and Operations
5.11 Recursion concept variants of recursion direct indirect tail and tree
5.12 Backtracking algorithmic strategy
5.13 Use of stack in backtracking.

Unit - 6 Queue
6.1 Basic concept
6.2 Queue as Abstract Data Type
6.3 Representation of Queue using Sequential organization
6.4 Queue Operations
6.5 Circular Queue and its advantage
6.6 Multiqueues
6.7 Linked Queue and Operations
6.8 DequeueBasic concept types Input restricted and Output restricted
6.9 Priority Queue Basic concept types Ascending and Descending.