Here are some algorithms that I find elegant / beautiful:
- many recursive algorithms (I said why I think so, in another comment in this thread, agreeing with kamaal's comment about recursion - https://news.ycombinator.com/item?id=18236708 ), and recursive data structures too; to repeat: elegance and simplicity, although you have to think for a while to grok some of them - then it suddenly becomes clear how they work.
- Huffman encoding and decoding (mentioned by someone else here too; I had also commented about this on HN earlier (I think in an HN thread about old BYTE magazine issues being available on the Internet Archive). I had seen an elegant Huffman algorithm in an old BYTE issue; the author was Jonathan Amsterdam; IIRC, a tree was used to both build the codes and decode the encoded data;
- Depth First Search is cool; others in this thread said it too; "The Go Programming Language" book (code at gopl.io) has a nice example of it, which they use to implement a topological sort, to find a valid ordering of all (e.g. computer science) courses, given the prerequisite courses for each course. The code for it is pretty short and clear, which makes it more cool. Topological sorting has many uses. Scheduling (somewhat similar to the course ordering above) is one such use. Another interesting one is the tsort Unix command, which I used to use in C program compiler / linker commands in my early Unix C programming days. A typical usage (IIRC) is to pipe the lorder command to tsort as part of the compiling / linking process, and use the output in the surrounding compiler or linker command (using shell command substitution). I forget the exact details now (it probably involved a pipeline using the commands cc, ar, lorder and tsort), but it can be looked up.
Someone else mentioned XOR (exclusive OR). I once wrote two C programs for encrypting and decrypting files using this property of XOR, which I read about somewhere:
- if A XOR B gives C,
then C XOR B gives A,
for any bit patterns A, B and C.
Putting it in other words, if you XOR a byte A (from your input) with a bit pattern B (of byte length), then XORing the output (C) with the same bit pattern B, gives you A back as the output. So you can use it to encrypt and decrypt bytes, although the algorithm is easily decipherable, if you know about it. So caveat lector: it is not strong encryption, at all.
Demo of that in Python:
In [133]: for c in 'abcdefghij':
...: oc1 = ord(c)
...: oc2 = oc1 ^ 255
...: oc3 = oc2 ^ 255
...: print oc1, oc2, oc3
...:
97 158 97
98 157 98
99 156 99
100 155 100
101 154 101
102 153 102
103 152 103
104 151 104
105 150 105
106 149 106
You can see that the numbers in the 1st and 3rd columns above are the same. Another interesting observation is that the numbers in the middle column are incrementally decreasing.
So that rule can be used to encrypt the bytes of a file, by XORing each byte with some specific byte, and writing the XORed results to an output file. To decrypt the file, just XOR each byte from the output (now input) file with the same specific byte as earlier. I had written a C program to accept a string of characters and an input filename, on the command line,and to cyclically use the bytes in that string, to XOR with the bytes in the input file, while both encrypting and decrypting. It worked, but I was surprised to see (IIRC, it was done quite a while ago) that the same string was sometimes seen repeatedly occurring (as plaintext) in the encrypted file. Don't know the mathematical / cryptographical reason for it, if any.