problem solving using data structures in python

• Runestone in social media: Follow @iRunestone Our Facebook Page
• Table of Contents
• Assignments
• Peer Instruction (Instructor)
• Peer Instruction (Student)
• Change Course
• Instructor's Page
• Progress Page
• Edit Profile
• Change Password
• Scratch ActiveCode
• Scratch Activecode
• Instructors Guide
• About Runestone
• Report A Problem
• This Chapter
• 1. Introduction' data-toggle="tooltip" >

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College

There is a wonderful collection of YouTube videos recorded by Gerry Jenkins to support all of the chapters in this text.

• 1.1. Objectives
• 1.2. Getting Started
• 1.3. What Is Computer Science?
• 1.4. What Is Programming?
• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
• 1.7. Review of Basic Python
• 1.8.1. Built-in Atomic Data Types
• 1.8.2. Built-in Collection Data Types
• 1.9.1. String Formatting
• 1.10. Control Structures
• 1.11. Exception Handling
• 1.12. Defining Functions
• 1.13.1. A Fraction Class
• 1.13.2. Inheritance: Logic Gates and Circuits
• 1.14. Summary
• 1.15. Key Terms
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 2.1.1. A Basic implementation of the MSDie class
• 2.2. Making your Class Comparable
• 3.1. Objectives
• 3.2. What Is Algorithm Analysis?
• 3.3. Big-O Notation
• 3.4.1. Solution 1: Checking Off
• 3.4.2. Solution 2: Sort and Compare
• 3.4.3. Solution 3: Brute Force
• 3.4.4. Solution 4: Count and Compare
• 3.5. Performance of Python Data Structures
• 3.7. Dictionaries
• 3.8. Summary
• 3.9. Key Terms
• 3.10. Discussion Questions
• 3.11. Programming Exercises
• 4.1. Objectives
• 4.2. What Are Linear Structures?
• 4.3. What is a Stack?
• 4.4. The Stack Abstract Data Type
• 4.5. Implementing a Stack in Python
• 4.6. Simple Balanced Parentheses
• 4.7. Balanced Symbols (A General Case)
• 4.8. Converting Decimal Numbers to Binary Numbers
• 4.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 4.9.2. General Infix-to-Postfix Conversion
• 4.9.3. Postfix Evaluation
• 4.10. What Is a Queue?
• 4.11. The Queue Abstract Data Type
• 4.12. Implementing a Queue in Python
• 4.13. Simulation: Hot Potato
• 4.14.1. Main Simulation Steps
• 4.14.2. Python Implementation
• 4.14.3. Discussion
• 4.15. What Is a Deque?
• 4.16. The Deque Abstract Data Type
• 4.17. Implementing a Deque in Python
• 4.18. Palindrome-Checker
• 4.19. Lists
• 4.20. The Unordered List Abstract Data Type
• 4.21.1. The Node Class
• 4.21.2. The Unordered List Class
• 4.22. The Ordered List Abstract Data Type
• 4.23.1. Analysis of Linked Lists
• 4.24. Summary
• 4.25. Key Terms
• 4.26. Discussion Questions
• 4.27. Programming Exercises
• 5.1. Objectives
• 5.2. What Is Recursion?
• 5.3. Calculating the Sum of a List of Numbers
• 5.4. The Three Laws of Recursion
• 5.5. Converting an Integer to a String in Any Base
• 5.6. Stack Frames: Implementing Recursion
• 5.7. Introduction: Visualizing Recursion
• 5.8. Sierpinski Triangle
• 5.9. Complex Recursive Problems
• 5.10. Tower of Hanoi
• 5.11. Exploring a Maze
• 5.12. Dynamic Programming
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Glossary
• 5.17. Programming Exercises
• 6.1. Objectives
• 6.2. Searching
• 6.3.1. Analysis of Sequential Search
• 6.4.1. Analysis of Binary Search
• 6.5.1. Hash Functions
• 6.5.2. Collision Resolution
• 6.5.3. Implementing the Map Abstract Data Type
• 6.5.4. Analysis of Hashing
• 6.6. Sorting
• 6.7. The Bubble Sort
• 6.8. The Selection Sort
• 6.9. The Insertion Sort
• 6.10. The Shell Sort
• 6.11. The Merge Sort
• 6.12. The Quick Sort
• 6.13. Summary
• 6.14. Key Terms
• 6.15. Discussion Questions
• 6.16. Programming Exercises
• 7.1. Objectives
• 7.2. Examples of Trees
• 7.3. Vocabulary and Definitions
• 7.4. List of Lists Representation
• 7.5. Nodes and References
• 7.6. Parse Tree
• 7.7. Tree Traversals
• 7.8. Priority Queues with Binary Heaps
• 7.9. Binary Heap Operations
• 7.10.1. The Structure Property
• 7.10.2. The Heap Order Property
• 7.10.3. Heap Operations
• 7.11. Binary Search Trees
• 7.12. Search Tree Operations
• 7.13. Search Tree Implementation
• 7.14. Search Tree Analysis
• 7.15. Balanced Binary Search Trees
• 7.16. AVL Tree Performance
• 7.17. AVL Tree Implementation
• 7.18. Summary of Map ADT Implementations
• 7.19. Summary
• 7.20. Key Terms
• 7.21. Discussion Questions
• 7.22. Programming Exercises
• 8.1. Objectives
• 8.2. Vocabulary and Definitions
• 8.3. The Graph Abstract Data Type
• 8.4. An Adjacency Matrix
• 8.5. An Adjacency List
• 8.6. Implementation
• 8.7. The Word Ladder Problem
• 8.8. Building the Word Ladder Graph
• 8.9. Implementing Breadth First Search
• 8.10. Breadth First Search Analysis
• 8.11. The Knight’s Tour Problem
• 8.12. Building the Knight’s Tour Graph
• 8.13. Implementing Knight’s Tour
• 8.14. Knight’s Tour Analysis
• 8.15. General Depth First Search
• 8.16. Depth First Search Analysis
• 8.17. Topological Sorting
• 8.18. Strongly Connected Components
• 8.19. Shortest Path Problems
• 8.20. Dijkstra’s Algorithm
• 8.21. Analysis of Dijkstra’s Algorithm
• 8.22. Prim’s Spanning Tree Algorithm
• 8.23. Summary
• 8.24. Key Terms
• 8.25. Discussion Questions
• 8.26. Programming Exercises

Acknowledgements ¶

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables ¶

Search Page

• Table of Contents
• Scratch ActiveCode
• Navigation Help
• Help for Instructors
• About Runestone
• Report A Problem
• 1. Introduction
• 2. Analysis
• 3. Basic Data Structures
• 4. Recursion
• 5. Sorting and Searching
• 6. Trees and Tree Algorithms
• 7. Graphs and Graph Algorithms

Problem Solving with Algorithms and Data Structures using Python ¶

By Brad Miller and David Ranum, Luther College (as remixed by Jeffrey Elkner)

• 1.1. Objectives
• 1.2. Getting Started
• 1.3. What Is Computer Science?
• 1.4. What Is Programming?
• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
• 1.7. Review of Basic Python
• 1.8.1. Built-in Atomic Data Types
• 1.8.2. Built-in Collection Data Types
• 1.9.1. String Formatting
• 1.10. Control Structures
• 1.11. Exception Handling
• 1.12. Defining Functions
• 1.13.1. A Fraction Class
• 1.13.2. Inheritance: Logic Gates and Circuits
• 1.14. Summary
• 1.15. Key Terms
• 1.16. Discussion Questions
• 1.17. Programming Exercises
• 2.1. Objectives
• 2.2. What Is Algorithm Analysis?
• 2.3. Big-O Notation
• 2.4.1. Solution 1: Checking Off
• 2.4.2. Solution 2: Sort and Compare
• 2.4.3. Solution 3: Brute Force
• 2.4.4. Solution 4: Count and Compare
• 2.5. Performance of Python Data Structures
• 2.7. Dictionaries
• 2.8. Summary
• 2.9. Key Terms
• 2.10. Discussion Questions
• 2.11. Programming Exercises
• 3.1. Objectives
• 3.2. What Are Linear Structures?
• 3.3. What is a Stack?
• 3.4. The Stack Abstract Data Type
• 3.5. Implementing a Stack in Python
• 3.6. Simple Balanced Parentheses
• 3.7. Balanced Symbols (A General Case)
• 3.8. Converting Decimal Numbers to Binary Numbers
• 3.9.1. Conversion of Infix Expressions to Prefix and Postfix
• 3.9.2. General Infix-to-Postfix Conversion
• 3.9.3. Postfix Evaluation
• 3.10. What Is a Queue?
• 3.11. The Queue Abstract Data Type
• 3.12. Implementing a Queue in Python
• 3.13. Simulation: Hot Potato
• 3.14.1. Main Simulation Steps
• 3.14.2. Python Implementation
• 3.14.3. Discussion
• 3.15. What Is a Deque?
• 3.16. The Deque Abstract Data Type
• 3.17. Implementing a Deque in Python
• 3.18. Palindrome-Checker
• 3.19. Lists
• 3.20. The Unordered List Abstract Data Type
• 3.21.1. The Node Class
• 3.21.2. The Unordered List Class
• 3.22. The Ordered List Abstract Data Type
• 3.23.1. Analysis of Linked Lists
• 3.24. Summary
• 3.25. Key Terms
• 3.26. Discussion Questions
• 3.27. Programming Exercises
• 4.1. Objectives
• 4.2. What Is Recursion?
• 4.3. Calculating the Sum of a List of Numbers
• 4.4. The Three Laws of Recursion
• 4.5. Converting an Integer to a String in Any Base
• 4.6. Stack Frames: Implementing Recursion
• 4.7. Introduction: Visualizing Recursion
• 4.8. Sierpinski Triangle
• 4.9. Complex Recursive Problems
• 4.10. Tower of Hanoi
• 4.11. Exploring a Maze
• 4.12. Dynamic Programming
• 4.13. Summary
• 4.14. Key Terms
• 4.15. Discussion Questions
• 4.16. Glossary
• 4.17. Programming Exercises
• 5.1. Objectives
• 5.2. Searching
• 5.3.1. Analysis of Sequential Search
• 5.4.1. Analysis of Binary Search
• 5.5.1. Hash Functions
• 5.5.2. Collision Resolution
• 5.5.3. Implementing the Map Abstract Data Type
• 5.5.4. Analysis of Hashing
• 5.6. Sorting
• 5.7. The Bubble Sort
• 5.8. The Selection Sort
• 5.9. The Insertion Sort
• 5.10. The Shell Sort
• 5.11. The Merge Sort
• 5.12. The Quick Sort
• 5.13. Summary
• 5.14. Key Terms
• 5.15. Discussion Questions
• 5.16. Programming Exercises
• 6.1. Objectives
• 6.2. Examples of Trees
• 6.3. Vocabulary and Definitions
• 6.4. List of Lists Representation
• 6.5. Nodes and References
• 6.6. Parse Tree
• 6.7. Tree Traversals
• 6.8. Priority Queues with Binary Heaps
• 6.9. Binary Heap Operations
• 6.10.1. The Structure Property
• 6.10.2. The Heap Order Property
• 6.10.3. Heap Operations
• 6.11. Binary Search Trees
• 6.12. Search Tree Operations
• 6.13. Search Tree Implementation
• 6.14. Search Tree Analysis
• 6.15. Balanced Binary Search Trees
• 6.16. AVL Tree Performance
• 6.17. AVL Tree Implementation
• 6.18. Summary of Map ADT Implementations
• 6.19. Summary
• 6.20. Key Terms
• 6.21. Discussion Questions
• 6.22. Programming Exercises
• 7.1. Objectives
• 7.2. Vocabulary and Definitions
• 7.3. The Graph Abstract Data Type
• 7.4. An Adjacency Matrix
• 7.5. An Adjacency List
• 7.6. Implementation
• 7.7. The Word Ladder Problem
• 7.8. Building the Word Ladder Graph
• 7.9. Implementing Breadth First Search
• 7.10. Breadth First Search Analysis
• 7.11. The Knight’s Tour Problem
• 7.12. Building the Knight’s Tour Graph
• 7.13. Implementing Knight’s Tour
• 7.14. Knight’s Tour Analysis
• 7.15. General Depth First Search
• 7.16. Depth First Search Analysis
• 7.17. Topological Sorting
• 7.18. Strongly Connected Components
• 7.19. Shortest Path Problems
• 7.20. Dijkstra’s Algorithm
• 7.21. Analysis of Dijkstra’s Algorithm
• 7.22. Prim’s Spanning Tree Algorithm
• 7.23. Summary
• 7.24. Key Terms
• 7.25. Discussion Questions
• 7.26. Programming Exercises

Acknowledgements ¶

We are very grateful to Franklin Beedle Publishers for allowing us to make this interactive textbook freely available. This online version is dedicated to the memory of our first editor, Jim Leisy, who wanted us to “change the world.”

Indices and tables ¶

• Module Index
• Search Page

• Python Basics
• Interview Questions
• Python Quiz
• Popular Packages
• Python Projects
• Practice Python
• AI With Python
• Learn Python3
• Python Automation
• Python Web Dev
• DSA with Python
• Python OOPs
• Dictionaries
• Learn Data Structures and Algorithms | DSA Tutorial
• Python Data Structures and Algorithms
• What Should I Learn First: Data Structures or Algorithms?
• Why Every Developer Should Learn Data Structures and Algorithms?
• Data Structures and Algorithms (DSA) MCQ Quiz Online
• Top Reasons for Failure in Data Structures and Algorithms
• What to do if I get stuck in Data Structures and Algorithms (DSA)?
• Real-life Applications of Data Structures and Algorithms (DSA)
• How can one become good at Data structures and Algorithms easily?
• Maths for Data Structure and Algorithms (DSA) | A Complete Guide
• Top 100 Data Structure and Algorithms DSA Interview Questions Topic-wise
• Data Structures & Algorithms (DSA) Guide for Google Tech interviews
• Data Structures & Algorithms Guide for Developers
• Best Data Structures and Algorithms Books
• Data Structures and Algorithms Online Courses : Free and Paid
• Most Asked Problems in Data Structures and Algorithms | Beginner DSA Sheet
• Learn Data Structures and Algorithms for your Dream Job with this online Course
• Walk-Through DSA3 : Data Structures and Algorithms Online Course by GeeksforGeeks
• Top Data Structures and Algorithms Courses for Java Developers [2024]
• Data Structures and Algorithms Complete Guide using C++

Learn DSA with Python | Python Data Structures and Algorithms

This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists , trees , graphs , etc, and traversal as well as searching and sorting algorithms with the help of good and well-explained examples and practice questions.

Python Lists are ordered collections of data just like arrays in other programming languages. It allows different types of elements in the list. The implementation of Python List is similar to Vectors in C++ or ArrayList in JAVA. The costly operation is inserting or deleting the element from the beginning of the List as all the elements are needed to be shifted. Insertion and deletion at the end of the list can also become costly in the case where the preallocated memory becomes full.

Example: Creating Python List

List elements can be accessed by the assigned index. In python starting index of the list, a sequence is 0 and the ending index is (if N elements are there) N-1.

Example: Python List Operations

Python tuples are similar to lists but Tuples are immutable in nature i.e. once created it cannot be modified. Just like a List, a Tuple can also contain elements of various types.

In Python, tuples are created by placing a sequence of values separated by ‘comma’ with or without the use of parentheses for grouping of the data sequence. 

Note: To create a tuple of one element there must be a trailing comma. For example, (8,) will create a tuple containing 8 as the element.

Example: Python Tuple Operations

Python set is a mutable collection of data that does not allow any duplication. Sets are basically used to include membership testing and eliminating duplicate entries. The data structure used in this is Hashing, a popular technique to perform insertion, deletion, and traversal in O(1) on average. 

If Multiple values are present at the same index position, then the value is appended to that index position, to form a Linked List. In, CPython Sets are implemented using a dictionary with dummy variables, where key beings the members set with greater optimizations to the time complexity.

Set Implementation:

Sets with Numerous operations on a single HashTable:

Example: Python Set Operations

Frozen sets.

Frozen sets in Python are immutable objects that only support methods and operators that produce a result without affecting the frozen set or sets to which they are applied. While elements of a set can be modified at any time, elements of the frozen set remain the same after creation.

Example: Python Frozen set

Python Strings is the immutable array of bytes representing Unicode characters. Python does not have a character data type, a single character is simply a string with a length of 1.

Note: As strings are immutable, modifying a string will result in creating a new copy.

Example: Python Strings Operations

Python dictionary is an unordered collection of data that stores data in the format of key:value pair. It is like hash tables in any other language with the time complexity of O(1). Indexing of Python Dictionary is done with the help of keys. These are of any hashable type i.e. an object whose can never change like strings, numbers, tuples, etc. We can create a dictionary by using curly braces ({}) or dictionary comprehension.

Example: Python Dictionary Operations

A matrix is a 2D array where each element is of strictly the same size. To create a matrix we will be using the NumPy package .

Example: Python NumPy Matrix Operations

Python Bytearray gives a mutable sequence of integers in the range 0 <= x < 256.

Example: Python Bytearray Operations

Linked list.

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least two parts:

• Pointer (Or Reference) to the next node

Example: Defining Linked List in Python

Let us create a simple linked list with 3 nodes.

Linked List Traversal 

In the previous program, we have created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose function printList() that prints any given list.

More articles on Linked List

• Linked List Insertion
• Linked List Deletion (Deleting a given key)
• Linked List Deletion (Deleting a key at given position)
• Find Length of a Linked List (Iterative and Recursive)
• Search an element in a Linked List (Iterative and Recursive)
• Nth node from the end of a Linked List
• Reverse a linked list

>>> More

A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an element is removed from that end only. The insert and delete operations are often called push and pop.

The functions associated with stack are:

• empty() – Returns whether the stack is empty – Time Complexity: O(1)
• size() – Returns the size of the stack – Time Complexity: O(1)
• top() – Returns a reference to the topmost element of the stack – Time Complexity: O(1)
• push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
• pop() – Deletes the topmost element of the stack – Time Complexity: O(1)

More articles on Stack

• Infix to Postfix Conversion using Stack
• Prefix to Infix Conversion
• Prefix to Postfix Conversion
• Postfix to Prefix Conversion
• Postfix to Infix
• Check for balanced parentheses in an expression
• Evaluation of Postfix Expression

As a stack, the queue is a linear data structure that stores items in a First In First Out (FIFO) manner. With a queue, the least recently added item is removed first. A good example of the queue is any queue of consumers for a resource where the consumer that came first is served first.

Operations associated with queue are:

• Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity: O(1)
• Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity: O(1)
• Front: Get the front item from queue – Time Complexity: O(1)
• Rear: Get the last item from queue – Time Complexity: O(1)

More articles on Queue

• Implement Queue using Stacks
• Implement Stack using Queues
• Implement a stack using single queue

Priority Queue

Priority Queues are abstract data structures where each data/value in the queue has a certain priority. For example, In airlines, baggage with the title “Business” or “First-class” arrives earlier than the rest. Priority Queue is an extension of the queue with the following properties.

• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue.

heapq module in Python provides the heap data structure that is mainly used to represent a priority queue. The property of this data structure is that it always gives the smallest element (min heap) whenever the element is popped. Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time. It supports the extraction and insertion of the smallest element in the O(log n) times.

Generally, Heaps can be of two types:

• Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
• Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

More Articles on Heap

• Binary Heap
• K’th Largest Element in an array
• K’th Smallest/Largest Element in Unsorted Array
• Sort an almost sorted array
• K-th Largest Sum Contiguous Subarray
• Minimum sum of two numbers formed from digits of an array

Binary Tree

A tree is a  hierarchical data structure that looks like the below figure –

The topmost node of the tree is called the root whereas the bottommost nodes or the nodes with no children are called the leaf nodes. The nodes that are directly under a node are called its children and the nodes that are directly above something are called its parent.

A binary tree is a tree whose elements can have almost two children. Since each element in a binary tree can have only 2 children, we typically name them the left and right children. A Binary Tree node contains the following parts.

• Pointer to left child
• Pointer to the right child

Example: Defining Node Class

Now let’s create a tree with 4 nodes in Python. Let’s assume the tree structure looks like below –

Example: Adding data to the tree

Tree traversal.

Trees can be traversed in different ways. Following are the generally used ways for traversing trees. Let us consider the below tree –

Depth First Traversals:

• Inorder (Left, Root, Right) : 4 2 5 1 3
• Preorder (Root, Left, Right) : 1 2 4 5 3
• Postorder (Left, Right, Root) : 4 5 2 3 1

Algorithm Inorder(tree)

• Traverse the left subtree, i.e., call Inorder(left-subtree)
• Visit the root.
• Traverse the right subtree, i.e., call Inorder(right-subtree)

Algorithm Preorder(tree)

• Traverse the left subtree, i.e., call Preorder(left-subtree)
• Traverse the right subtree, i.e., call Preorder(right-subtree)

Algorithm Postorder(tree)

• Traverse the left subtree, i.e., call Postorder(left-subtree)
• Traverse the right subtree, i.e., call Postorder(right-subtree)

Time Complexity –  O(n)

Breadth-First or Level Order Traversal

Level order traversal of a tree is breadth-first traversal for the tree. The level order traversal of the above tree is 1 2 3 4 5.

For each node, first, the node is visited and then its child nodes are put in a FIFO queue. Below is the algorithm for the same –

• Create an empty queue q
• temp_node = root /*start from root*/
• print temp_node->data.
• Enqueue temp_node’s children (first left then right children) to q
• Dequeue a node from q

Time Complexity: O(n) 

More articles on Binary Tree

• Insertion in a Binary Tree
• Deletion in a Binary Tree
• Inorder Tree Traversal without Recursion
• Inorder Tree Traversal without recursion and without stack!
• Print Postorder traversal from given Inorder and Preorder traversals
• Find postorder traversal of BST from preorder traversal

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

The above properties of the Binary Search Tree provide an ordering among keys so that the operations like search, minimum and maximum can be done fast. If there is no order, then we may have to compare every key to search for a given key.

Searching Element

• Start from the root.
• Compare the searching element with root, if less than root, then recurse for left, else recurse for right.
• If the element to search is found anywhere, return true, else return false.

Insertion of a key 

• Compare the inserting element with root, if less than root, then recurse for left, else recurse for right.
• After reaching the end, just insert that node at left(if less than current) else right.

More Articles on Binary Search Tree

• Binary Search Tree – Delete Key
• Construct BST from given preorder traversal | Set 1
• Binary Tree to Binary Search Tree Conversion
• Find the node with minimum value in a Binary Search Tree
• A program to check if a binary tree is BST or not

A graph is a nonlinear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as a Graph consisting of a finite set of vertices(or nodes) and a set of edges that connect a pair of nodes.

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges E = {01, 12, 23, 34, 04, 14, 13}. The following two are the most commonly used representations of a graph.

Adjacency Matrix

Adjacency list.

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. The adjacency matrix for an undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w. 

Vertices of Graph [‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’] Edges of Graph [(‘a’, ‘c’, 20), (‘a’, ‘e’, 10), (‘b’, ‘c’, 30), (‘b’, ‘e’, 40), (‘c’, ‘a’, 20), (‘c’, ‘b’, 30), (‘d’, ‘e’, 50), (‘e’, ‘a’, 10), (‘e’, ‘b’, 40), (‘e’, ‘d’, 50), (‘e’, ‘f’, 60), (‘f’, ‘e’, 60)] Adjacency Matrix of Graph [[-1, -1, 20, -1, 10, -1], [-1, -1, 30, -1, 40, -1], [20, 30, -1, -1, -1, -1], [-1, -1, -1, -1, 50, -1], [10, 40, -1, 50, -1, 60], [-1, -1, -1, -1, 60, -1]]

An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above graph. 

Graph Traversal

Breadth-first search or bfs.

Breadth-First Traversal for a graph is similar to Breadth-First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.

For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth-First Traversal of the following graph is 2, 0, 3, 1.

Time Complexity: O(V+E) where V is the number of vertices in the graph and E is the number of edges in the graph.

Depth First Search or DFS

Depth First Traversal for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, a node may be visited twice. To avoid processing a node more than once, use a boolean visited array.

• Create a recursive function that takes the index of the node and a visited array.
• Mark the current node as visited and print the node.
• Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

More articles on graph

• Graph representations using set and hash
• Find Mother Vertex in a Graph
• Iterative Depth First Search
• Count the number of nodes at given level in a tree using BFS
• Count all possible paths between two vertices

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function . Using the recursive algorithms, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

What is the base condition in recursion?

In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems. 

In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.

How memory is allocated to different function calls in recursion?

When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to the calling function and a different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.

Let us take the example of how recursion works by taking a simple function. 

The memory stack has been shown in below diagram.

More articles on Recursion

• Recursion in Python
• Practice Questions for Recursion | Set 1
• Practice Questions for Recursion | Set 2
• Practice Questions for Recursion | Set 3
• Practice Questions for Recursion | Set 4
• Practice Questions for Recursion | Set 5
• Practice Questions for Recursion | Set 6
• Practice Questions for Recursion | Set 7

Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial. For example, if we write simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

Tabulation vs Memoization

There are two different ways to store the values so that the values of a sub-problem can be reused. Here, will discuss two patterns of solving dynamic programming (DP) problem: 

• Tabulation: Bottom Up
• Memoization: Top Down

As the name itself suggests starting from the bottom and accumulating answers to the top. Let’s discuss in terms of state transition.

Let’s describe a state for our DP problem to be dp[x] with dp[0] as base state and dp[n] as our destination state. So,  we need to find the value of destination state i.e dp[n].

If we start our transition from our base state i.e dp[0] and follow our state transition relation to reach our destination state dp[n], we call it the Bottom-Up approach as it is quite clear that we started our transition from the bottom base state and reached the topmost desired state.

Now, Why do we call it tabulation method?

To know this let’s first write some code to calculate the factorial of a number using bottom up approach. Once, again as our general procedure to solve a DP we first define a state. In this case, we define a state as dp[x], where dp[x] is to find the factorial of x.

Now, it is quite obvious that dp[x+1] = dp[x] * (x+1)

Memoization

Once, again let’s describe it in terms of state transition. If we need to find the value for some state say dp[n] and instead of starting from the base state that i.e dp[0] we ask our answer from the states that can reach the destination state dp[n] following the state transition relation, then it is the top-down fashion of DP.

Here, we start our journey from the top most destination state and compute its answer by taking in count the values of states that can reach the destination state, till we reach the bottom-most base state.

Once again, let’s write the code for the factorial problem in the top-down fashion

More articles on Dynamic Programming

• Optimal Substructure Property
• Overlapping Subproblems Property
• Fibonacci numbers
• Subset with sum divisible by m
• Maximum Sum Increasing Subsequence
• Longest Common Substring

Searching Algorithms

Linear search.

• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of the elements, return -1.

The time complexity of the above algorithm is O(n). 

For more information, refer to Linear Search .

Binary Search

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The time complexity of the above algorithm is O(log(n)). 

For more information, refer to Binary Search .

Sorting Algorithms

Selection sort.

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. 

Flowchart of the Selection Sort: 

Time Complexity: O(n 2 ) as there are two nested loops.

Auxiliary Space: O(1) 

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Illustration : 

Time Complexity: O(n 2 )

Insertion Sort

To sort an array of size n in ascending order using insertion sort :

• Iterate from arr[1] to arr[n] over the array.
• Compare the current element (key) to its predecessor.
• If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Illustration:

Time Complexity: O(n 2 ))

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. 

Time Complexity: O(n(logn))

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Always pick first element as pivot.

• Always pick last element as pivot (implemented below)
• Pick a random element as pivot.
• Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Partition Algorithm

There can be many ways to do partition, following pseudo code adopts the method given in CLRS book. The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element. 

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow the exchange of far items. In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h th element is sorted.

Time Complexity:  O(n 2 ). 

Please Login to comment...

Similar reads.

• Python-Data-Structures

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Learn Algorithms and Data Structures in Python

Algorithms and data structures are important for most programmers to understand.

We just released a course on the freeCodeCamp YouTube channel that is a beginner-friendly introduction to common data structures (linked lists, stacks, queues, graphs) and algorithms (search, sorting, recursion, dynamic programming) in Python.

This course will help you prepare for coding interviews and assessments. In this course, you will:

• Watch live hands-on coding-focused video tutorials
• Practice coding with cloud Jupyter notebooks
• Solve questions from real programming interviews

Aakash N S teaches this course. He is the co-founder and CEO of Jovian and has created many popular courses about machine learning and programming.

The course is broken up into a series of lessons, assignments, and projects. There are Jupyter Notebook files to go along with each section.

Here is what is covered in the course:

Lesson 1 - Binary Search, Linked Lists and Complexity

• Linear and Binary Search
• Complexity and Big O Notation
• Linked Lists using Python Classes

Assignment 1 - Binary Search Practice

• Understand and solve a problem systematically
• Implement linear search and analyze it
• Optimize the solution using binary search

Lesson 2 - Binary Search Trees, Traversals and Recursion

• Binary trees, traversals, and recursion
• Binary search trees & common operations
• Balanced binary trees and optimizations

Assignment 2 - Hash Tables and Python Dictionaries

• Hash tables from scratch in Python
• Handling collisions using linear probing
• Replicating Python dictionaries

Lesson 3 - Sorting Algorithms and Divide & Conquer

• Bubble sort and Insertion Sort
• Merge sort using Divide & Conquer
• Quicksort and average complexity

Assignment 3 - Divide and Conquer Practice

• Implement polynomial multiplication
• Optimize using divide and conquer
• Analyze time and space complexity

Lesson 4 - Recursion and Dynamic Programming

• Recursion and memoization
• Subsequence and knapsack problems
• Backtracking and pruning

Lesson 5 - Graph Algorithms (BFS, DFS & Shortest Paths)

• Graphs, trees, and adjacency lists
• Breadth-first and depth-first search
• Shortest paths and directed graphs

Project - Step-by-Step Solution to a Programming Problem

• Pick an interesting coding problem
• Solve the problem step-by-step
• Document and present the solution

Lesson 6 - Python Interview Questions, Tips & Advice

• Practice questions and solutions
• Tips for solving coding challenges
• Advice for cracking coding interviews

Watch the course below or on the freeCodeCamp.org YouTube channel (13-hour watch).

I'm a teacher and developer with freeCodeCamp.org. I run the freeCodeCamp.org YouTube channel.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

How Do You Use Data Structures and Algorithms in Python?

Data structures and algorithms allow us to organize, store and manage data for efficient access and modification. But which structures and algorithms do you use for your project? Let’s start with the simple stuff.

Data Structures and Algorithms in Python

Built-in data structures, user-defined data structures.

• Tree Traversal Algorithms
• Sorting Algorithms

Searching Algorithms

First, let’s take a look at four built-in data structures in Python: list, tuple, set, and dictionary.

We define a list using square brackets that hold data separated by commas. The list is mutable, ordered and can contain a mix of data types.

Our output will look like this:

Below there are some useful functions for the list.

A tuple is another container. It’s a data type for immutable ordered sequences of elements. A tuple is immutable because you can’t add or remove elements from them, nor can you sort them in place.

​​​​​Set is a mutable and unordered collection of unique elements. It permits us to remove duplicates from a list quickly.

The output will look like this:

Dictionary is a mutable and unordered data structure . It permits storing a pair of items (i.e. keys and values). As the example below demonstrates, in the dictionary , it’s possible to include containers inside other containers to create compound data structures.

More on Lists How to Append Lists in Python

Now I’ll introduce you to three user-defined data structures: ques, stack, and tree. (Please note, in what follows, I’m assuming you have a basic knowledge of classes and functions .)

Stack using arrays

The stack is a linear data structure where we arrange elements sequentially. It follows the principle last in, first out (LIFO). So, the last element inserted will be removed first. The operations are:

• Push → Inserting an element into the stack
• Pop → Deleting an element from the stack

The conditions to check:

• Overflow condition → This condition occurs when we try to put one more element into a stack that’s already at maximum capacity. 
• Underflow condition → This condition occurs when we try to delete an element from an empty stack.

Queue Using Arrays

The queue is a linear data structure where elements are sequential. It follows the FIFO principle (first in, first out). Think about when you go to the movies with your friends, as you can imagine the first of you that hands over your ticket is also the first one who steps out of line. The mechanism of the queue is the same.

The aspects that characterize a queue are:

• Front → Points to starting element
• Rear → Points to the last element

There are two operations:

• Enqueue → Inserting an element into the queue (at the end).
• Dequeue → Deleting an element from the queue (from the front).

There are two conditions: 

• Overflow → Insertion into a full queue
• Underflow → Deletion from an empty queue

And the output will look like this:

General Tree

Trees are used to define hierarchy. It starts with the root node and goes further down. The last nodes are called child nodes.

Here we’ll focus on the binary tree . The binary tree is a tree data structure in which each node has (at most) two children, which are referred to as the left child and the right child. Below you can see a representation and an example of the binary tree in Python where I constructed a class called node and the objects that represent the different nodes (A, B, C, D, and E).

More From Our Python Experts How to Improve Your Control Flow Coding in Python

The concept of the algorithm has existed since antiquity. In fact, the ancient Egyptians used algorithms to solve their problems and they taught this approach to the Greeks.

The word algorithm derives from the ninth-century Persian mathematician Muḥammad ibn Mūsā al-Khwārizmī , whose name was Latinized as Algorithmi. Al-Khwārizmī was also an astronomer, geographer, and a scholar in the House of Wisdom in Baghdad.

As you already know, algorithms are instructions formulated in a finite and sequential order to solve problems.

When we write an algorithm , we have to know what the exact problem is, determine where we need to start and stop, and formulate the intermediate steps.

There are three main approaches to solve algorithms:

• Divide et Impera (also known as divide and conquer) → It divides the problem into sub-parts and solves each one separately.
• Dynamic programming → It divides the problem into sub-parts, remembers the results of the sub-parts, and applies it to similar ones.
• Greedy algorithms → This involves taking the easiest step while solving a problem without worrying about the complexity of the future steps.

Tree Traversal Algorithm

Trees in Python are non-linear data structures. They are characterized by roots and nodes. I take the class I constructed before for the binary tree.

Tree Traversal refers to visiting each node present in the tree exactly once, in order to update or check them.

There are three types of tree traversals :

• In-order traversal
• Pre-order traversal
• Post-order traversal

In-Order Traversal

In-order traversal refers to visiting the left node, followed by the root and then the right nodes.

Here D is the leftmost node where the nearest root is B. The right of root B is E. Now the left sub-tree is completed, so I move towards the root node A and then to node C.

Pre-Order Traversal

Pre-order traversal refers to visiting the root node followed by the left nodes and then the right nodes.

In this case, I move to the root node A and then to the left child node B and to the sub child node D. After that I can go to the nodes E and then C.

Post-Order Traversal

Post-order traversal refers to visiting the left nodes followed by the right nodes and then the root node.

I go to the most left node which is D and then to the right node E. Then, I can go from the left node B to the right node C. Finally, I move towards the root node A.

Your output will look like:

Sorting Algorithm

We use the sorting algorithm to sort data in a given order. We can classify the data in merge sort and bubble sort.

The merge sort algorithm follows the divide et impera rule. The algorithm first divides into smaller lists, compares adjacent lists and then reorders them in the desired sequence. In other words, from unordered elements as input, we need to have ordered elements as output. Here’s merge sort in practice:  

The output looks like this:

Bubble Sort

This algorithm first compares and then sorts adjacent elements if they are not in the specified order. For example:

Insertion Sort

This algorithm picks one item in a given list and places it at the exact spot where you want it.

We use searching algorithms to seek for some elements present in a given data set. There are many types of search algorithms such as linear search, binary search , exponential search and interpolation search, among others. For now, we’ll focus on linear search and binary search.

Linear Search

In a single-dimensional array we have to search a particular key element. The input is the group of elements and the key element we want to find. So, we have to compare the key element with each element of the group. In the following code, I try to seek element 27 in our list.

Binary Search

In this algorithm, we assume the list is in ascending order. So, if the value of the search key is less than the element in the middle of the list, we narrow the interval to the lower half. Otherwise, we narrow to the upper half. We continue our check until we find the value or the list is empty.

Now that you have some sense of basic data structures and algorithms, you can start going deeper and using more complex algorithms in Python .​​​​​​​

Frequently Asked Questions

Can i use python for data structures and algorithms.

Python features built-in data structures, and data in Python can be analyzed with algorithms like traversal, searching and sorting algorithms. 

How long does it take to learn Python data structures and algorithms?

Learning Python data structures and algorithms typically takes anywhere from a few weeks to a few months, depending on one’s experience, dedication and the quality of their learning resources, among other factors.

Built In’s expert contributor network publishes thoughtful, solutions-oriented stories written by innovative tech professionals. It is the tech industry’s definitive destination for sharing compelling, first-person accounts of problem-solving on the road to innovation.

Great Companies Need Great People. That's Where We Come In.

Programming, Data Structures And Algorithms Using Python

Note: This exam date is subjected to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout, books and references, instructor bio.

Prof. Madhavan Mukund

Course certificate.

• Assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course. 
• ( All assignments in a particular week will be counted towards final scoring - quizzes and programming assignments). 
• Unproctored programming exam score = 25% of the average scores obtained as part of Unproctored programming exam - out of 100
• Proctored Exam score =50% of the proctored certification exam score out of 100

DOWNLOAD APP

Data Structures in Python

Learn, analyze, implement data structures using python with exercises.

Includes Certificate of Completion

Add this credential to your LinkedIn profile, resume, or CV. You can share it on social media and in your performance review.

What's in the course?

• 26 video lecture s
• 7 + hour s of content
• GPT-4 level AI assistance

Course Outcomes

• Understand the fundamentals of the Data Structures and Algorithms
• Understand concept behind Arrays, Linked Lists, Stacks & Queues, Hash tables, Trees and Graphs
• Improve your problem solving skills and become a confident developer for your next coding interview
• Code an implementation of each data structure, so you understand how they work behind the scene
• Understand each and every concept from scratch with proper knowledge of their complexities and implementations in Python

Course Structure

28 lecture s • 6h 35m total duration

Course Introduction

Essential Concepts

Linked List

Stack & Queue

Hash Tables

About This Course

Take the first step on your journey through Data Structures with this beginner-friendly course. You'll gain a comprehensive understanding of concepts, visualizations, and implementations, all at your own pace and in a simplified way.

This course starts with the fundamentals, enabling you to grasp the complexities and uses of each topic. We explore the essentials like memory and logarithms before moving onto key data structures such as arrays, linked lists, stacks, queues, hash tables, trees, heaps, tries, and graphs. Along the way, you'll observe how each structure is implemented in Python, giving you the knowledge to use these tools effectively in your own projects.

Throughout your learning experience, the emphasis is on understanding every concept through a logical and visual approach. Be prepared for plenty of examples and quizzes that bolster your understanding in a practical manner. The only prerequisite for this course is a basic knowledge of Python; everything else is covered from scratch, step-by-step.

Once you've finished the course, a wide range of opportunities will be open to you. Whether you're looking to land an internship, kickstart your freelance career, or just want to improve your problem-solving abilities, the comprehensive understanding you gain from this course will provide a solid foundation. And, if you're keen to dive deeper into the complex questions surrounding Data Structures, you'll be fully equipped to do so.

Used by learners at

Course Requirements

• Basics of Python

Student Feedback

Course Instructor

Shubham is a software developer with a passion for teaching. He has worked with many funded startups, self-projects and as a top-rated freelancer on marketplaces. Shubham has taught programming and d... View profile

More Courses By Shubham Sarda

Master JavaScript Fundamentals

React JS Masterclass

Learn Web Development Basics: HTML & CSS

Upgrade to a Pro account and unlock more courses for accelerated learning. Instant feedback, interactive learning and more.

• 100+ coding courses
• Certificate of completion
• Hands-on practice
• 24x7 doubt solving with AI
• 100+ projects to practice
• In-depth project feedback
• AWS cloud sandboxes

• Title Problem Solving with Algorithms and Data Structures Using Python
• Author(s) Brad Miller, David Ranum.
• Publisher: Franklin, Beedle & Associates (2011), eBook (Creative Commons Edition, 2013)
• License(s): CC BY-NC-SA 4.0
• Hardcover/Papeback 438 pages
• eBook HTML and PDF
• Language: English
• ISBN-10: 1590282574
• ISBN-13: 978-1590282571

Tis textbook is about computer science. It is also about Python. However, there is much more. The study of algorithms and data structures is central to understanding what computer science is all about. Learning computer science is not unlike learning any other type of difficult subject matter.

The only way to be successful is through deliberate and incremental exposure to the fundamental ideas. A beginning computer scientist needs practice so that there is a thorough understanding before continuing on to the more complex parts of the curriculum. In addition, a beginner needs to be given the opportunity to be successful and gain confidence.

This textbook is designed to serve as a text for a first course on data structures and algorithms, typically taught as the second course in the computer science curriculum. Even though the second course is considered more advanced than the first course, this book assumes you are beginners at this level.

You may still be struggling with some of the basic ideas and skills from a first computer science course and yet be ready to further explore the discipline and continue to practice problem solving. We cover abstract data types and data structures, writing algorithms, and solving problems. We look at a number of data structures and solve classic problems that arise.

The tools and techniques that you learn here will be applied over and over as you continue your study of computer science.

• Python Programming
• Algorithms and Data Structures
• Computational Complexity
• Problem Solving with Algorithms and Data Structures Using Python (Brad Miller, et al)
• The Mirror Site (1) - HTML
• The Mirror Site (2) - PDF
• The Mirror Site (3) - PDF
• The Mirror Site (4) - PDF (770 pages)

This textbook serves as a gentle introduction for undergraduates to theoretical concepts in data structures and algorithms in computer science while providing coverage of practical implementation (coding) issues.

This introduction to computer programming with Python begins with some of the basics of computing and programming before diving into the fundamental elements and building blocks of computer programs in Python language.

This book covers Analysis and Design of Algorithms, Scientific Computing, Monte Carlo Simulations, and Parallel Algorithms. It teaches the core knowledge required by any scientist interested in numerical algorithms and computational finance.

This book uses Python to introduce folks to programming and algorithmic thinking. It is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques.

It promotes object-oriented design using Python and illustrates the use of the latest object-oriented design patterns. Virtually all the data structures are discussed in the context of a single class hierarchy.

Learn how to use Python to write programs that do in minutes what would take you hours to do by hand - no prior programming experience required. You'll create Python programs that effortlessly perform useful and impressive feats of automation.

This hands-on guide takes you through the Python programming language a step at a time, beginning with basic programming concepts before moving on to functions, recursion, data structures, and object-oriented design. 2nd edition updated for Python 3.

It focuses on introducing programming techniques and developing good habits. To that end, our approach avoids some of the more esoteric features of Python and concentrates on the programming basics that transfer directly to other imperative programming.

This book deepens your knowledge of problem-solving techniques from the realm of computer science by challenging you with time-tested scenarios, exercises, and algorithms. As you work through examples in search, clustering, graphs, and more.

The algorithmic approach to solving problems in computer technology is an essential tool. This book presents a readable, entertaining, and energetic book that will motivate and challenge students to open their minds to the algorithmic nature of problem solving.

• IT Research Library
• Books by O'Reilly®
• Pro Certificates Studies
• Careers and Job Interviews
• Project Management
• Search Engines
• Developer Tools
• Bargin Computer Books
• Free IT Magazines
• About This Site

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Problem Solving with Algorithms and Data Structures using Python

RunestoneInteractive/pythonds

Folders and files, repository files navigation, problem solving with algorithms and data structures using python.

This book began as a paper book, first published by Franklin Beedle & Associates back in 2005. Written by Brad Miller and David Ranum. We are grateful for the vision of Jim Leisy who gave us permission to take our text and publish it online as an interactive textbook.

Getting Started

We have tried to make it as easy as possible for you to build and use this book.

• You can see and read this book online at interactivepython.org
• pip install -r requirements.txt -- Should install everything you need
• runestone build -- will build the html and put it in ./build/pythonds
• runestone serve -- will start a webserver and serve the pages locally from ./build/pythonds

Sponsor this project

• https://www.paypal.me/runestoneinteractive

Contributors 21

• Python 99.4%

Data Structures

Arrays - ds easy problem solving (basic) max score: 10 success rate: 93.18%, 2d array - ds easy problem solving (basic) max score: 15 success rate: 93.15%, dynamic array easy problem solving (basic) max score: 15 success rate: 86.86%, left rotation easy problem solving (basic) max score: 20 success rate: 91.31%, sparse arrays medium problem solving (basic) max score: 25 success rate: 97.28%, array manipulation hard problem solving (intermediate) max score: 60 success rate: 61.37%, print the elements of a linked list easy problem solving (basic) max score: 5 success rate: 97.16%, insert a node at the tail of a linked list easy problem solving (intermediate) max score: 5 success rate: 95.27%, insert a node at the head of a linked list easy problem solving (basic) max score: 5 success rate: 98.32%, insert a node at a specific position in a linked list easy problem solving (intermediate) max score: 5 success rate: 96.97%, cookie support is required to access hackerrank.

Seems like cookies are disabled on this browser, please enable them to open this website

• Engineering & Transportation
• Engineering

Download the free Kindle app and start reading Kindle books instantly on your smartphone, tablet, or computer - no Kindle device required .

Read instantly on your browser with Kindle for Web.

Using your mobile phone camera - scan the code below and download the Kindle app.

Image Unavailable

• To view this video download Flash Player

Problem Solving in Data Structures & Algorithms Using Python: Programming Interview Guide First Edition

There is a newer edition of this item:.

• ISBN-10 1541128257
• ISBN-13 978-1541128255
• Edition First Edition
• Publication date December 14, 2016
• Language English
• Dimensions 8.5 x 0.93 x 11 inches
• Print length 411 pages
• See all details

Product details

• Publisher ‏ : ‎ CreateSpace Independent Publishing Platform; First Edition (December 14, 2016)
• Language ‏ : ‎ English
• Paperback ‏ : ‎ 411 pages
• ISBN-10 ‏ : ‎ 1541128257
• ISBN-13 ‏ : ‎ 978-1541128255
• Item Weight ‏ : ‎ 2.58 pounds
• Dimensions ‏ : ‎ 8.5 x 0.93 x 11 inches
• #16,915 in Engineering (Books)
• #49,496 in Education (Books)
• #63,513 in Professional

Customer reviews

Customer Reviews, including Product Star Ratings help customers to learn more about the product and decide whether it is the right product for them.

To calculate the overall star rating and percentage breakdown by star, we don’t use a simple average. Instead, our system considers things like how recent a review is and if the reviewer bought the item on Amazon. It also analyzed reviews to verify trustworthiness.

• Sort reviews by Top reviews Most recent Top reviews

Top reviews from the United States

There was a problem filtering reviews right now. please try again later..

Top reviews from other countries

• Amazon Newsletter
• About Amazon
• Accessibility
• Sustainability
• Press Center
• Investor Relations
• Amazon Devices
• Amazon Science
• Sell on Amazon
• Sell apps on Amazon
• Supply to Amazon
• Protect & Build Your Brand
• Become an Affiliate
• Become a Delivery Driver
• Start a Package Delivery Business
• Advertise Your Products
• Self-Publish with Us
• Become an Amazon Hub Partner
• › See More Ways to Make Money
• Amazon Visa
• Amazon Store Card
• Amazon Secured Card
• Amazon Business Card
• Shop with Points
• Credit Card Marketplace
• Reload Your Balance
• Amazon Currency Converter
• Your Account
• Your Orders
• Shipping Rates & Policies
• Amazon Prime
• Returns & Replacements
• Manage Your Content and Devices
• Recalls and Product Safety Alerts
• Conditions of Use
• Privacy Notice
• Consumer Health Data Privacy Disclosure
• Your Ads Privacy Choices

• PyCon India 2024

Event-Driven Application using Python & Apache Kafka

hemi s.k (~hemi) |  06 May, 2024

Description:

The workshop provides participants with insights into building event-driven applications with Apache Kafka and Python. By the workshop's conclusion, attendees will have acquired knowledge of Kafka's problem-solving capabilities, learned to implement Kafka in their projects, integrated it with Python libraries, and utilized Kafka Connect for seamless event routing across systems. Covered topics include distributed systems, Kafka event handling, read-write operations, partitioning, scaling, and consumer group management. This workshop is designed for engineers and architects seeking to enhance their applications with real-time data integration functionalities. Teaching methodologies encompass code demonstrations, practical examples, and actionable guidance for incorporating Kafka effectively. Workshop Syllabus:

Introduction

• Overview of the Workshop

Event-Driven Applications

• Understanding Event-Driven Architecture
• Importance and Benefits of Event-Driven Design

Introduction to Kafka

• What is Apache Kafka?
• Key Concepts of Kafka
• Understanding Kafka's Distributed Nature

Kafka Events

• Exploring the Structure of Kafka Events
• Writing Events to Kafka
• Reading Events from Kafka

Pizza Demo!

• Interactive Demonstration: Ordering Pizza with Kafka

Managing Kafka Logs

• Log Size and Retention Policies
• Understanding Kafka Topic Partitions
• Selecting an Appropriate Partition Strategy
• Ensuring Data Ordering within Partitions

Scaling Kafka

• Strategies for Scaling Out Kafka
• Partition Management and Scaling Considerations

Partitions Demo!

• Hands-On Exercise: Working with Kafka Partitions

Coordinating Multiple Applications

• Introduction to Kafka Consumer Groups
• Consumer Group Strategies and Best Practices

Consumer Groups Demo!

• Practical Session: Implementing Consumer Groups in Kafka

Kafka Connect

• Overview of Kafka Connect for Data Integration
• Use Cases and Configuration Options

Additional Resources

• Recommended Reading Materials, Tools, and Online Resources for Further Learning

Prerequisites:

• Basic programming concepts
• Familiarity with Python programming
• Understanding of distributed systems concepts
• Interest in event-driven architecture
• Desire to learn Kafka

Speaker Info:

Hello, I'm Hemangi Karchalkar. Armed with six years of professional programming experience and an enduring love for coding, I presently serve as a Senior Software Developer at EPAM Systems. Beyond my coding prowess, I find fulfillment in sharing knowledge with others. My passion lies in aiding individuals in their journey to success in the realms of data science and artificial intelligence. I've been fortunate to present at esteemed gatherings such as PyCon Italia 2023, Pycon India 2023, Pyconf Hyderabad 2022, Pycon Italia 2024, and GIDS Bangalore 2023.

Speaker Links:

PyCon Italia 2023 PyCon Italia 2024 LinkedIn Profile