algorithms

What is Backtracking? For any given problem — be it a decision-making problem like whether to stop the vehicle at any instance — in autonomous driving, an optimization problem like choosing the best path from my home to the office, or an enumeration problem like generating all possible permutations and combinations of teams play-outs in […]

Problem statement: A binary array sorted in decreasing order is given. We need to count the number of 1’s in it. Examples: Input: arr[] = {1, 1, 0, 0, 0, 0, 0} Output: 2 Input: arr[] = {1, 1, 1, 1, 1, 1, 1} Output: 7 Input: arr[] = {0, 0, 0, 0, 0, 0, […]

Given problem: A list of n strings each of length n is sorted into lexicographic order using the merge sort algorithm. Solution: Comparing two strings require O(n) comparisons, hence each merge will take O(n2) time. So, the recurrence equation will be: T(n) = 2 T(n/2) + O(n2) The n in the equation represents no.of elements […]

Let us start with the heapsort algorithm: The build_maxheap() funnction has a standard implementation of O(n). The important part of the sorting is the for loop, which executes for n times. Inside that we have a swap method call and heapify method call. The heapify method is a standard walk through of complete binary tree. […]

Problem statment Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size). Solution There can be two ways you can solve the above problem. Option A: The stack – efficient when pushing an item Option B: The stack – efficient when popping an item In this post lets us discuss the an implementation […]

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It works best on a nearly sorted list. It has the following characteristics Stable; i.e., does not change the relative order of elements with equal keys In-place; i.e., only requires a constant amount O(1) of […]

Coin Exchange Problem: Coin exchange problem is nothing but finding the minimum number of coins (of certain denominations) that add up to a given amount of money. It is a knapsack type problem. The interesting fact is that it has 2 variations: 1. Greedy Algorithm: For some type of coin system (canonical coin systems — […]

What is a Data Structure? We will not be talking about data structures implementation in this post, but about their usage or choice during programming. As usual lets start from the basic definition. Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. They […]

We all know about the standard comparison based sorting algorithms and their time/space complexity. Algorithms like bubble sort, insertion sort, selection sort, quick sort, merge sort, Heap sort operate with a asymptotic lower bound of O(n log n). Also, other unconventional sorting algorithms like Bucket Sort, Counting Sort, Radix Sort run in O(n) We will not talk […]