`DATA STRUCTURES AND ALGORITHM IN PYTHON
What are data structures?
Data structures allow you easy access to efficient modification
Organize, store, relate and perform operations on them accordingly
There are two categories of data structures in python
• Built-in data structures
• User defined data structures
Built-in data structures
Enables you to store and access data. They include:
Lists
Sets
Tuples
Dictionary
User defined
Aallow users to create there own data structures
Stack
Queue
Tree
LinkedList
Graph
HashMap
Built in data structures
Lists
Lists used to store data of different data types in a sequential manner
They are mutable. To create a list, you use the square brackets and add elements into it accordingly. If you do not pass any elements inside the square brackets, you get an empty list as the output.
1
2
3
4 my_list = [] #create empty list
print(my_list)
my_list = [1, 2, 3, 'example', 3.132] #creating list with data
print(my_list)
Tuple are same as list , only that when data enters a tuple it cannot be modified. Not mutable
You create a tuple using parenthesis or using the tuple() function.
1
2 my_tuple = (1, 2, 3) #create tuple
A tuple is a built-in data structure in Python that is an ordered collection of objects. The primary differing characteristic between lists and tuples is mutability. Lists are mutable, whereas tuples are immutable. Tuples cannot be modified, added, or deleted once they’ve been created. Lists are defined by using parentheses to enclose the elements, which are separated by commas
Dictionary
Used to store key value pairs, example is mapping employee names with employee IDs
Created using curly braces
Dictionaries can be created using the flower braces or using the dict() function. You need to add the key-value pairs whenever you work with dictionaries.
my_dict = {1: 'Python', 2: 'Java'} #dictionary with elements
print(my_dict)
are used to store key-value pairs
Sets
A collection of unordered elements
They are mutable, can be created using curly braces.
Creating a set
Sets are created using the flower braces but instead of adding key-value pairs, you just pass values to it.
1
2 my_set = {1, 2, 3, 4, 5, 5, 5} #create set
User-defined data structures
Stack
Linear data structures based on the principle of last in first out. Built using array structures.
Applications. Recursive programming, reverse inverse, word editors
Queues
Linear data structure that is based on principle of first in first out. Data entered first will be accessed first. Built using array structures. Allows insertion of elements from one end and deletion from the other.
queue = ['first', 'second', 'third']
print(queue)
Aq
Trees
Non linear data structures with roots and nodes. Root is where the data originate and nodes are data point that are available to us. Node preceding is the parent and node that is after is the child. Last node is the leaves.
Uses:
Html pages, searching purposes
Linked list
Linear data structures that are not stored consequently but are linked to each other using pointers. Node is composed of data and a pointers called the nest. These are used in image viewing applications
Graph
Used to store data collection of point called
Uses
Google maps, uber to find the shortest distance
Hashmaps
Same as dictionary
Used in phone books, populate data according to the data
=
Algorithms
These are rules or instructions that are formulated in a finite, sequential order to solve problems. They provide pseudocode for problems for various languages.
Process for writing algorithms
Identify the problem
Identify starting point
Determine end point
Formulate intermediate steps
Review steps
Can be done depending on user preferences
Elements
Defined output and input
Flexibility
Algorithm Classes
Greedy algorithms- This involves taking the easiest step without worrying about future complexity
Dynamic programming- Divide problem into sections and remember the result of each section and apply to similar ones.
Divide and Conquer- Divides problems into sections and solve them separately
Tree Traversal algorithms
This refers to visiting each node present in the tree exactly once in order to update
Types of tree traversals
In-order traversal- refers to visiting the left nodes followed by the root and then right
Post-order traversal- refers to visiting the left nodes followed by the right nodes and then root node
Pre-order traversal- refers to visiting the root nodes and then right nodes.
Sorting Algorithms
Sorting algorithms denote the ways to arrange data in a particular format. Sorting ensures that data searching is optimized to a high level and that the data is
• Bubble Sort – This algorithm is based on comparison in which there is repeated swapping of adjacent elements if they are in an incorrect order.
• Merge Sort – Based on the divide and conquer algorithm, Merge sort divides the Array into two halves, sorts them, and then combines them.
• Insertion Sort – This sorting begins with comparing and sorting the first two elements. Then, the third element is compared with the two previously sorted elements and so on.
• Shell Sort – It is a form of Insertion sort, but here, far away elements are sorted. A large sub-list of a given list is sorted, and the size of the list is progressively reduced until all the elements are sorted.
• Selection Sort – This algorithm begins by finding the minimum value from a list of elements and puts it into a sorted list. The process is then repeated for each of the remaining elements in the list which is unsorted. The new element entering the sorted list is compared with its existing elements and placed at the correct position. The process goes on until all the elements are sorted.
Searching Algorithms
Searching algorithms help in checking and retrieving an element from different data structures. One type of searching algorithm applies the method of sequential search where the list is sequentially traversed, and every element is checked (linear search). In another type, the interval search, elements are searched for in sorted data structures (binary search). Let us look at some of the examples:
• Linear Search **– In this algorithm, each item is sequentially searched one by one.
• **Binary Search – The search interval is repeatedly divided in half. If the element to be searched is lower than the central component of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. The process is repeated until the value is found.
Graph Algorithms
There are two methods of traversing graphs using their edges. These are:
• Depth-first Traversal (DFS) – In this algorithm, a graph is traversed in a depth-ward motion. When any iteration faces a dead end, a stack is used to go to the next vertex and start a search. DFS is implemented in Python using the set data types.
• Breadth-first Traversal (BFS) – In this algorithm, a graph is traversed in a breadthward motion. When any iteration faces a dead end, a queue is used to go to the next vertex and start a search. BFS is implemented in Python using the queue data structure.
Algorithm Analysis
• A Priori Analysis – This represents a theoretical analysis of the algorithm before its implement ation. An algorithm’s efficiency is measured by presuming that factors, such as processor speed, are constant and have no consequence on the algorithm.
• A Posterior Analysis – This refers to the empirical analysis of the algorithm after its implementation. A programming language is used to implement the selected algorithm, followed by its execution on a computer. This analysis collects statistics, such as the time and space required for the algorithm to run.
AQ `DATA STRUCTURES AND ALGORITHM IN PYTHON
What are data structures?
Data structures allow you easy access to efficient modification
Organize, store, relate and perform operations on them accordingly
There are two categories of data structures in python
• Built-in data structures
• User defined data structures
Built-in data structures
Enables you to store and access data. They include:
Lists
Sets
Tuples
Dictionary
User defined
Aallow users to create there own data structures
Stack
Queue
Tree
LinkedList
Graph
HashMap
Built in data structures
Lists
Lists used to store data of different data types in a sequential manner
They are mutable. To create a list, you use the square brackets and add elements into it accordingly. If you do not pass any elements inside the square brackets, you get an empty list as the output.
1
2
3
4 my_list = [] #create empty list
print(my_list)
my_list = [1, 2, 3, 'example', 3.132] #creating list with data
print(my_list)
Tuple are same as list , only that when data enters a tuple it cannot be modified. Not mutable
You create a tuple using parenthesis or using the tuple() function.
1
2 my_tuple = (1, 2, 3) #create tuple
A tuple is a built-in data structure in Python that is an ordered collection of objects. The primary differing characteristic between lists and tuples is mutability. Lists are mutable, whereas tuples are immutable. Tuples cannot be modified, added, or deleted once they’ve been created. Lists are defined by using parentheses to enclose the elements, which are separated by commas
Dictionary
Used to store key value pairs, example is mapping employee names with employee IDs
Created using curly braces
Dictionaries can be created using the flower braces or using the dict() function. You need to add the key-value pairs whenever you work with dictionaries.
my_dict = {1: 'Python', 2: 'Java'} #dictionary with elements
print(my_dict)
are used to store key-value pairs
Sets
A collection of unordered elements
They are mutable, can be created using curly braces.
Creating a set
Sets are created using the flower braces but instead of adding key-value pairs, you just pass values to it.
1
2 my_set = {1, 2, 3, 4, 5, 5, 5} #create set
User-defined data structures
Stack
Linear data structures based on the principle of last in first out. Built using array structures.
Applications. Recursive programming, reverse inverse, word editors
Queues
Linear data structure that is based on principle of first in first out. Data entered first will be accessed first. Built using array structures. Allows insertion of elements from one end and deletion from the other.
queue = ['first', 'second', 'third']
print(queue)
Aq
Trees
Non linear data structures with roots and nodes. Root is where the data originate and nodes are data point that are available to us. Node preceding is the parent and node that is after is the child. Last node is the leaves.
Uses:
Html pages, searching purposes
Linked list
Linear data structures that are not stored consequently but are linked to each other using pointers. Node is composed of data and a pointers called the nest. These are used in image viewing applications
Graph
Used to store data collection of point called
Uses
Google maps, uber to find the shortest distance
Hashmaps
Same as dictionary
Used in phone books, populate data according to the data
=
Algorithms
These are rules or instructions that are formulated in a finite, sequential order to solve problems. They provide pseudocode for problems for various languages.
Process for writing algorithms
Identify the problem
Identify starting point
Determine end point
Formulate intermediate steps
Review steps
Can be done depending on user preferences
Elements
Defined output and input
Flexibility
Algorithm Classes
Greedy algorithms- This involves taking the easiest step without worrying about future complexity
Dynamic programming- Divide problem into sections and remember the result of each section and apply to similar ones.
Divide and Conquer- Divides problems into sections and solve them separately
Tree Traversal algorithms
This refers to visiting each node present in the tree exactly once in order to update
Types of tree traversals
In-order traversal- refers to visiting the left nodes followed by the root and then right
Post-order traversal- refers to visiting the left nodes followed by the right nodes and then root node
Pre-order traversal- refers to visiting the root nodes and then right nodes.
Sorting Algorithms
Sorting algorithms denote the ways to arrange data in a particular format. Sorting ensures that data searching is optimized to a high level and that the data is
• Bubble Sort – This algorithm is based on comparison in which there is repeated swapping of adjacent elements if they are in an incorrect order.
• Merge Sort – Based on the divide and conquer algorithm, Merge sort divides the Array into two halves, sorts them, and then combines them.
• Insertion Sort – This sorting begins with comparing and sorting the first two elements. Then, the third element is compared with the two previously sorted elements and so on.
• Shell Sort – It is a form of Insertion sort, but here, far away elements are sorted. A large sub-list of a given list is sorted, and the size of the list is progressively reduced until all the elements are sorted.
• Selection Sort – This algorithm begins by finding the minimum value from a list of elements and puts it into a sorted list. The process is then repeated for each of the remaining elements in the list which is unsorted. The new element entering the sorted list is compared with its existing elements and placed at the correct position. The process goes on until all the elements are sorted.
Searching Algorithms
Searching algorithms help in checking and retrieving an element from different data structures. One type of searching algorithm applies the method of sequential search where the list is sequentially traversed, and every element is checked (linear search). In another type, the interval search, elements are searched for in sorted data structures (binary search). Let us look at some of the examples:
• Linear Search – In this algorithm, each item is sequentially searched one by one.
• Binary Search – The search interval is repeatedly divided in half. If the element to be searched is lower than the central component of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. The process is repeated until the value is found.
Graph Algorithms
There are two methods of traversing graphs using their edges. These are:
• Depth-first Traversal (DFS) – In this algorithm, a graph is traversed in a depthward motion. When any iteration faces a dead end, a stack is used to go to the next vertex and start a search. DFS is implemented in Python using the set data types.
• Breadth-first Traversal (BFS) – In this algorithm, a graph is traversed in a breadthward motion. When any iteration faces a dead end, a queue is used to go to the next vertex and start a search. BFS is implemented in Python using the queue data structure.
Algorithm Analysis
• A Priori Analysis – This represents a theoretical analysis of the algorithm before its implementation. An algorithm’s efficiency is measured by presuming that factors, such as processor speed, are constant and have no consequence on the algorithm.
• A Posterior Analysis – This refers to the empirical analysis of the algorithm after its implementation. A programming language is used to implement the selected algorithm, followed by its execution on a computer. This analysis collects statistics, such as the time and space required for the algorithm to run.
AQ `DATA STRUCTURES AND ALGORITHM IN PYTHON
What are data structures?
Data structures allow you easy access to efficient modification
Organize, store, relate and perform operations on them accordingly
There are two categories of data structures in python
• Built-in data structures
• User defined data structures
Built-in data structures
Enables you to store and access data. They include:
Lists
Sets
Tuples
Dictionary
User defined
Aallow users to create there own data structures
Stack
Queue
Tree
LinkedList
Graph
HashMap
Built in data structures
Lists
Lists used to store data of different data types in a sequential manner
They are mutable. To create a list, you use the square brackets and add elements into it accordingly. If you do not pass any elements inside the square brackets, you get an empty list as the output.
1
2
3
4 my_list = [] #create empty list
print(my_list)
my_list = [1, 2, 3, 'example', 3.132] #creating list with data
print(my_list)
Tuple are same as list , only that when data enters a tuple it cannot be modified. Not mutable
You create a tuple using parenthesis or using the tuple() function.
1
2 my_tuple = (1, 2, 3) #create tuple
A tuple is a built-in data structure in Python that is an ordered collection of objects. The primary differing characteristic between lists and tuples is mutability. Lists are mutable, whereas tuples are immutable. Tuples cannot be modified, added, or deleted once they’ve been created. Lists are defined by using parentheses to enclose the elements, which are separated by commas
Dictionary
Used to store key value pairs, example is mapping employee names with employee IDs
Created using curly braces
Dictionaries can be created using the flower braces or using the dict() function. You need to add the key-value pairs whenever you work with dictionaries.
my_dict = {1: 'Python', 2: 'Java'} #dictionary with elements
print(my_dict)
are used to store key-value pairs
Sets
A collection of unordered elements
They are mutable, can be created using curly braces.
Creating a set
Sets are created using the flower braces but instead of adding key-value pairs, you just pass values to it.
1
2 my_set = {1, 2, 3, 4, 5, 5, 5} #create set
User-defined data structures
Stack
Linear data structures based on the principle of last in first out. Built using array structures.
Applications. Recursive programming, reverse inverse, word editors
Queues
Linear data structure that is based on principle of first in first out. Data entered first will be accessed first. Built using array structures. Allows insertion of elements from one end and deletion from the other.
queue = ['first', 'second', 'third']
print(queue)
Aq
Trees
Non linear data structures with roots and nodes. Root is where the data originate and nodes are data point that are available to us. Node preceding is the parent and node that is after is the child. Last node is the leaves.
Uses:
Html pages, searching purposes
Linked list
Linear data structures that are not stored consequently but are linked to each other using pointers. Node is composed of data and a pointers called the nest. These are used in image viewing applications
Graph
Used to store data collection of point called
Uses
Google maps, uber to find the shortest distance
Hashmaps
Same as dictionary
Used in phone books, populate data according to the data
=
Algorithms
These are rules or instructions that are formulated in a finite, sequential order to solve problems. They provide pseudocode for problems for various languages.
Process for writing algorithms
Identify the problem
Identify starting point
Determine end point
Formulate intermediate steps
Review steps
Can be done depending on user preferences
Elements
Defined output and input
Flexibility
Algorithm Classes
Greedy algorithms- This involves taking the easiest step without worrying about future complexity
Dynamic programming- Divide problem into sections and remember the result of each section and apply to similar ones.
Divide and Conquer- Divides problems into sections and solve them separately
Tree Traversal algorithms
This refers to visiting each node present in the tree exactly once in order to update
Types of tree traversals
In-order traversal- refers to visiting the left nodes followed by the root and then right
Post-order traversal- refers to visiting the left nodes followed by the right nodes and then root node
Pre-order traversal- refers to visiting the root nodes and then right nodes.
Sorting Algorithms
Sorting algorithms denote the ways to arrange data in a particular format. Sorting ensures that data searching is optimized to a high level and that the data is
• Bubble Sort – This algorithm is based on comparison in which there is repeated swapping of adjacent elements if they are in an incorrect order.
• Merge Sort – Based on the divide and conquer algorithm, Merge sort divides the Array into two halves, sorts them, and then combines them.
• Insertion Sort – This sorting begins with comparing and sorting the first two elements. Then, the third element is compared with the two previously sorted elements and so on.
• Shell Sort – It is a form of Insertion sort, but here, far away elements are sorted. A large sub-list of a given list is sorted, and the size of the list is progressively reduced until all the elements are sorted.
• Selection Sort – This algorithm begins by finding the minimum value from a list of elements and puts it into a sorted list. The process is then repeated for each of the remaining elements in the list which is unsorted. The new element entering the sorted list is compared with its existing elements and placed at the correct position. The process goes on until all the elements are sorted.
Searching Algorithms
Searching algorithms help in checking and retrieving an element from different data structures. One type of searching algorithm applies the method of sequential search where the list is sequentially traversed, and every element is checked (linear search). In another type, the interval search, elements are searched for in sorted data structures (binary search). Let us look at some of the examples:
• Linear Search – In this algorithm, each item is sequentially searched one by one.
• Binary Search – The search interval is repeatedly divided in half. If the element to be searched is lower than the central component of the interval, the interval is narrowed to the lower half. Otherwise, it is narrowed to the upper half. The process is repeated until the value is found.
Graph Algorithms
There are two methods of traversing graphs using their edges. These are:
• Depth-first Traversal (DFS) – In this algorithm, a graph is traversed in a depthward motion. When any iteration faces a dead end, a stack is used to go to the next vertex and start a search. DFS is implemented in Python using the set data types.
• Breadth-first Traversal (BFS) – In this algorithm, a graph is traversed in a breadthward motion. When any iteration faces a dead end, a queue is used to go to the next vertex and start a search. BFS is implemented in Python using the queue data structure.
Algorithm Analysis
• A Priori Analysis – This represents a theoretical analysis of the algorithm before its implementation. An algorithm’s efficiency is measured by presuming that factors, such as processor speed, are constant and have no consequence on the algorithm.
• A Posterior Analysis – This refers to the empirical analysis of the algorithm after its implementation. A programming language is used to implement the selected algorithm, followed by its execution on a computer. This analysis collects statistics, such as the time and space required for the algorithm to run.
Top comments (0)