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 ...

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...

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.

A sequence (array) is really just a function which associates integers (indices) with the corresponding values. However, there is no reason to restrict our usage of binary search to tangible sequences. In fact, we can use the same algorithm described above on any monotonic function f. ... The only difference is that we replace an array lookup with a function evaluation: we are now looking for some x such that f(x) is equal to the target value.

Source: TopCoder

Example

Problem: Given a perfect square S (such as 16129 = 127 * 127) between 1 and 10 ** 6, find its square root (assuming you don't know how to calculate the square root).

Solution: Since the square is between 1 and 10 ** 6,...