Defining Greedy Algorithm

An algorithm is called greedy if it follows the problem-solving heuristic of making the locally optimal choice at each stage with the aim of finding a global optimum.

In most situations, a greedy strategy does not lead to the optimal solution. Hence, it is extremely important to reason about the correctness of the greedy strategy before using it to solve a problem.

Problem 1: Too much to do!

Let's say you have to maximise the number of tasks that you complete in a 10-hour duration. You are given an array T = [2, 4, 1, 6] where T_i denotes the time required to complete the i^th task.

The answer to this question would be 3 as you would choose to do tasks T₂, T₀ and T₁ — which take 1, 2 and 4 hours respect...

Sequence Motifs and their Biological Significance

Sequence motifs are nucleic acid sequences that are widespread across or within a genomes and have or are speculated to have certain regulatory or structural biological functions.

Motifs that are found in different parts of the genomes like exons, introns and junk, have different functions. Motifs present in the exons ( coding part of the genome) decide the structure of the protein or label proteins to be sent to certain parts of the cell for processes like phosphorylation. Motifs that are present in introns (which makes up the non coding part of genome) are usually the regulatory sequences which determine the amount of gene expression and binding sites of proteins. Satellite DNA, which is the main component of centromeres and heterochromatin, is an example of motif found in junk parts of the genome.

Sequence Motifs and Consensus Se...

This is a very comprehensive 94-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc.

The primary objectives of this course are to learn about 30 different algorithms and data structures. The algorithm tutori...

While many ciphers have been created based upon the Feistel structure, the most famous of these is the Data Encryption Standard (DES). DES was based off of the original Lucifer cipher developed by Feistel and Coppersmith and submitted as an entry to the US National Bureau of Standards as a candidate for the US official encryption standard. After some modification (to improve security against differential cryptanalysis), it was selected and published as a standard in 1977.

Encryption with DES

The DES algorithm is a 16-round Feistel cipher. It takes as input a 64-bit input and a 64-bit secret key, and consists of three main stages:

• The initial permutation
• The round function (repeated 16 times)
• The final permutation

A diagram of how these stages fit together with the ...

Motivation: Given an array of N numbers, you need to support two operations. Operation 1: find-min(i, j) = return the minimum value in array[i ... j]. Operation 2: update(i, v) = update the value at array[i] to v. Solve the problem for N <= 10^6, number of operations <= 10^6.

To solve the above problem, both the operations need to run in O(log N) time, but using an naive array gives O(N) run-time for operation 1 (and O(1) run-time for operation 2). So how do you solve the problem? Read on. :)

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.