Python – Recursion ”; Previous Next Recursion allows a function to call itself. Fixed steps of code get executed again and again for new values. We also have to set criteria for deciding when the recursive call ends. In the below example we see a recursive approach to the binary search. We take a sorted list and give its index range as input to the recursive function. Binary Search using Recursion We implement the algorithm of binary search using python as shown below. We use an ordered list of items and design a recursive function to take in the list along with starting and ending index as input. Then, the binary search function calls itself till find the searched item or concludes about its absence in the list. Example def bsearch(list, idx0, idxn, val): if (idxn < idx0): return None else: midval = idx0 + ((idxn – idx0) // 2) # Compare the search item with middle most value if list[midval] > val: return bsearch(list, idx0, midval-1,val) else if list[midval] < val: return bsearch(list, midval+1, idxn, val) else: return midval list = [8,11,24,56,88,131] print(bsearch(list, 0, 5, 24)) print(bsearch(list, 0, 5, 51)) Output When the above code is executed, it produces the following result − 2 None Print Page Previous Next Advertisements ”;
Category: python Data Structure
Python – Hash Table
Python – Hash Table ”; Previous Next Hash tables are a type of data structure in which the address or the index value of the data element is generated from a hash function. That makes accessing the data faster as the index value behaves as a key for the data value. In other words Hash table stores key-value pairs but the key is generated through a hashing function. So the search and insertion function of a data element becomes much faster as the key values themselves become the index of the array which stores the data. In Python, the Dictionary data types represent the implementation of hash tables. The Keys in the dictionary satisfy the following requirements. The keys of the dictionary are hashable i.e. the are generated by hashing function which generates unique result for each unique value supplied to the hash function. The order of data elements in a dictionary is not fixed. So we see the implementation of hash table by using the dictionary data types as below. Accessing Values in Dictionary To access dictionary elements, you can use the familiar square brackets along with the key to obtain its value. Example # Declare a dictionary dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} # Accessing the dictionary with its key print (“dict[”Name”]: “, dict[”Name”]) print (“dict[”Age”]: “, dict[”Age”]) Output When the above code is executed, it produces the following result − dict[”Name”]: Zara dict[”Age”]: 7 Updating Dictionary You can update a dictionary by adding a new entry or a key-value pair, modifying an existing entry, or deleting an existing entry as shown below in the simple example − Example # Declare a dictionary dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} dict[”Age”] = 8; # update existing entry dict[”School”] = “DPS School”; # Add new entry print (“dict[”Age”]: “, dict[”Age”]) print (“dict[”School”]: “, dict[”School”]) Output When the above code is executed, it produces the following result − dict[”Age”]: 8 dict[”School”]: DPS School Delete Dictionary Elements You can either remove individual dictionary elements or clear the entire contents of a dictionary. You can also delete entire dictionary in a single operation.To explicitly remove an entire dictionary, just use the del statement. Example dict = {”Name”: ”Zara”, ”Age”: 7, ”Class”: ”First”} del dict[”Name”]; # remove entry with key ”Name” dict.clear(); # remove all entries in dict del dict ; # delete entire dictionary print (“dict[”Age”]: “, dict[”Age”]) print (“dict[”School”]: “, dict[”School”]) Output This produces the following result. Note that an exception is raised because after del dict dictionary does not exist anymore. dict[”Age”]: dict[”Age”] dict[”School”]: dict[”School”] Print Page Previous Next Advertisements ”;
Python – Algorithm Design
Python – Algorithm Design ”; Previous Next Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. From the data structure point of view, following are some important categories of algorithms − Search − Algorithm to search an item in a data structure. Sort − Algorithm to sort items in a certain order. Insert − Algorithm to insert item in a data structure. Update − Algorithm to update an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure. Characteristics of an Algorithm Not all procedures can be called an algorithm. An algorithm should have the following characteristics − Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. Finiteness − Algorithms must terminate after a finite number of steps. Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code. How to Write an Algorithm? There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code. As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm. We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution. Example Let”s try to learn algorithm-writing by using an example. Problem − Design an algorithm to add two numbers and display the result. step 1 − START step 2 − declare three integers a, b & c step 3 − define values of a & b step 4 − add values of a & b step 5 − store output of step 4 to c step 6 − print c step 7 − STOP Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as − step 1 − START ADD step 2 − get values of a & b step 3 − c ← a + b step 4 − display c step 5 − STOP In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing. Writing step numbers, is optional. We design an algorithm to get a solution of a given problem. A problem can be solved in more than one ways. Hence, many solution algorithms can be derived for a given problem. The next step is to analyze those proposed solution algorithms and implement the best suitable solution. Print Page Previous Next Advertisements ”;
Python – Queue
Python – Queue ”; Previous Next We are familiar with queue in our day to day life as we wait for a service. The queue data structure aslo means the same where the data elements are arranged in a queue. The uniqueness of queue lies in the way items are added and removed. The items are allowed at on end but removed form the other end. So it is a First-in-First out method. A queue can be implemented using python list where we can use the insert() and pop() methods to add and remove elements. Their is no insertion as data elements are always added at the end of the queue. Adding Elements In the below example we create a queue class where we implement the First-in-First-Out method. We use the in-built insert method for adding data elements. Example class Queue: def __init__(self): self.queue = list() def addtoq(self,dataval): # Insert method to add element if dataval not in self.queue: self.queue.insert(0,dataval) return True return False def size(self): return len(self.queue) TheQueue = Queue() TheQueue.addtoq(“Mon”) TheQueue.addtoq(“Tue”) TheQueue.addtoq(“Wed”) print(TheQueue.size()) Output When the above code is executed, it produces the following result − 3 Removing Element In the below example we create a queue class where we insert the data and then remove the data using the in-built pop method. Example class Queue: def __init__(self): self.queue = list() def addtoq(self,dataval): # Insert method to add element if dataval not in self.queue: self.queue.insert(0,dataval) return True return False # Pop method to remove element def removefromq(self): if len(self.queue)>0: return self.queue.pop() return (“No elements in Queue!”) TheQueue = Queue() TheQueue.addtoq(“Mon”) TheQueue.addtoq(“Tue”) TheQueue.addtoq(“Wed”) print(TheQueue.removefromq()) print(TheQueue.removefromq()) Output When the above code is executed, it produces the following result − Mon Tue Print Page Previous Next Advertisements ”;
Python – Binary Tree
Python – Binary Tree ”; Previous Next Tree represents the nodes connected by edges. It is a non-linear data structure. It has the following properties − One node is marked as Root node. Every node other than the root is associated with one parent node. Each node can have an arbiatry number of chid node. We create a tree data structure in python by using the concept os node discussed earlier. We designate one node as root node and then add more nodes as child nodes. Below is program to create the root node. Create Root We just create a Node class and add assign a value to the node. This becomes tree with only a root node. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data def PrintTree(self): print(self.data) root = Node(10) root.PrintTree() Output When the above code is executed, it produces the following result − 10 Inserting into a Tree To insert into a tree we use the same node class created above and add a insert class to it. The insert class compares the value of the node to the parent node and decides to add it as a left node or a right node. Finally the PrintTree class is used to print the tree. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data def insert(self, data): # Compare the new value with the parent node if self.data: if data self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Use the insert method to add nodes root = Node(12) root.insert(6) root.insert(14) root.insert(3) root.PrintTree() Output When the above code is executed, it produces the following result − 3 6 12 14 Traversing a Tree The tree can be traversed by deciding on a sequence to visit each node. As we can clearly see we can start at a node then visit the left sub-tree first and right sub-tree next. Or we can also visit the right sub-tree first and left sub-tree next. Accordingly there are different names for these tree traversal methods. Tree Traversal Algorithms Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree. In-order Traversal Pre-order Traversal Post-order Traversal In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the In-order traversal logic is implemented by creating an empty list and adding the left node first followed by the root or parent node. At last the left node is added to complete the In-order traversal. Please note that this process is repeated for each sub-tree until all the nodes are traversed. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Inorder traversal # Left -> Root -> Right def inorderTraversal(self, root): res = [] if root: res = self.inorderTraversal(root.left) res.append(root.data) res = res + self.inorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.inorderTraversal(root)) Output When the above code is executed, it produces the following result − [10, 14, 19, 27, 31, 35, 42] Pre-order Traversal In this traversal method, the root node is visited first, then the left subtree and finally the right subtree. In the below python program, we use the Node class to create place holders for the root node as well as the left and right nodes. Then, we create an insert function to add data to the tree. Finally, the Pre-order traversal logic is implemented by creating an empty list and adding the root node first followed by the left node. At last, the right node is added to complete the Pre-order traversal. Please note that, this process is repeated for each sub-tree until all the nodes are traversed. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() # Preorder traversal # Root -> Left ->Right def PreorderTraversal(self, root): res = [] if root: res.append(root.data) res = res + self.PreorderTraversal(root.left) res = res + self.PreorderTraversal(root.right) return res root = Node(27) root.insert(14) root.insert(35) root.insert(10) root.insert(19) root.insert(31) root.insert(42) print(root.PreorderTraversal(root)) Output When the above code is executed, it produces the following result − [27, 14, 10, 19, 35, 31, 42] Post-order Traversal In this traversal method, the root node is visited last, hence the name. First,
Python – Search Tree
Python – Search Tree ”; Previous Next A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties.The left sub-tree of a node has a key less than or equal to its parent node”s key.The right sub-tree of a node has a key greater than to its parent node”s key.Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree left_subtree (keys) ≤ node (key) ≤ right_subtree (keys) Search for a value in a B-tree Searching for a value in a tree involves comparing the incoming value with the value exiting nodes. Here also we traverse the nodes from left to right and then finally with the parent. If the searched for value does not match any of the exiting value, then we return not found message, or else the found message is returned. Example class Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert method to create nodes def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) else data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # findval method to compare the value with nodes def findval(self, lkpval): if lkpval < self.data: if self.left is None: return str(lkpval)+” Not Found” return self.left.findval(lkpval) else if lkpval > self.data: if self.right is None: return str(lkpval)+” Not Found” return self.right.findval(lkpval) else: print(str(self.data) + ” is found”) # Print the tree def PrintTree(self): if self.left: self.left.PrintTree() print( self.data), if self.right: self.right.PrintTree() root = Node(12) root.insert(6) root.insert(14) root.insert(3) print(root.findval(7)) print(root.findval(14)) Output When the above code is executed, it produces the following result − 7 Not Found 14 is found Print Page Previous Next Advertisements ”;
Python – Algorithm Classes
Python – Algorithm Classes ”; Previous Next Algorithms are unambiguous steps which should give us a well-defined output by processing zero or more inputs. This leads to many approaches in designing and writing the algorithms. It has been observed that most of the algorithms can be classified into the following categories. Greedy Algorithms Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions. So greedy algorithms look for a easy solution at that point in time without considering how it impacts the future steps. It is similar to how humans solve problems without going through the complete details of the inputs provided. Most networking algorithms use the greedy approach. Here is a list of few of them − Travelling Salesman Problem Prim”s Minimal Spanning Tree Algorithm Kruskal”s Minimal Spanning Tree Algorithm Dijkstra”s Minimal Spanning Tree Algorithm Divide and Conquer This class of algorithms involve dividing the given problem into smaller sub-problems and then solving each of the sub-problem independently. When the problem can not be further sub divided, we start merging the solution to each of the sub-problem to arrive at the solution for the bigger problem. The important examples of divide and conquer algorithms are − Merge Sort Quick Sort Kruskal”s Minimal Spanning Tree Algorithm Binary Search Dynamic Programming Dynamic programming involves dividing the bigger problem into smaller ones but unlike divide and conquer it does not involve solving each sub-problem independently. Rather the results of smaller sub-problems are remembered and used for similar or overlapping sub-problems. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems.Dynamic algorithms are motivated for an overall optimization of the problem and not the local optimization. The important examples of Dynamic programming algorithms are − Fibonacci number series Knapsack problem Tower of Hanoi Print Page Previous Next Advertisements ”;
Python – Divide and Conquer
Python – Divide and Conquer ”; Previous Next In divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the subproblems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those “atomic” smallest possible sub-problem (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem. Broadly, we can understand divide-and-conquer approach in a three-step process. Divide/Break This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in nature but still represent some part of the actual problem. Conquer/Solve This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered ”solved” on their own. Merge/Combine When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquer &s; merge steps works so close that they appear as one. Examples The following program is an example of divide-and-conquer programming approach where the binary search is implemented using python. Binary Search implementation In binary search we take a sorted list of elements and start looking for an element at the middle of the list. If the search value matches with the middle value in the list we complete the search. Otherwise we eleminate half of the list of elements by choosing whether to procees with the right or left half of the list depending on the value of the item searched. This is possible as the list is sorted and it is much quicker than linear search.Here we divide the given list and conquer by choosing the proper half of the list. We repeat this approcah till we find the element or conclude about it”s absence in the list. Example def bsearch(list, val): list_size = len(list) – 1 idx0 = 0 idxn = list_size # Find the middle most value while idx0 <= idxn: midval = (idx0 + idxn)// 2 if list[midval] == val: return midval # Compare the value the middle most value if val > list[midval]: idx0 = midval + 1 else: idxn = midval – 1 if idx0 > idxn: return None # Initialize the sorted list list = [2,7,19,34,53,72] # Print the search result print(bsearch(list,72)) print(bsearch(list,11)) Output When the above code is executed, it produces the following result − 5 None Print Page Previous Next Advertisements ”;
Python – Sets
Python – Sets ”; Previous Next Mathematically a set is a collection of items not in any particular order. A Python set is similar to this mathematical definition with below additional conditions. The elements in the set cannot be duplicates. The elements in the set are immutable(cannot be modified) but the set as a whole is mutable. There is no index attached to any element in a python set. So they do not support any indexing or slicing operation. Set Operations The sets in python are typically used for mathematical operations like union, intersection, difference and complement etc. We can create a set, access it’s elements and carry out these mathematical operations as shown below. Creating a set A set is created by using the set() function or placing all the elements within a pair of curly braces. Example Days=set([“Mon”,”Tue”,”Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) Months={“Jan”,”Feb”,”Mar”} Dates={21,22,17} print(Days) print(Months) print(Dates) Output When the above code is executed, it produces the following result. Please note how the order of the elements has changed in the result. set([”Wed”, ”Sun”, ”Fri”, ”Tue”, ”Mon”, ”Thu”, ”Sat”]) set([”Jan”, ”Mar”, ”Feb”]) set([17, 21, 22]) Accessing Values in a Set We cannot access individual values in a set. We can only access all the elements together as shown above. But we can also get a list of individual elements by looping through the set. Example Days=set([“Mon”,”Tue”,”Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) for d in Days: print(d) Output When the above code is executed, it produces the following result − Wed Sun Fri Tue Mon Thu Sat Adding Items to a Set We can add elements to a set by using add() method. Again as discussed there is no specific index attached to the newly added element. Example Days=set([“Mon”,”Tue”,”Wed”,”Thu”,”Fri”,”Sat”]) Days.add(“Sun”) print(Days) Output When the above code is executed, it produces the following result − set([”Wed”, ”Sun”, ”Fri”, ”Tue”, ”Mon”, ”Thu”, ”Sat”]) Removing Item from a Set We can remove elements from a set by using discard() method. Again as discussed there is no specific index attached to the newly added element. Example Days=set([“Mon”,”Tue”,”Wed”,”Thu”,”Fri”,”Sat”]) Days.discard(“Sun”) print(Days) Output When the above code is executed, it produces the following result. set([”Wed”, ”Fri”, ”Tue”, ”Mon”, ”Thu”, ”Sat”]) Union of Sets The union operation on two sets produces a new set containing all the distinct elements from both the sets. In the below example the element “Wed” is present in both the sets. Example DaysA = set([“Mon”,”Tue”,”Wed”]) DaysB = set([“Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) AllDays = DaysA|DaysB print(AllDays) Output When the above code is executed, it produces the following result. Please note the result has only one “wed”. set([”Wed”, ”Fri”, ”Tue”, ”Mon”, ”Thu”, ”Sat”]) Intersection of Sets The intersection operation on two sets produces a new set containing only the common elements from both the sets. In the below example the element “Wed” is present in both the sets. Example DaysA = set([“Mon”,”Tue”,”Wed”]) DaysB = set([“Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) AllDays = DaysA & DaysB print(AllDays) Output When the above code is executed, it produces the following result. Please note the result has only one “wed”. set([”Wed”]) Difference of Sets The difference operation on two sets produces a new set containing only the elements from the first set and none from the second set. In the below example the element “Wed” is present in both the sets so it will not be found in the result set. Example DaysA = set([“Mon”,”Tue”,”Wed”]) DaysB = set([“Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) AllDays = DaysA – DaysB print(AllDays) Output When the above code is executed, it produces the following result. Please note the result has only one “wed”. set([”Mon”, ”Tue”]) Compare Sets We can check if a given set is a subset or superset of another set. The result is True or False depending on the elements present in the sets. Example DaysA = set([“Mon”,”Tue”,”Wed”]) DaysB = set([“Mon”,”Tue”,”Wed”,”Thu”,”Fri”,”Sat”,”Sun”]) SubsetRes = DaysA <= DaysB SupersetRes = DaysB >= DaysA print(SubsetRes) print(SupersetRes) Output When the above code is executed, it produces the following result − True True Print Page Previous Next Advertisements ”;
Python – Dequeue
Python – Dequeue ”; Previous Next A double-ended queue, or deque, supports adding and removing elements from either end. The more commonly used stacks and queues are degenerate forms of deques, where the inputs and outputs are restricted to a single end. Example import collections DoubleEnded = collections.deque([“Mon”,”Tue”,”Wed”]) DoubleEnded.append(“Thu”) print (“Appended at right – “) print (DoubleEnded) DoubleEnded.appendleft(“Sun”) print (“Appended at right at left is – “) print (DoubleEnded) DoubleEnded.pop() print (“Deleting from right – “) print (DoubleEnded) DoubleEnded.popleft() print (“Deleting from left – “) print (DoubleEnded) Output When the above code is executed, it produces the following result − Appended at right – deque([”Mon”, ”Tue”, ”Wed”, ”Thu”]) Appended at right at left is – deque([”Sun”, ”Mon”, ”Tue”, ”Wed”, ”Thu”]) Deleting from right – deque([”Sun”, ”Mon”, ”Tue”, ”Wed”]) Deleting from left – deque([”Mon”, ”Tue”, ”Wed”]) Print Page Previous Next Advertisements ”;