Blog Posts tagged with 'python'

Depth-First Search in Python - Recursive and Non-Recursive Programming

Earlier I showed how to do depth-first search in C# and breadth-first search in C#. In this article I want to show depth-first search in Python, using both a recursive and non-recursive solution, because I want to show an example of topological sorting of a directed acyclic graph and the algorithm is based on depth-first search. I am also actively learning Python and it is best that I write Python code daily as much as possible.

Read More

Decorators in Python to Improve Naive Recursive Function for Fibonacci

I built my first decorator in Python to provide caching on Python functions that can support memoization, like the well-known recursive Fibonacci algorithm. Turns out a decorator, called lru_cache, already exists in functools that does memoization. This article shows how to create a custom Python decorator for caching as well as use the lru_cache decorator in functools to speed up the recursive Fibonacci algorithm.

Read More

Verify Binary Search Tree is Valid in Python

This weekend I completed the data structures portion of the Cracking the Coding Interview Questions on HackerRank. One of the programming challenges, validating a binary search tree, taught me how to verify a binary search tree is valid and I wanted to share my solution using Python.

Read More

Binary Heap and heapq in Python

I have been learning about Binary Heaps in my data structures class, and have been coding several examples in both Python and C#. In this article I want to introduce heapq in the Python collections module, which provide min Binary Heap functionality. I also provide an example of how to write a custom min Binary Heap in Python to perform Heapsort!

Read More

Queue Data Structure in Python and C#

Implementing a Queue Data Structure in Python and C#. In Python, I will describe how to use deque in the collections module as well as how to develop your own custom Queue using a Link List. In C#, I describe how to implement a Queue using an Array as well as using the Queue and Queue<T> Classes in System.Collections and System.Collections.Generic. I will also discuss abstraction in computer science to help hide the implementation details.

Read More

Local Functions and Memoization in Python to Solve for Fibonacci Numbers

Using memoization in the naieve, recursive algorithm for solving Fibonacci numbers makes a huge performance impact by reducing the number of recursive calls to re-solve Fibonacci numbers already calculated. In this case I will be using a Python dictionary and local functions ( nested functions ) to improve the recursive, naieve algorithm.

Read More

Stack Data Structure in Python and C#

This article first shows how to use the List Type in Python as a Stack data structure. It then provides an example of a custom Stack Class built in Python that still leverages the List Type in Python but uses abstraction to hide the underlying storage and its non-Stack methods. The article also shows how to use the deque in Python, Stack<T> in C# from System.Collections.Generic, and how to code the Stack data structure using a link list!

Read More

Inorder Traversal of Binary Search Tree in Python

In a recent programming challenge I was asked to code an inorder traversal of a binary search tree to print the values of its keys in the correct order. An order traversal of a binary search tree will print the keys of the node's left sub-tree, followed by the node's key, followed by the keys of the node's right sub-tree. I also show how to create a binary search tree in Python using level order traversal (like breadth-first search) and a list of ordered keys.

Read More

Bubble Sort in Python and HackerRank 30 Days of Code

Day 20 of HackerRank's 30 Days of Code was to write Bubble sort. I enjoy coding sorting algorithms (merge sort, insertion sort, selection sort, quicksort), so I was excited for the opportunity to write Bubble sort in Python, which I have done for fun in the past.

Read More

Quickselect Algorithm in Python

The Quickselect Algorithm is a selection algorithm based on the Quicksort sorting algorithm that provides a best case runtime of O(n) when finding the k-th smallest item in an unordered list. Quickselect achieves a better best case runtime compared to Quicksort, because it only has to recursively partition one side of the current partition. Here is an example of the Quickselect Algorithm using Python.

Read More

Quicksort Algorithm in Python

Today, in one of my algorithms design and analysis classes I learned about Quicksort. Much like Merge Sort, Quicksort is a divide and conquer sorting algorithm that sorts the items in O(nlogn). In this article I will be writing a Quicksort function in Python.

Read More

Python Fibonacci Number Generator

I mentioned learning about generating Fibonacci numbers using Python in my computer science and algorithm courses using recursive functions and Dynamic Programming. I wrote an article about the differences: Fibonacci Numbers - Tale of Two Algorithms using Python. In this article I show a Fibonacci Number Generator using Python generators. I also talk more about Python generators as well as mention the differences between range and xrange in Python 2.7.

Read More

Algorithm to Make Change in Python - Dynamic Programming

Making change is another classic example of Dynamic Programming I learned in my algorithms classes. In this example, I use Python to make change for a certain dollar amount given a list of dollars in U.S. currency. The goal is to make change using the least number of bills. Dynamic Programming is a great solution for this, since the problem involves overlapping sub-problems.

Read More

Dynamic Programming in Python for Clash of Clans

Using Dynamic Programming in Python to solve the Knapsack Problem in Clash of Clans. The goal is to find the best troop composition to hide the maximum amount of elixir and dark elixir in my barracks!

Read More

Entity Framework Core Example Using SQLAlchemy

Taking the example code I wrote with Entity Framework Core and C# and performing the same O/R Mapping and SQL Commands using SQLAlchemy and Python to perform CRUD operation on a SQLite Database.

Read More

Insertion Sort Using Python

A solution to insertion sort using Python that I wrote with Pythonista on my iPad Pro. I have also included several Doctests to verify it is sorting a list of integers correctly using insertion sort. If you are attending computer science and algorithms courses like myself, I hope you find the code useful!

Read More

Caesar Cipher in Python - Classical Cryptography

My computer science assignment was to develop a class in Python that encrypts and decrypts messages using the Caesar Cipher. I chose this solution, because it was the most creative by using Python string constants, the zip function to create a tuple from 2 iterable lists, dictionaries for constant lookup, and list comprehensions for doing the actual encryption and decryption.

Read More

Python Training - Selection Sort with Sample Unit Tests

I am learning Python and taking several online courses on computer science and algorithms. One of my assigments is to write Selection Sort in Python. I wrote this sample code on my iPad Pro using Pythonista and included unit tests.

Read More

ASP.NET Core Web API on macOS Using Visual Studio Code

In this article I create an ASP.NET Core Web API Application and Python web client on macOS that allows me to list, add, and remove daily reminders. I also show how to register services with the ASP.NET Core Dependency Injection Framework. I use Visual Studio Code to build the Web API Application and PyCharm to build the Python web client.

Read More

Merge Sort in Python Using Pythonista 3 on iPad Pro

I am learning divide and conquer algorithms and wrote Merge Sort in Python using Pythonista 3 on my iPad Pro. I included Doctests this time and plan to do so in the future. The Doctests provided a sanity check when I changed my algorithm based on an optimization I found elsewhere.

Read More