Introduction Selection sort is a simple in-place (i.e. no auxiliary memory) comparison based sorting algorithm. It is an inefficient algorithm with O(n2) running time as it uses two nested loops. Here is a summary of steps how the algorithm works: Given an unsorted list Start with the first element on the left side Scan all

Introduction Insertion sort is a simple in place (i.e no need for an auxiliary memory) sorting algorithm. It is an efficient algorithm for small data sets, specially for lists that are partially sorted. For more information about how sorting works, you may refer to the following article For more in depth information about insertion sort

This post is a rewrite of the following article but in Python Python code def IterativeBinarySearch(A, key, l, r): # As long as left index is less than right index while l A[m]: # Update the left index l = m + 1 # We found the key else: return m # Key was not

For definition and explanation please refer to the following post. This post is only implementation in Python. Python code # Function recieves the input array A def MCSS (A): # Auxiliary array B = # MCSS ending at position 0 is just the first element B.append(A[0]) # Populate B for i in range (1,

Some time ago, I applied for a software QA position and was given this assignment: Problem Given 2 input files with rows in the format: <account ID><billing ID><Sign-up Date in MM-DD-YYYY format> Write a python script to print: All accounts in the first file not in the second All accounts in the second file not

Introduction Today, I am going to dive into the awesome world of sorting. It reminds me with entry level computer science courses and algorithm design. The goal of this article is to summarize popular sorting algorithms and put it in one place so that it is easy to remember and refer to. My intention is

Introduction One of the - confusing - topics in Algorithm design is the concept of NP completeness. If you search the topic on the internet you will probably find tons of articles and lectures on the subject however in this short article I will summarize it so that it is easy to remember by the

Dynamic programming making change algorithm Today we are going to discuss a new problem that can be solved using Dynamic Programming technique. We will talk about the well known problem of making change using a minimum number of coins. If you take the US currency as an example where we have the denominations (1C, 5C,

Longest Increasing Sub Sequence Welcome to the 6th part of our discussion on Dynamic Programming. You can refer to the first article (introduction) here. In this article we are going to discuss the "Longest Increasing Sub Sequence" problem which can be solved efficiently using Dynamic Programming. Problem Definition Given a sequence of numbers [A1 ..

Longest Common Subsequence Welcome to the 4th article on Dynamic Programming. You can refer to the first article (introduction) here. I will be using the shortcut LCS to refer to longest common sub-sequence. Let us get started. Introduction One of the applications of "Longest Common Subsequence" problem is comparing DNA strings to see how similar