Integer Division This is the 5th part in a series of short articles on loop invariants. You can refer to the first part (introduction) here. Our example for today is a little bit harder than the previous examples. We are going to develop an algorithm to do integer division. Let us see how can we
Factorial Hello everyone! This is the 4th part in a series of short articles on loop invariants. You can refer to the first part (introduction) here. We are going to continue talking about loop invariants. Let us see how to find an appropriate loop invariant to calculate the factorial of a positive integer. Problem definition
Power Function Hello! This is the third part in a series of short articles on loop invariants. You can refer to the first part (introduction) here. In this article we will develop an algorithm to calculate the nth power of a positive integer. Problem definition Given two positive integers (x) and (n), develop an algorithm
Array sum Hello! This is the second part in a series of short articles on loop invariants. You can refer to the first part (introduction) here. In this article we will develop an algorithm to calculate the sum of all elements in an array. It is very easy to solve this problem using intuition but
Introduction Today, I am going to talk about a confusing concept in algorithm design. I think you have already guessed from the title of this article. Yes, let us talk about the puzzling topic of Loop Invariants. I personally believe it is a mathematical concept more than it is a computer science concept simply because
Integer Knapsack Problem Welcome! This is part 10 in a series of articles on Dynamic Programming. You can refer to the first part (introduction) by clicking here. Today we are going to discuss the “Integer Knapsack Problem”. Please recall that our problem today is a little bit different from the “01 Knapsack Problem” in which
Moving on a Checkerboard Welcome to a new article on Dynamic Programming. Today we will discuss “Moving on a Checkerboard” problem. This is part 9 of a series of articles on the topic. You can refer to the first article here. Let us get started. Problem Definition We are given a grid of squares or
Edit Distance or Levenshtein Distance Welcome! This is part eight in a series of articles on Dynamic Programming. You can start at the beginning of this series if you wish by clicking here. Today we are going to talk about “Edit Distance” or “Levenshtein distance” problem which has many applications such as spell checking. Let
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 ..
