computer science

14 Articles

Taking A Crack At The Traveling Salesman Problem

October 21, 2020 by 16 Comments

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” →

Grab A Stanford Computer Science Education

October 14, 2020 by 18 Comments

There are two reasons to go to school: learn about something and to get a coveted piece of paper that helps you get jobs, or at least, job interviews. With so many schools putting material online, you can do the first part without spending much money as long as you don’t expect the school to help you or grant you that piece of paper. Stanford has a huge computer science department and [Rui Ma] cataloged over 150 computer science classes available online in some form from the University. Just the thing to while away time during the quarantine.

Apparently, [Rui] grabbed the 2020 course catalog to find on-campus classes and found the companion website for each class, organizing them for our benefit. The list doesn’t include the actual online class offerings, which you can find directly from Stanford, although there is another list for that.

Continue reading “Grab A Stanford Computer Science Education” →

A Turing-Complete CPU From RAM

February 20, 2020 by 16 Comments

Building a general-purpose computer means that you’ll have to take a lot of use cases into consideration, and while the end product might be useful for a lot of situations, it will inherently contain a lot of inefficiencies. On the other hand, if you want your computer to do one thing and do it very well, you can optimize to extremes and still get results. This computer, built from RAM, is just such an example.

The single task in this case was to build a computer that can compute the Fibonacci sequence.  Since it only does one thing, another part of the computer that can be simplified (besides the parts list) is the instruction set. In this case, the computer uses a single instruction: byte-byte-jump. Essentially all this computer does is copy one byte to another, and then perform an unconditional jump. Doing this single task properly is enough to build every other operation from, so this was chosen for simplicity even though the science behind why this works is a little less intuitive.

Of course, a single instruction set requires a lot of clock cycles to work (around 200 for a single operation). The hardware used in this build is also interesting and although it uses a Raspberry Pi to handle some of the minutiae, it’s still mostly done entirely in RAM chips, only cost around $15, and is a fascinating illustration of some of the more interesting fundamentals of computer science. If you’re interested, you can build similar computers out of 74-series chips as well.

Tony Brooker And Autocode – The First High-level Language

January 2, 2020 by 30 Comments

The field of computer science has undeniably changed the world for virtually every single person by now. Certainly for you as Hackaday reader, but also for everyone around you, whether they’re working in the field themselves, or are simply enjoying the fruits of convenience it bears. What was once a highly specialized niche field for a few chosen people has since grown into a discipline that not only created one of the biggest industry in modern times, but also revolutionized every other industry, some a few times over.

The fascinating part about all this is the relatively short time span it took to get here, and with that the privilege to live in an era where some of the pioneers and innovators, the proverbial giants whose shoulders every one of us is standing on, are still among us. Sadly, one of them, [Tony Brooker], a pioneer of the early programming language concept known as Autocode, passed away in November. Reaching the remarkable age of 94, the truly sad part however is that this might be the first time you hear his name, and there’s a fair chance you never heard of Autocode either.

But Autocode was probably the first high-level computer language, and as such played a fundamental role in the development of whatever you’re coding in today. So to honor the memory of [Tony Brooker], let’s remember the work he did with Autocode, and the leap in computer science history that it represented.

Continue reading “Tony Brooker And Autocode – The First High-level Language” →

A Nurse Call System Becomes Turing Complete

March 9, 2019 by 3 Comments

George Mallory, a famous English mountaineer, once suggested that it was of no use to climb mountains. Instead, he posited, the only reason to climb a mountain is because it is there. Likewise, when you become an expert in nurse call systems like those found in hospitals, you may find that you do things with them that are of similar use. Making a Turing-complete nurse call system is something you do because you can.

[Erik] has been working on this particular call system, known as Netrix, and used Wireshark to sniff out all of its protocols. With this information he realized that it would be possible to use the system’s routing features to perform all of the tasks that any Turing complete system can do: conditional branching and memory access. He set up a virtual machine and set about implementing all of these tasks using the nurse call system’s features.

The setup for this project is impressive, and belies an extensive knowledge of this one proprietary system but also of computer science in general. It’s interesting to see how something can be formed into a working computer system from parts that otherwise might not be used that way. Even things that aren’t electronic can be used as Turing-complete computers.

Photo via Wikimedia Commons

A Compiler In Plain Text Also Plays Music

January 17, 2019 by 18 Comments

As a layperson reading about some branches of mathematics, it often seems like mathematicians are just people who really like to create and solve puzzles. And, knowing that computer science shares a lot of its fundamentals with mathematics, we can assume that most computer scientists are also puzzle-solvers as well. This latest project from [tom7] shows off his puzzle creating and solving skills with a readable file which is also a paper, which is also a compiler for C programs, which can also play music.

[tom7] started off with the instruction set for the Intel 8086 processor. Of the instructions available, he wanted to use only instructions which are also readable in a text file. This limits him dramatically in what this file will be able to execute, but also sets up the puzzle. He walks through each of the hurdles he found by only using instructions that also code to text, including limited memory space, no obvious way of exiting the program once it was complete, not being able to jump backward in the program (i.e. looping), and a flurry of other issues that come up once the instruction set is limited in this way.

The result is a sort of C compiler which might not be the most efficient way of executing programs, but it sure is the most effective way of showing off [tom7]’s PhD in computer science. As a bonus, the file can also play an antiquated type of sound file due to one of the available instructions being a call for the processor to interact with I/O. If you want to learn a little bit more about compilers, you can check out a primer we have for investigating some of their features.

Thanks to [Greg] for the tip!

Continue reading “A Compiler In Plain Text Also Plays Music” →

Software: It Is All In The Details

January 6, 2019 by 22 Comments

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” →