Data Structures Foundation-2021 Batch - Class Notes

Data Structures Foundation
Subject Code: 21CSC203A

Course Faculty: Ms. Naveeta
Programme: AIML, ISE & MC
Semester: III
Course Summary
This course is aimed at preparing the students to understand and
apply the principles of data structures and algorithms, implement
standard data structures and develop algorithms for efficient
computer programs.
A broad range of abstract data types as well as algorithms for data
storage, access and manipulation used in program development are
taught.
Data representation in computer memory, features of linear and non-
linear data structures, algorithms for searching and sorting, analysis
of computational time and space usage are covered.
Students are trained to develop applications using appropriate data
structures and algorithms.
Students implement and test computer programs in Python language.
Course Resources
EssentialReading
Class Notes
Goodrich, M.T., Tamassia, R. and Goldwasser,
M.H., 2013. Data structures and algorithms in
Python. John Wiley & Sons Ltd.
Recommended Reading
Necaise, R.D., 2011. Data structures and
algorithms using Python. Wiley.
Websites
https://www.coursera.org/
http://nptel.ac.in/
Course Syllabus
Unit-1 (Stacks, Queues, and Deques): Stacks, Queues, Double-Ended
Queues
Unit-2 (Linked Lists): Singly Linked Lists, Circularly Linked Lists, Doubly
Linked Lists
Unit-3 (Trees): General Trees, Binary Trees, Implementing Trees, Tree
Traversal Algorithms
Unit-4 (Priority Queues): The Priority Queue Abstract Data Type,
Implementing a Priority Queue, Heaps, Sorting with a Priority Queue
Unit-5 (Maps, Hash Tables, and Skip Lists): Maps and Dictionaries,
Hash Tables, Sorted Maps, Sets
Unit-6 (Search Trees): Binary Search, Binary Search Trees, Balanced
Search Trees, AVL Trees
Unit-7 (Sorting and Selection): Why Study Sorting Algorithms, Merge
Sort, Quick Sort, Selection Sort
Evaluation of Data Structures Foundation
Evaluation of Python & Data Structures Laboratory
Prerequisite for this
course
Basic knowledge of Python Programming

Language.
Why Data Structures Required ?
Data
Structure and
Types
Data Structure and Types
Popular linear data structures
Popular Non linear data structures
Popular Non linear data structures
Linear Vs Non-linear Data Structures
Big O notation
Big O notation
Big O notation
Big O notation
Big O notation
Big O notation
Big O notation
Big O notation
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Arrays
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List
We wrap both the data item and the next node reference in a "node". Each node has a data item and a pointer to another node.
Linked List
Linked List
Linked List
Linked List
Linked List
Linked List: Insert Elements to a Linked List

Linked List: Delete & Search
Linked List python implementation
Google Collab Link: https://colab.research.google.com/drive/1hk1XKEFYBXhA8atOJCOWcEltuk-8B0_N?usp=sharing
Understanding the concept of
class
Class
Attribute
Function
Object
Instance
Understanding the concept
of class (in python)
Doubly Linked List
Doubly Linked List:
Insertion at the Beginning
Doubly Linked List
Doubly Linked List: Insertion in between two nodes
Let's add a node with value 6 after node with value 1 in the doubly linked list.
Doubly Linked List: Insertion in between two
nodes
Doubly Linked List: Insertion in between two
nodes
Doubly Linked List: Insertion at the End
Let's add a node with value 6 at the end of the doubly linked list.
Doubly Linked List: Insertion at the End
Let's add a node with value 6 at the end of the doubly linked list.
Doubly Linked List: Deletion from a Doubly Linked List
Doubly Linked List: Deletion from a Doubly
Linked List
Doubly Linked List: Deletion from a Doubly Linked List
Doubly Linked List: Deletion from a Doubly
Linked List
Doubly Linked List: Complexity
1. Complexity of Insertion Operation

The insertion operations that do not require traversal have the time complexity of O(1).
And, insertion that requires traversal has time complexity of O(n).
2. Complexity of Deletion Operation

All deletion operations run with time complexity of O(1).
And, deletion that requires traversal has time complexity of O(n).
Doubly Linked List: Applications
Singly Linked List Vs Doubly Linked List
Doubly Linked List python implementation

Doubly Linked List python
implementation
Circular Linked List
Circular Linked List: Complexity
1. Complexity of Insertion Operation

The insertion operations that do not require traversal have the time complexity of O(1).
And, insertion that requires traversal has time complexity of O(n).
2. Complexity of Deletion Operation

All deletion operations run with time complexity of O(1).
And, deletion that requires traversal has time complexity of O(n).
Stack Data Structure


Stack: Basic Operations of Stack



Stack python implementation
Stack python implementation
Queue Data Structure


Queue Data Structure:
Implementation in Python
Queue Data Structure:
Implementation in Python
Queue python implementation

Types of Queues
Simple Queue
Circular Queue
Priority Queue
Deque (Double Ended Queue)
Circular Queue Data Structure
Priority Queue
Priority Queue
Priority Queue
Priority Queue
Priority Queue
Priority Queue
We will come back to

priority queues once we
learn about trees
Priority Queue
1. Inserting an Element into the Priority Queue
Priority Queue
2. Deleting an Element from the Priority Queue
Priority Queue
3. Peeking from the Priority Queue (Find max/min)
4. Extract-Max/Min from the Priority Queue

Best way to represent product hierarchy ?
Tree Data Structure
Tree Data Structure
Tree Data Structure
Tree Terminologies
Tree Terminologies
Tree Terminologies
Tree Traversal
Tree Traversal - inorder, preorder and postorder
Every tree is a combination of
Inorder traversal
Inorder traversal
Inorder traversal
Output:
Python Implementation of Tree traversal Algorithms
Tree Traversal python implementation

Binary Tree
Types of Binary Tree
Binary Tree Representation
Binary Tree Representation
Pre-order
In-order
Post-order
Python Implementation of Binary Tree
Output:
Full Binary Tree
Let, i = the number of internal nodes; i=3
n = be the total number of nodes; n=7
l = number of leaves; l=4
λ = number of levels; λ=4
1. The number of leaves is i + 1; 4
2. The total number of nodes is 2i + 1; 7
3. The number of internal nodes is (n – 1) / 2; 3
4. The number of leaves is (n + 1) / 2; 4
5. The total number of nodes is 2l – 1; 7
6. The number of internal nodes is l – 1; 3
7. The number of leaves is at most 2λ – 1; 8

Python Implementation of Full Binary Tree
Output:
Binary Search Algorithm
Binary Search Tree(BST)
There are two basic operations that you can perform on a binary search tree:
Binary Search Tree operations in Python
Binary Search Tree operations in Python
Heap Data Structure
Heap Data Structure
Heap Data Structure
Python Code for Max Heap Data Structure
Python Code for Min Heap Data Structure
Insertion in Heap Data Structure
Deletion in Heap Data Structure
Heap Data Structure
Heap Data Structure
Balanced Binary Tree
Balanced Binary Tree
AVL Tree
AVL Tree
AVL Tree
AVL Tree
AVL Tree
AVL Tree
AVL Tree
AVL Tree Implementation
AVL Tree Complexity
Deque (doubly ended queues)
● Deque or doubly ended queues are linear data structures with which we can perform last in
first out (LIFO) operations as well as first in first out (FIFO) operations.
● Deques have many applications in real life such as implementing undo operation in
softwares and in storing the browsing history in the web browsers.
Quick Sort
Quick Sort
Quick Sort
Quick Sort
Quick Sort Implementation
Quick Sort
Quick Sort
Quick Sort
Selection Sort
Selection Sort
Selection Sort
Selection Sort: Python Implementation
Selection Sort
Merge Sort
Merge Sort
Merge Sort
Merge Sort: An Illustration
Merge Sort: Python Implementation
Merge Sort: Code Trace
https://docs.google.com/document/d/128aWMWR5Fs33shAlFsPC-0A8bNjtHRjx/
edit?usp=sharing&ouid=107172905328835780244&rtpof=true&sd=true
Merge Sort: An Illustration
Merge Sort: Application
Assists External Sorting

External sorting is a technique used for sorting large amounts of data that cannot fit in the memory of a single machine. This technique is
used when the data size is too large to fit in the available memory, and it must be stored on disk or other external storage devices.
The basic idea of external sorting is to divide the data into smaller chunks that can fit into memory and sort these chunks individually. The
sorted chunks are then merged to produce the final sorted output.
The external sorting algorithm typically consists of two phases:
1. Sorting Phase: In this phase, the large input data is divided into smaller chunks, which can fit into the available memory. These
chunks are then sorted using an efficient sorting algorithm such as merge sort, quicksort, or heap sort. The sorted chunks are then
stored on disk.
2. Merging Phase: In this phase, the sorted chunks are merged to produce the final sorted output. This is done by using a merge
algorithm that takes two sorted chunks at a time and merges them into a single sorted chunk. This process is repeated until all the
sorted chunks are merged into a single output file.
External sorting is widely used in data processing applications such as database systems, data warehousing, and big data processing. It
allows processing large volumes of data efficiently, without having to load the entire data into memory at once, which can lead to
performance degradation and system crashes.

Data Structures Foundation-2021 Batch - Class Notes

Uploaded by

Copyright:

Available Formats

Data Structures Foundation-2021 Batch - Class Notes

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structures Foundation-2021 Batch - Class Notes

Uploaded by

Copyright:

Available Formats

Data Structures Foundation

Subject Code: 21CSC203A

Basic knowledge of Python Programming

Linked List: Insert Elements to a Linked List

1. Complexity of Insertion Operation

2. Complexity of Deletion Operation

Google Collab Link: https://colab.research.google.com/drive/1hk1XKEFYBXhA8atOJCOWcEltuk-8B0_N?usp=sharing

1. Complexity of Insertion Operation

2. Complexity of Deletion Operation

Stack Data Structure

Stack Data Structure

Stack: Basic Operations of Stack

Stack: Basic Operations of Stack

Stack: Basic Operations of Stack

Queue Data Structure

Queue Data Structure

Google Collab Link: https://colab.research.google.com/drive/1hk1XKEFYBXhA8atOJCOWcEltuk-8B0_N?usp=sharing

We will come back to

4. Extract-Max/Min from the Priority Queue

Google Collab Link: https://colab.research.google.com/drive/1hk1XKEFYBXhA8atOJCOWcEltuk-8B0_N?usp=sharing

Let, i = the number of internal nodes; i=3

n = be the total number of nodes; n=7

l = number of leaves; l=4

λ = number of levels; λ=4

1. The number of leaves is i + 1; 4

2. The total number of nodes is 2i + 1; 7

3. The number of internal nodes is (n – 1) / 2; 3

4. The number of leaves is (n + 1) / 2; 4

5. The total number of nodes is 2l – 1; 7

6. The number of internal nodes is l – 1; 3

7. The number of leaves is at most 2λ – 1; 8

Assists External Sorting

You might also like