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:
- Go to the grocery store
- Find the product
- Add to cart
- 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
- Write pseudocode
- Implement it with any programming language following pseudocode
- Test correctness by checking output with different inputs
- Analyse complexity
If you are just starting out then this book is a great place to start
Helpful Python Modules
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
- http://codingbat.com/python (if you are an absolute beginner)
blog comments powered by Disqus