Learn Algorithms with Python

In this post, I will show you some Python modules and resources which can help you learn "Data Structures and Algorithms" with Python as a beginner.

Posted by Karan on February 07, 2018   23541 views

In this post, we will explore how to get started with data structures and algorithms. So if you are a novice programmer or one who has no computer science background then you are reading something worth your time. So let's begin with few questions

What is an Algorithm?

An algorithm is a set of steps or a procedure to solve a problem, especially by computers. For example, the algorithm to buy something from a grocery store will have following steps:

  1. Go to the grocery store
  2. Find the product
  3. Add to cart
  4. Make payment

Similarly, for accomplishing tasks in computers a procedure is followed to get it done. Let's talk about some famous algorithms

  • Optimization Algorithms - Google Maps Direction show optimal distance using graph algorithms (like Dijkstra's Algorithm)
  • Data Compression - compressed zip files 
  • Face Detection - computer vision algorithms (like Viola-Jones algorithm )
  • RSA Algorithm - secure communication with cryptography
  • Random number generator 
  • Pattern Searching
  • Merge sort, Quicksort, Heapsort etc.
  • Scheduling algorithms to manage tasks in computers

Design and analysis of an algorithm is a fundamental topic in computer science and it is important to check the efficiency and correctness of algorithms. To compare algorithms you may check how much time it takes to give output on a particular machine, with particular hardware specification, with a particular language, but this is not a generic way to measure efficiency, therefore the Asymptotic Notations are used to compare algorithms independent of the hardware and the language.

 

Why Python for Algorithms?

Traditional programming languages like C, C++ etc. force students to deal with details of data structures and supporting routines, rather than algorithm design. Python represents and algorithm-oriented language that has been sorely needed in education. The way Python handles data types represents a perfect match with the way textbook present algorithms.

If it sounds "Not Easy" then don't worry, we will learn it in fun way. There is a bunch of topics like searching, sorting, operations on graphs, linked lists, trees etc., Consider these topics as grapes, then "how do you eat all the grapes from a bunch of grapes?", and the answer is "one by one", I will provide you a couple of resources where you can start practicing algorithms step by step.

While learning algorithms you might read "Pseudocode" frequently in books or tutorials, the pseudocode is way of writing algorithms which is not specific to a programming language, for example, you can write pseudocode to check if a number is even or odd as

a <- input a number
if a is divisible by 2
    print a is an even number
else
    print a is an odd number

One can implement the following algorithm in any language by following above pseudocode. If you want to master algorithms then read "Introduction to Algorithms" (by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein), in this book algorithms are represented by pseudocodes which can be implemented by any programming language.

Strategy to learn an Algorithm

You can follow these steps 

  1. Write pseudocode 
  2. Implement it with any programming language following pseudocode
  3. Test correctness by checking output with different inputs
  4. Analyse complexity

If you are just starting out then this book is a great place to start

http://interactivepython.org/runestone/static/pythonds/index.html

Helpful Python Modules

Pygorithms

Pygorithm is a python module which can help you learn algorithms in fun way. You can get the code, time complexities and much more by just importing the required algorithm. It covers implementation of all major algorithms in Python.

To install it with pip:

pip3 install pygorithm

Now open python shell in the terminal and try the following code

>>> from pygorithm import sorting
>>> arr = [107, 97, 114, 97, 110] # list be sorted
>>> sorting.bubble_sort.sort(arr)
[97, 97, 107, 110, 114]           # sorted list

>>> help(sorting)
Help on package pygorithm.sorting in pygorithm:

NAME
    pygorithm.sorting - Collection of sorting methods

PACKAGE CONTENTS
    bubble_sort
    bucket_sort
    counting_sort
    heap_sort
    insertion_sort
    merge_sort
    quick_sort
    selection_sort
    shell_sort

DATA
    __all__ = ['bubble_sort', 'bucket_sort', 'counting_sort', 'heap_sort',...

FILE
    /usr/lib/python3.6/site-packages/pygorithm/sorting/__init__.py

(END)


>>> code = sorting.bubble_sort.get_code()
>>> print(code)
def sort(_list):
    """
    Bubble Sorting algorithm

    :param _list: list of values to sort
    :return: sorted values
    """
    for i in range(len(_list)):
        for j in range(len(_list) - 1, i, -1):
            if _list[j] < _list[j - 1]:
                _list[j], _list[j - 1] = _list[j - 1], _list[j]
    return _list


>>> print ( sorting.bubble_sort.time_complexities() )
Best Case: O(n), Average Case: O(n ^ 2), Worst Case: O(n ^ 2).

For Improved Bubble Sort:
Best Case: O(n); Average Case: O(n * (n - 1) / 4); Worst Case: O(n ^ 2)

Github link: https://github.com/OmkarPathak/pygorithm

Other resources

 


blog comments powered by Disqus