Rudy Andrut has auralized a bunch of sorting algorithms based on their visualizations. They sound pretty amazing! Also, if you are looking for the visualizations that were previously done check them out here: sorting algorithm visualizations (sortvis.org).

Here are the videos:

Honestly, you don’t necessarily need to learn much complex mathematics. However, if you have an interest in theoretical computer science, machine learning, artificial intelligence, or other more advanced areas it may be useful to take some time learning as much as you can.

Discrete Mathematics
Discrete Math is the study of mathematical structures that are discrete (not continuous). It deals with countable sets of objects. Theoretical Computer Science deals heavily with graphy theory and logic when involved with discrete mathamatics. There are many additional areas of theoretical Computer Science that involve discrete mathematics, such as computability, automata theory, and formal language.

Linear Algebra
Linear Algebra helps to solve systems of linear equations with multiple unknown variables. It can be useful in a variety of areas in Computer Science, such as: data compression or cryptography. It can also help to understand the properties of the Fourier Transform which can apply to things such as signal processing. As an example, the fast Fourier Transform helps to multiple really large numbers quickly.

Probability & Statistics
Statistics and Probability can be useful in nearly all areas of Computer Science. You can use statistics for doing all kinds of data analysis. Some real world applications might include: Artificial Intelligence, machine learning, and advanced data analysis techniques. Statistics can help you study the behavior of numbers in certain distributions across a given sample. Two good examples would be: handling large set of data (SQL databases) or applications involving statistics in their calculations (financial data).

Calculus
Calculus can be particularly useful in Computer Science for many things. You may need to implement specific algorithms which utilize limits or functions where you need an approximate answer. Calculus can help you approximate these things. Lambda Calclulus in particular helps to provide a foundation for computation with functions. Basically, Lambda Calculus is a system for function definition, application, and recursion.

Others
By studying these 4 areas of mathematics you may begin to understand some of the fundamentals of more advanced areas, such as: machine learning, artificial intelligence, computer graphics, signal processing, compiler design, algorithms, etc. Most universities give you a descent set of mathemetics courses and you should at least be able to dabble enough in each area to build some foundational skills for some more advanced areas of study.

Someone (Mike Davey) has built an actual, WORKING, Turing Machine. It is complete with a control, a write head, erase head, read head, and even a mechanism for storage using 35mm leader tape (stores about 10 kilobits). His website, aturingmachine.com, has a video where you can watch it working!

Additional Resources
Turing Machine (Wikipedia)
Alan Turing (Wikipedia)

Mike Davey’s Turing Machine
A Turing Machine – Overview (aturingmachine.com)
Video of “A Turing Machine” (youtube.com)

A new, extremely fast sorting algorithm has been created for GPUs (CUDA-capable only) by researchers at the University of Virginia. This new algorithm is capable of sorting at a rate of one billion (integer) keys per second using a GPU. Normally CPUs aren’t as efficient as CPUs for these types of algorithms (for sorting), but these researchers claim to have created one much faster than any other known CPU-based sorting method.

This algorithm is for sorting large sequences of fixed-length keys/values. The current implementation can sort any of the C/C++ built-in numeric types or any structured payload types. Head over to the project’s website using the link below or download the code directly and try it for yourself.

RadixSorting – back40computing (Google Code)

There has been a LOT of debate as of late regarding Vinay Deolalikar’s P != NP research paper. I’m not going to lie, I don’t understand very many of the concepts described in his P!= NP paper (released August 6, 2010). I’m still learning many of the theoretical Computer Science concepts, but I found many of the debates brought up by this paper very interesting. One of the interesting debates involves cryptography.

Cryptography is the practice and study of hiding information via combinations of mathematics, computer science, and engineering. It is often used to prevent unwanted third parties from viewing certain data. The debate regarding this paper and Cryptography that has arisen basically says that if P=NP then all current cryptographic implementations would become theoretically much more vulnerable. Cryptography relies on certain problems being difficult. A good and efficient solution to certain NP complete problems could break many existing cryptographic systems, for example the NP complete problem 3-SAT and public-key cryptography. These cryptographic systems would need to be updated or replaced with something stronger.

Although Cryptography could face many problems, if P=NP there could be many benefits for other problems in mathematics. Efficient solutions to other difficult problems would have huge implications for problems such as protein structure prediction or various logistics problems. Proving some mathematical theorms can take decades of research. A method that is proven to find proofs to these theorms would put an end to this problem.

Additional Resources

• Cryptography (Wikipedia)
• P != NP – Research Paper (Vinay Deolalikar of HP Research Labs)
• Vinay Deolalikar (HP Labs)
• P versus NP problem (Wikipedia)

There are only a small handful number of operating systems dominant in today’s computing world. Systems software has been stagnant for nearly the past two decades. A good example mentioned in the source article mentions the excitement behind the Linux operating system. It’s true that there is much excitement and commitment for Linux, but did you know that Linux is essentially an open source clone of a 40 year old operating system (Unix)? This is just one example mentioned in the article, which in addition to pointing out the stagnation of systems software, it helps to paint a picture of the today’s systems research and also tries to uncover what happened.

Check out the full article: Systems Software Research is Irrelevant (freshmeat.net)

Originally algorithms were designed to process a single item at a time in sequential order. However, modern computer hardware is able to process multiple pieces of data at the same time in parallel. This leads to Parallel and Distributed Computing algorithms for solving more complex problems efficiently. I came across an interesting webpage which gives an Introduction to Parallel & Distributed Algorithms.

Here is a quick run down of a few interesting things that the article covers.

• Parallel Computing – When many calculations are performed simultaneously.
• Distributed Computing – When multiple autonomous computers communicated via a network and interact to achieve common goals.
• Algorithms for solving computational problems via parallel and distributed methods.
• Other related topics: sorting, difficulty of parallelization, etc.

Additional Resources

• Parallel Computing (wikipedia.org)
• Distributed Computing (wikipedia.org)

Read the full article: Introduction to Parallel & Distributed Algorithms (toves.org)

Online games can create a ton of complex data. But it can be a gold mine for design ideas, at least according to the article over at newscientist.com. In this article they talk about data mining online gaming data, with hopes of reaping the rewards of new ideas based on user behavior. The researchers are even using computer controlled bots that learn from the data mined from human behavior in game replays. This can make for much smarter artificial intelligence. In order to conduct their research they are using machine learning algorithms to uncover complex patterns. Check out the article for the full story.

Online Games are a Gold Mine for Design Ideas (newscientist.com)

First, we should start off by explaining what a Turing Machine is. A Turing Machine is a theoretical machine that manipulates symbols on a tape. This machine is simple but easily adaptable. It is able to simulate the logic of any algorithm and is especially useful at explaining how a CPU functions. The machine is named after Alan Turing, who was one of the most significant computer scientists and mathematicians of the early to mid 1900′s. He developed this device as a thought experiment with the purpose of representing a computing machine. It wasn’t meant to be an actual, practical computing device.

In order for a programming language, instruction set, or similar set of data-manipulation rules to be Turing complete it must be able to fully simulate a Turing machine. The rules that follow in sequence on data must be able to produce the result of any calculation. At a minimum, to be Turing complete, the rules must contain conditional branching and the ability to change memory.

It can be proven that something is Turing complete by showing that the rules can simulate the most primitive computer, because even the simplest computer can simulate the most complicated computer.

This is a very basic answer, but this should provide a good overview to get started learning about what it means to be Turing complete. Check out the resources below for additional information.

Additional Resources

• Alan Turing (Wikipedia)
• Turing Machine (Wikipedia)
• Turing Complete (Wikipedia)
• What is Turing Complete? (Stack Overflow)
  

As a relative newcomer to a Computer Science M.Sc. program I have trying to do a lot of reading and understanding outside of the assigned coursework and information from the university. It seems to be difficult at times to understand and digest some of the information out there. Much of it is really complex and I have found that I need to build a better foundational understanding in certain areas of Computer Science before reading some of the more prominent research papers (and other information).

Although I will add additional information and resources to the resources page, I thought it may be beneficial to add some of them in this post to bring awareness to a bunch of good places to start with “beginner” research.

• Reading List for the Self-Taught Computer Scientist (via reddit.com)
• Structure and Interpretation of Computer Programs (via mit.edu)
• MIT Courseware: Electrical Engineering and Computer Science
• Stanford Engineering Everywhere
• Theoretical Computer Science – Stack Exchange (ask questions and find answers)
• Computer Science Unplugged

Also, don’t forget that the resources page contains research papers, external links, and other information.