Data Structures and

fundamentals of
Algorithm
UNIT 1
Data Types
 Data Structures
The data structure is a specific way of storing and organizing data in the computer's memory
so that these data can be easily retrieved and efficiently used when needed later.

Built In User Defined

1. List 1. Stack
2. Tuple 2. Queue
3. Dictionary 3. Tree
4. Set 4. Graph
5. Linked List
6. Hash map

**Only Tree and Graph are Non-Linear, other all are linear
Abstract Data Types (ADT)
● An abstract data type (or ADT) is a programmer-defined data type that
specifies a set of data values and a collection of well-defined operations
that can be performed on those values
● Defined independent of their implementation details
● 2 types: Simple and Complex ADT
● ADT operations can be categorized as:
- Constructors: Create and initialize new instances of the ADT.
- Accessors: Return data contained in an instance without modifying it.
- Mutators: Modify the contents of an ADT instance.
- Iterators: Process individual data components sequentially.
● Eg. Date ADT, List, Stack, Queue
Abstractions
● An abstraction is a mechanism for separating the properties of an object
and restricting the focus to those relevant in the current context.
● The user of the abstraction does not have to understand all of the details
in order to utilize the object, but only those relevant to the current task or
problem.
● Types of abstractions:
- Procedural abstractions
- Data abstractions
 Abstractions
★ Procedural abstractions:
➔ Procedural abstraction is the use of a function or method knowing what it does but
ignoring how it’s accomplished.
➔ Consider the mathematical square root function which you have probably used at
some point. You know the function will compute the square root of a given
number, but do you know how the square root is computed?
★ Data abstractions
➔ The separation of the properties of a data type (its values and operations) from the
implementation of that data type.
➔ You have used strings in Python many times. But do you know how they are
implemented? That is, do you know how the data is structured internally or how he
various operations are implemented?
Date ADT
● A date represents a single day in the proleptic Gregorian calendar.
● An example of simple ADT
● Operations:
1. Date( month, day, year ): Creates a new Date instance initialized to
the given Gregorian date which must be valid.
2. day(): Returns the Gregorian day number of this date.
3. month(): Returns the Gregorian month number of this date.
4. year(): Returns the Gregorian year of this date.
5. monthName(): Returns the Gregorian month name of this date.
6. dayOfWeek(): Returns the day of the week as a number between 0
and 6 with 0 representing Monday and 6 representing Sunday.
Date ADT
7. numDays( otherDate ): Returns the number of days as a positive
integer between this date and the otherDate.
8. isLeapYear(): Determines if this date falls in a leap year and returns the
appropriate boolean value.
9. advanceBy( days ): Advances the date by the given number of days.

Other examples of ADT

● Lists- sort(), append(), clear(), del() etc.
● Stack- push(), pop(), peek(), isEmpty()
Date ADT
Bags
● A bag is a simple container that can be used to store a collection of
items.
● Allows duplicate values
● Unordered
● Cannot access individual items
● Operations that can be performed include:
- Adding items
- Removing items
- Determine if item is in bag
- Traverse over the collection of items
Bags
● A bag is a container that stores a collection in which duplicate values
are allowed.
● The items, each of which is individually stored, have no particular
order but they must be comparable.
● Bag(): Creates a bag that is initially empty.
● length (): Returns the number of items stored in the bag. Accessed
using the len() function.
Bags
● contains ( item ): Determines if the given target item is stored in the
bag and returns the appropriate boolean value. Accessed using the in
operator.
● add( item ): Adds the given item to the bag.
● remove( item ): Removes and returns an occurrence of item from the
bag. An exception is raised if the element is not in the bag.
● iterator (): Creates and returns an iterator that can be used to iterate
over the collection of items.
Bags- Examples
Iterators
● Traversals are very common operations, especially on containers
● A traversal iterates over the entire collection, providing access to each
individual element.
● Traversals can be used for a number of operations, including
searching for a specific item or printing an entire collection
● Python’s container types—strings, tuples, lists, and dictionaries—can
be traversed using the for loop construct.
● For our user-defined abstract data types, we can add methods that
perform specific traversal operations when necessary
Iterators
● Python, provides a built-in iterator construct that can be used to
perform traversals on user-defined ADTs.
● An iterator is an object that provides a mechanism for performing
generic traversals through a container without having to expose
the underlying implementation.
● Used with Python’s for loop construct to provide a traversal
mechanism for both built-in and user-defined containers.
Iterators
● It consists of the methods __iter__() and __next__()

CODE 2
CODE 1
Iterators- Create an Iterator
● To create an object/class as an iterator you have to implement the
methods __iter__() and __next__() to your object.
● All classes have a function called __init__(), which allows you to do
some initializing when the object is being created.
● The __iter__() method acts similar, you can do operations (initializing
etc.), but must always return the iterator object itself.
● The __next__() method also allows you to do operations, and must
return the next item in the sequence.
 Iterators- Create an Iterator
Create an iterator that
returns numbers,
starting with 1, and
each sequence will
increase by one
(returning 1,2,3,4,5
etc.)
ARRAYS
● An array is defined as a collection of elements of similar data type.
● Array elements are stored in contiguous memory.
● Array name represents its base address. The base address is the address
of the first element of the array.
● Array elements are accessed by using an integer index

● Types of Array: Single Dimensional Array( 1-D) & Multi-Dimensional Array

(2-D OR 3-D)
Creating an Array
● An array cannot change size once it has been created.
● Array in Python can be created by importing an array module.
array(data_type, value_list) is used to create an array with data type and
value list specified in its arguments.
● Some of the data types are mentioned below which will help in creating an array of different data
types.
Array ADT- Some Methods
● append(x): Append a new item with value x to the end of the array.
● count(x) : Return the number of occurrences of x in the array.
● extend(iterable) : Append items from iterable to the end of the array. If
iterable is another array, it must have exactly the same type code If
iterable is not an array, it must be iterable and its elements must be the
right type to be appended to the array.
● insert(i, x) : Insert a new item with value x in the array before position i.
Negative values are treated as being relative to the end of the array.
● pop([i]) :Removes the item with the index i from the array and returns it.
The optional argument defaults to -1, so that by default the last item is
removed and returned.
● reverse(): Reverse the order of the items in the array.
Python Lists

● An list is defined as a collection of elements of any data type.

● List items are ordered, changeable, and allow duplicate values.
● List items are indexed, the first item has index [0], the second item has
index [1] etc.
Python Lists
● Suppose we create a list containing several values:
pyList = [ 4, 12, 2, 34, 17 ]
● the list() constructor being called to create a list object and fill it with the given
values.
● Following Figure illustrates the abstract and physical views of our sample list:
Python Lists
● In the physical view, the elements of the array structure used to store the actual
contents of the list are enclosed inside the dashed gray box.
● The elements with null references shown outside the dashed gray box are the
remaining elements of the underlying array structure that are still available for
use.
● This notation will be used throughout the section to illustrate the contents of the
list and the underlying array used to implement it.
● If there is room in the array, the item is stored in the next available slot of the
array and the length field is incremented by one
Python Lists

● For example, consider the following list operations:

pyList.append( 18 )
pyList.append( 64 )
pyList.append( 6 )
● After the second statement is executed, the array becomes full
Python Lists
● By definition, a list can contain any number of items and never becomes full.
● Thus, when the third statement is executed, the array will have to be expanded
to make room for value 6. (an array cannot change size once it has been
created.)
● To allow for the expansion of the list, the following steps have to be performed:
(1) a new array is created with additional capacity,
(2) the items from the original array are copied to the new array,
(3) the new larger array is set as the data structure for the list, and
(4) the original smaller array is destroyed.
Python Lists
Python Lists
Python Lists- Extending list
Python Lists- Inserting in a list
Python Lists- Removing Items
ARRAYS VS LISTS

LISTS ARRAYS
It consists of elements that belong to It consists of elements that belong to
the different data types. the same data type.
It consumes a larger memory. It consumes less memory than a list.
It favors a shorter sequence of data. It favors a longer sequence of data.
The lists are the build-in data We need to import the array before
structure so we don't need to work with the array.
import it.
TWO DIMENSIONAL ARRAYS
● A two-dimensional array consists of a collection of elements organized into
rows and columns.
● Individual elements are referenced by specifying the specific row and column
indices (r, c), both of which start at 0.
● Following: Figure shows an abstract view of both a one- and a two dimensional
array
TWO DIMENSIONAL ARRAYS
TWO DIMENSIONAL ARRAYS
MATRIX ABSTRACT DATA TYPE
● A matrix is a collection of scalar(numeric, character) values arranged in rows
and columns as a rectangular grid of a fixed size.
● The elements of the matrix can be accessed by specifying a given row and
column index with indices starting at 0
MATRIX ABSTRACT DATA TYPE
MATRIX ABSTRACT DATA TYPE
 MATRIX ADT- Matrix Operations
● Addition and Subtraction.
1. Two m × n matrices can be added or subtracted to create a third m × n matrix.
2. When adding two m × n matrices, corresponding elements are summed as
illustrated here.
3. Subtraction is performed in a similar fashion but the corresponding elements
are subtracted instead of summed.
MATRIX ADT- Matrix Operations
MATRIX ADT- Matrix Operations
 MATRIX ADT- Matrix Operations
● Multiplication
➔ Only defined for matrices where the number of columns in the matrix on the
lefthand side is equal to the number of rows in the matrix on the righthand side
➔ Given a matrix of size m × n multiplied by a matrix of size n × p, the resulting
matrix is of size m × p.
Sets
● A set is a container that stores a collection of unique values over a given
comparable domain in which the stored values have no particular ordering.
● Unordered
● Mutable
● Defined using { } in python or set()
Sets
Sets
Selecting a Data Structure for sets implementation
● To replicate the functionality of the set structure provided by Python, leaves
the array, list, and dictionary containers for consideration in implementing
the Set ADT
● Storage requirements for the bag and set are very similar with the difference
being that a set cannot contain duplicates.
● Dictionary would seem to be the ideal choice since it can store unique
items, but it would waste space in this case. As dictionary stores key/value
pairs, which requires two data fields per entry.
● An array could be used to implement the set, but a set can contain any
number of elements and by definition an array has a fixed size.
● To use the array structure, we would have to manage the expansion of the
array when necessary in the same fashion as it’s done for the list.
Selecting a Data Structure for sets implementation
● Since the list can grow as needed, it seems ideal for storing the elements of
a set just as it was for the bag and it does provide for the complete
functionality of the ADT.
● Since the list allows for duplicate values, however, we must make sure as
part of the implementation that no duplicates are added to our set.
Maps
● A map is a container for storing a collection of data records in which each
record is associated with a unique key.
● The key components must be comparable.
Searching & Sorting
algorithms
Searching

● Searching is the process of finding some particular element in the list.

● If the element is present in the list, then the process is called
successful, and the process returns the location of that element;
otherwise, the search is called unsuccessful.
● Two popular search methods are Linear Search and Binary Search.
Linear Search
● Linear search is also called a sequential search algorithm.
● It is the simplest searching algorithm.
● In Linear search, we simply traverse the list completely and match each
element of the list with the item whose location is to be found.
● If the match is found, then the location of the item is returned;
otherwise, the algorithm returns NULL.
● It is widely used to search an element from the unordered list, i.e., the
list in which items are not sorted.
● The worst-case time complexity of linear search is O(n).
Linear Search- Algorithm
Linear Search

Implementation of Linear Search in Python

Linear Search- Time & Space complexity
Binary Search
● Binary Search is a searching algorithm for finding an element's position
in a sorted array.
● In this approach, the element is always searched in the middle of a
portion of an array.
● If the match is found then, the location of the middle element is
returned.
● Otherwise, we search into either of the halves depending upon the
result produced through the match.
● Binary search can be implemented only on a sorted list of items.
Binary Search- Algorithm
Binary Search- Algorithm
Implementation of Binary Search in Python
Binary Search- Time & Space complexity
Sorting
● Sorting is the processing of arranging the data in ascending and
descending order.
● There are several types of sorting in data structures namely – bubble
sort, insertion sort, selection sort, merge sort, quick sort, radix sort etc.
● Sorting techniques are categorized into
★ Internal Sorting : Takes place in the main memory of a computer.
Example: - Bubble sort, Insertion sort, Quick sort, etc.
★ External Sorting: Takes place in the secondary memory of a computer,
Since the number of objects to be sorted is too large to fit in main memory.
Example: - Merge Sort
Bubble Sort
● Bubble sort is a sorting algorithm that compares two adjacent elements
and swaps them until they are not in the intended order.
● It is not suitable for large data sets.
● The average and worst-case complexity of Bubble sort is O(n2), where n
is a number of items.
● Bubble short is majorly used where -
○ complexity does not matter
○ simple and shortcode is preferred
Bubble Sort Algorithm
● Traverse from left and
compare adjacent
elements and the higher
one is placed at right side.
● In this way, the largest
element is moved to the
rightmost end at first.
● This process is then
continued to find the
second largest and place it
and so on until the data is
sorted.
Implementation of Bubble Sort in Python
Bubble Sort - Time & Space complexity

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
 Selection Sort
● Selection sort, also known as in-place comparison sort, is a simple
sorting algorithm. It works on the idea of repeatedly finding the smallest
element and placing it at its correct sorted position.
● Selection sort works by dividing the list into two sublists:
➔ Sorted sublist – that is built on the left end of the list from left to right.
➔ Unsorted sublist – that is the rest of the unsorted list, on the right end.
Working of Selection Sort
1. Set the first element as minimum

2. Compare minimum with the second

element. If the second element is smaller
than minimum, assign the second element
as minimum.
Compare minimum with the third element.
Again, if the third element is smaller, then
assign minimum to the third element
otherwise do nothing. The process goes on
until the last element.
Working of Selection Sort
3. After each iteration, minimum is placed in the front of the unsorted list.

4. For each iteration, indexing starts from the first unsorted element. Step 1
to 3 are repeated until all the elements are placed at their correct positions.
Implementation of Selection Sort
Selection Sort - Time & Space complexity

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
Insertion Sort
● Insertion sort is a sorting algorithm that places an unsorted element at its
suitable place in each iteration.
● Insertion sort works similarly as we sort cards in our hand in a card
game.
● We assume that the first card is already sorted then, we select an
unsorted card. If the unsorted card is greater than the card in hand, it is
placed on the right otherwise, to the left. In the same way, other unsorted
cards are taken and put in their right place.
Insertion Sort- Algorithm
Working of Insertion Sort
1. Suppose we need to sort the following
array

2. The first element in the array is assumed

to be sorted. Take the second element
and store it separately in key.
Compare key with the first element. If the
first element is greater than key, then key
is placed in front of the first element.
Working of Selection Sort
3. Now, the first two elements are
sorted.
Take the third element and compare it
with the elements on the left of it.
Placed it just behind the element
smaller than it.
If there is no element smaller than it,
then place it at the beginning of the
array.
Working of Selection Sort
4. Similarly, place every unsorted
element at its correct position
Implementation of Insertion Sort
Insertion Sort - Time & Space complexity

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
Merge Sort
● Merge Sort is one of the most popular sorting algorithms that is based on
the principle of Divide and Conquer Algorithm.
● Here, a problem is divided into multiple sub-problems. Each sub-problem
is solved individually. Finally, sub-problems are combined to form the
final solution.
● The MergeSort function repeatedly divides the array into two halves until
we reach a stage where we try to perform MergeSort on a subarray of
size 1 i.e. p == r.
● After that, the merge function comes into play and combines the sorted
arrays into larger arrays until the whole array is merged.
Implementation of Merge Sort
Merge Sort - Time & Space complexity
Case Time complexity

Best O(nlogn)

Average O(nlogn)

Worst O(nlogn)

Space Complexity O(n)

Stable Yes

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
Quick Sort
Quicksort is a sorting algorithm based on the divide and conquer approach
where :
1. An array is divided into subarrays by selecting a pivot element (element
selected from the array).
2. While dividing the array, the pivot element should be positioned in such a
way that elements less than pivot are kept on the left side and elements
greater than pivot are on the right side of the pivot.
3. The left and right subarrays are also divided using the same approach.
This process continues until each subarray contains a single element.
4. At this point, elements are already sorted. Finally, elements are
combined to form a sorted array.
Working of Quick Sort
Working of Quick Sort
Implementation of Quick Sort
Quick Sort - Time & Space complexity
Case Time complexity

Best O(nlogn)

Average O(nlogn)

Worst O(n2)

Space Complexity O(n)

Stable Yes

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
Radix Sort
1. Radix Sort is a linear sorting algorithm.
2. Radix Sort's time complexity of O(nk), where n is the size of the array
and k is the number of digits in the largest number.
3. It is not an in-place sorting algorithm because it requires extra space.
4. Radix Sort is a stable sort because it maintains the relative order of
elements with equal values.
5. Because it is based on digits or letters, radix sort is less flexible than
other sorts. If the type of data changes, the Radix sort must be rewritten.
Working of Radix Sort
Working of Radix Sort
Working of Radix Sort
Working of Radix Sort
Working of Radix Sort
Implementation of Radix Sort
Quick Sort - Time & Space complexity
Case Time complexity

Best O(nk)

Average O(nk)

Worst O(nk)

Space Complexity O(n+k)

Stable Yes

● Stable sorting maintains the position of two equals elements relative to one another.
● Unstable sorting does not maintain the position of two equals elements relative to one another.
Sorting Algorithm Time Complexity Space complexity

Bubble sort O(n2) O(1)

Selection sort O(n2) O(1)

Insertion sort O(n2) O(1)

Merge sort O(nlogn) O(n)

Quick sort O(n2) O(n)

Radix sort O(nk) O(n+k)