## Data Structures and Algorithms

Data Structures and Algorithms

Data Structures and Algorithms in python. Data Structures are the building block of softwares, while algorithms are the actual process of building the software.

data structures are the building materials

algorithms is the act of building ie comparing to building a house.

tou need the right type of building materials to build a particular type of house, that same way you need some particular data types for a particular software. the you need to build in a particular way or steps to save time and resources, that is the algorithm

```
Data structures in Python
1. Built-in data structures
2. User-Defined structures
Built-in Data structures
1. Lists
2. Dictionary
3. Tuple
4. Set
User-Defined structures
1. stack
2. Queue
3. Tree
4. Linkedlist
5. Graph
6. HashMap
Built-in Data stuctures
Lists
- Lists can have heterogenous data types in them
- lists are mutable
Examples
1.
a=[12,"xyz",34]
print(a)
2.
b=[]
print(b)
3.
b.append(3)
print(b)
Tuples
- Tuples are not mutable
c=(3,4,5)
print(c)
c.append(6)
Dictionary
- Hold, key value pairs
- Dictionaries are mutable
d={1: "python", 2: "java"}
print(d)
Sets
- Un-ordered collection of unique elements
- Sets are mutable
e={2,3,4,2}
print(e)
User-Defined Data structure
1. Stack
- Stack are linear data structure which is based on the principle of last in first out
- The data to be entered last will be the first to be accessed
- It is built using array structure and has operations namely {pushing,popping}
2. Queues
_ Queue are linear Data structure based on first-in first-out
- The Data entered first will be accessed first
- It is also built using array structure and has operation which can be performed from both ends of the queue
3. Trees
- Trees are non-linear data structures which have root and node.
- The root is the node where the Data originate
_ Trees create hierachy that can be used in application such as HTML pages E.t.c.
4. Linked List
_ Linked List are linear Data structures which are linked with each other using pointer
_ The node of Linked List are composed of Data and pointers called the Nest.
_ These Structures are most widely used in Image viewing application and in Music player application.
5. Graphs
_ Graphs are used to store data collection of points and edges
_ Many application such as Google Map, Uber make use of Graphs
6. HashMaps
_ HashMaps are the the same to what Dictionary is in Python
_ They can be used to implement application such as phonebooks
Algoriths
Algorithm are rules or instructions that are formulated in a finite,sequential order to solve problems.
They are provided the pseudocode for problems.
Writing Algorithms
- Figure out what is the problem
- Determine where you need to statrt
- DEtermine where you need to stop
- Formulate the intermediate steps
- Review your steps
Elements of a good Algorithm
1. Steps should be finite, clear and understable
2. Clear and precise description of the input and the output
3. Each step must have a defined output that depends only on inputs in that step or the preceding steps
4. The algorithm should be flexible
5. The steps should make use of general programming fundamentals
Algorithm Classes
1. Divide and Conquer
2. Dynamic Programming
3. Greedy Algorithms
1. Divide and Conquer
Divides the problem into sub-part and solves each one separately
2. Dynamic Programming
Divides the problem into sub-parts, remembers the result of the sub-parts and applies it to similar ones
3. Greedy Algorithms
Involves taking the easiest step while solving a problem without worrying about the complexity of the future steps
Tree Travesal Algorithms
Trees in python are non-linear data structures having a root and nodes. Tree Traversal refers to
visiting each node present in the exactly once in order to update or check them.
Types of Tree Traversals
1. In-order traversal
2. Post-order traversal
3. Pre-order traversal
1. In-order Traversal refers to visiting the left nodes followed by the root and then right nodes
2. Post-order Traversal refers to the visiting the left nodes followed by the right nodes and then root node
3. Pre-order Traversal refers to visiting the root nodes followed by the left nodes and then right nodes
# creating a node class
class Node:
def_init_(self,val):
self.childleft = None
self.childright = None
self.nodedata = val
# Creating an instance of the Node classto constuct the tree
root = Node(1)
root.childleft = Node(2)
root.childright = Node(3)
root.childleft.childright = Node(4)
root.childleft.childright = Node(5)
def InOrd(root):
if root:
print (root.nodedata)
PreOrd(root.childleft)
PreOrd(root.childright)
PreOrd(root)
def PostOrd(root):
if root:
PostOrd(root.childleft)
PostOrd(root.childright)
print (root.nodedata)
postOrd(root)
```