Blog Posts tagged with 'algorithms'

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

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

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

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

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

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

Binary Search Example in Python

Binary search is a very efficient algorithm for finding an item in a sorted list. I wrote a Python program that uses binary search to find random numbers in a list of 10,000 and 100,000 items. Using asymptotic notation, binary search is O(log n), which means it has a really slow rate of growth as the number of items to search grows large.

Read More

Fibonacci Numbers - Tale of Two Algorithms using Python

A mind blowing experiment looking at two different algorithms in Python for calculating Fibonacci numbers. One is the well-known recursive function, and the other is an alternative algorithm using a list. I profiled these functions in Pycharm, and am amazed at the results!

Read More