311–320 of 507 posts
Floyd–Steinberg dithering of images: https://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dither... It can simulate color transitions with fewer colours by using a simple error diffusion algorithm.
I really like Floyd's algorithm for sampling n elements without duplicates in linear time. https://fermatslibrary.com/s/a-sample-of-brilliance
The (fairly simple) nimber algorithm for optimal nim play which can then be applied to other games e.g. dots and boxes
I learned this while hanging out in the library (Martin Gardner’s column in Scientific American). I put it to good use years later in college: I decided to implement a Nim playing circuit (out of RTL logic gates, yuk!) for my digital design lab course final project in 1975. It was a complex sequential circuit, but the result was quite remarkable. It played perfect Nim with up to four piles of 1 to 16 tokens.
I like your project idea. I'm not hard core enough to build something from transistors but I'd love to give nin a go in assembler on an arduino. Something to add to my backlog!
You've made a Fibonacci number algorithm. Recursive it's slow, iterative it's nasty. There's another way
> let fib = 0 : 1 : zipWith (+) fib (tail fib)
Then to get the 10kth Fibonacci number you can
> fib !! 10000
It's fast. It's tiny. It has no risk of stack overflow because it's not a recursive function. It illustrates how and why lazy evaluation is important and even better than eager evaluation in many cases. I use this principle in my C#/Java work a lot.
It's my favorite.
It finds strongly connected components in a graph (read: cyclic dependencies), while doing a topological sort (read: you could use it for a package manager to determine which packages to install first).
It is proof of a very deep understanding of the nature of graphs.
Edit: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_...
I like Dijkstra's algorithm for finding the shortest path between two nodes in a graph. It's not so much that it is "beautiful", but it is a remarkably simple algorithm that a human can follow manually. The reason it is efficient is easily understood (it's easy to see how we are able to "finalize" nodes because it's obvious there is no shorter path to that node), and it takes what would otherwise be a complicated tas…
I've always suspected that Dijkstra's shortest path algorithm was invented many times before he wrote it down. The algorithm itself is relatively straight forward and I can imagine that a competent programmer not aware of it could come up with it independently. I mean, even Dijkstra himself came up with it because he needed it for a telecom gig. He can't have been the first one in the world who needed to find the sho…
I'm by no means a Haskell evangelist, but I believe it's a great educational tool for devs. You've made a Fibonacci number algorithm. Recursive it's slow, iterative it's nasty. There's another way > let fib = 0 : 1 : zipWith (+) fib (tail fib) Then to get the 10kth Fibonacci number you can > fib !! 10000 It's fast. It's tiny. It has no risk of stack overflow because it's not a recursive function. It illustrates how a…
fibs = 0 : scanl (+) 1 fibs
Earlier quoted context omitted.
Is the definition of "algorithm" that you're using here useful?
It's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.
I always push my devs to really study the Bittorrent protocol. The elements of the protocol are all fairly easy to understand, but it's gorgeous to see how elegantly it solved a social problem rather than a computational problem. The tit-for-tat and fast-finish protocols are incredibly graceful ways to create virtuous cycles in a social/technical hybrid, and replaced very real vicious cycles in previous protocols. Va…
Any suggestions where I can read about the BitTorrent protocol?
It worked pretty well. Used it for several years until I started making real money and decided I could buy things rather than pirate them.
I had only been coding for a year or two at that point, so it is probably filled with lots of odd choices, but it also isn't super optimized like I would guess the more well known clients might be, and so might be easier to parse.