Our Favorite Things: Binary Search

You might not think that it would be possible to have a favorite optimization algorithm, but I do. And if you’re well-versed in the mathematical art of hill climbing, you might be surprised that my choice doesn’t even involve taking any derivatives. That’s not to say that I don’t love Newton’s method, because I do, but it’s just not as widely applicable as the good old binary search. And this is definitely a tool you should have in your toolbox, too.

Those of you out there who slept through calculus class probably already have drooping eyelids, so I’ll give you a real-world binary search example. Suppose you’re cropping an image for publication on Hackaday. To find the best width for the particular image, you start off with a crop that’s too thin and one that’s too wide. Start with an initial guess that’s halfway between the edges. If this first guess is too wide, you split the difference again between the current guess and the thinnest width. Updated to this new guess, you split the differences again.

But let’s make this even more concrete: an image that’s 1200 pixels wide. It can’t get wider than 1200 or thinner than 0. So our first guess is 600. That’s too thin, so we guess 900 — halfway between 600 and the upper limit of 1200. That ends up too wide, so we next guess 750, halfway between 600 and 900. A couple more iterations get us to 675, then 638, and then finally 619. In this case, we got down to the pixel level pretty darn fast, and we’re done. In general, you can stop when you’re happy, or have reached any precision goal.

[Ed note: I messed up the math when writing this, which is silly. But also brought out the point that I usually round the 50% mark when doing the math in my head, and as long as you’re close, it’s good enough.]

What’s fantastic about binary search is how little it demands of you. Unlike fancier optimization methods, you don’t need any derivatives. Heck, you don’t even really need to evaluate the function any more precisely than “too little, too much”, and that’s really helpful for the kind of Goldilocks-y photograph cropping example above, but it’s also extremely useful in the digital world as well. Comparators make exactly these kinds of decisions in the analog voltage world, and you’ve probably noticed the word “binary” in binary search. But binary search isn’t just useful inside silicon. Continue reading “Our Favorite Things: Binary Search”

Hacking Multiplication With Karatsuba’s Algorithm

People tend to obsess over making computer software faster. You can, of course, just crank up the clock speed and add more processors, but often the most powerful way to make something faster is to find a better way to do it. Sometimes those methods are very different from how a human being would do the same task, but it suits the computer’s capabilities. [Nemean] has a video explaining a better multiplication algorithm known as Karatsuba’s algorithm and it is actually quite clever. You can see the video below.

To help you understand the algorithm, the video shows a simple two-digit by two-digit multiplication. You can see that the first and last digits are essentially the result of one multiplication. It is all the intermediate digits that add together. The only thing that might change the first digit is a carry.

Continue reading “Hacking Multiplication With Karatsuba’s Algorithm”

Taking A Crack At The Traveling Salesman Problem

The human mind is a path-planning wizard. Think back to pre-lockdown days when we all ran multiple errands back to back across town. There was always a mental dance in the back of your head to make sense of how you planned the day. It might go something like “first to the bank, then to drop off the dry-cleaning. Since the post office is on the way to the grocery store, I’ll pop by and send that box that’s been sitting in the trunk for a week.”

This sort of mental gymnastics doesn’t come naturally to machines — it’s actually a famous problem in computer science known as the traveling salesman problem. While it is classified in the industry as an NP-hard problem in combinatorial optimization, a more succinct and understandable definition would be: given a list of destinations, what’s the best round-trip route that visits every location?

This summer brought news that the 44-year old record for solving the problem has been broken. Let’s take a look at why this is a hard problem, and how the research team from the University of Washington took a different approach to achieve the speed up.

Continue reading “Taking A Crack At The Traveling Salesman Problem”

An Algorithm For De-Biasing AI Systems

A fundamental truth about AI systems is that training the system with biased data creates biased results. This can be especially dangerous when the systems are being used to predict crime or select sentences for criminals, since they can hinge on unrelated traits such as race or gender to make determinations.

A group of researchers from the Massachusetts Institute of Technology (MIT) CSAIL is working on a solution to “de-bias” data by resampling it to be more balanced. The paper published by PhD students [Alexander Amini] and [Ava Soleimany] describes an algorithm that can learn a specific task – such as facial recognition – as well as the structure of the training data, which allows it to identify and minimize any hidden biases.

Testing showed that the algorithm minimized “categorical bias” by over 60% compared against other widely cited facial detection models, all while maintaining the same precision of detection. This figure was maintained when the team evaluated a facial-image dataset from the Algorithmic Justice League, a spin-off group from the MIT Media Lab.

The team says that their algorithm would be particularly relevant for large datasets that can’t easily be vetted by a human, and can potentially rectify algorithms used in security, law enforcement, and other domains beyond facial detection.

Software: It Is All In The Details

Who’s the better programmer? The guy that knows 10 different languages, or someone who knows just one? It depends. Programming is akin to math, or perhaps it is that we treat some topics differently than others which leads to misconceptions about what makes a good programmer, mathematician, or engineer. We submit that to be a great programmer is less about the languages you know and more about the algorithms and data structures you understand. If you know how to solve the problem, mapping it to a particular computer language should be almost an afterthought. While there are many places that you can learn those things, there is a lot more focus on how to write the languages,  C++ or Java or Python or whatever. We were excited, then, to see [Jeff Erickson] is publishing his algorithms book distilled from teaching at the University of Illinois, Urbana-Champaign for a number of years. The best part? You can read the preprint version online now and it will remain online even after the book goes to print.

When you were in school, you probably learned math in two ways: there was the mechanics (4×4=16) and then there were the word problems (Johnny has 10 candy bars and eats 4, how many are left?). Word problems are usually the bane of the student’s existence, yet they are much more realistic. Your boss has (probably) never come in your office and asked you what 147 divided by 12 is. If she did, you could hand her a calculator. The real value comes in being able to synthesize the right math for the right problem and — if you are lucky — gaining intuition about it (doubling the price will only increase profit by 10%). Software is pretty much the same, for example no one rushes into your cubicle and says “Quick! We need a for loop written!” You get a hazy set of requirements if you are lucky, and you then need to map that into something that computers can do. For that reason, we’ve always been more of a fan of learning about algorithms and data structures rather than specific language features.

Continue reading “Software: It Is All In The Details”

Algorithms For Visual Learners

Computer programming is a lot like chess. It is fairly simple to teach people the moves. But knowing how the pieces move isn’t the reason you can win. You have to understand how the pieces work together. It is easy to learn the mechanics of a for loop or a Java interface. But what makes programs work are algorithms. There are many books and classes dedicated to algorithms, but if you are a visual learner, you might be interested in a site that shows visualizations of algorithms called VisuAlgo.

The site is from [Dr. Steven Halim] and is meant for students at the National University of Singapore, but it is available “free of charge for Computer Science community on earth.” We suspect if any astronauts or cosmonauts wanted to use it in space, they’d be OK with that, too.

The animations and commentary take you through algorithms ranging from the common — sorting and linked lists — to the obscure — Steiner and Fenwick trees. Each animation frame has some commentary, so it isn’t just pretty pictures. The site is available in many languages, too.

Many of the animations allow you to set up problems and execute them using a C-like pseudo language. When it executes, you can watch the execution pointer and a box comments on the current operation. For example, in the linked list unit, you can create a random doubly linked list and then search it for a particular value. Not only can you see the code, but the graphical representation of the list will update as the code runs.

The site allows you to register for free to get additional features, but we didn’t and it was still a great read about many different data structures. Also, a few of the commentary slides require you to show you are actually a computer science professor — we assume there’s some copyright issue involved because it is only a few.

This site is a great example of how many free educational resources are out there on the web. It isn’t just computer science either. MITx — or more generally, edX — has some great hardware classes and many other topics