Algorithms

It has also been a big year for algorithms. No-one actually proved P=NP, but a result at the end of the year was almost as good. 

The first important result was that the algorithm for the edit distance between two strings was optimal and there was no point in continuing for something that did the job more efficiently. This is a disappointment because edit distance is important in practical applications. However from a theoretical point of view the proof isn't quite complete because it assumes the strong exponential time hypothesis. What this means is that if you can find a better algorithm you have proved that the SAT problem can be solved in sub-exponential time which would be a step on the way to P=NP. 

Not such a great algorithmic breakthrough, was the discovery of a new sort of pentagonal tiling. A programmed search with some help from humans narrowed down the space and eventually found the new arrangement.

Another more mathematical result was the proof of the Erdos conjecture by Terence Tao who studied for a time as a child with Paul Erdos. The conjecture itself isn't of any great practical use, but who knows. What it does is give us some insight into how irregular infinite random sequences are allowed to be. 

The final big breakthrough was at the end of the year was the proof that the graph isomorphism problem is soluble in quasipolynomial time which is practically speaking as good as polynomial time. Again this isn't a proof that P=NP but one problem in NP is so close to being in P that it makes no real difference. However the problem isn't known to be NP complete so even if it was proved to be in P it wouldn't follow that P=NP. The proof is still being worked over by interested computer scientists.  

And to bring this review of the year to a close an interesting problem with a simple algorithm.  It seems that you are not wrong and your GPS tracker does usually turn in a longer distance for your run or your walk than you have actually done. The algorithm is simple, just add up the straight-line approximation distance given by the GPS locations. This should under estimate the length of the true curved path. However the problem is the way that unbiased errors in location produce distance estimates that are biased high. The reason is to do with the fact that a straight line is the shortest distance between two points and so random shifts in both point tend to increase the distance. For 2016 the question is "how to fix it?"

Edit Distance Algorithm Is Optimal 

Computer Finds New Pentagonal Tiling - With Some Human Help 

 Erdos Conjecture Proven 

The Computer Science Breakthrough Of The Decade 

GPS Always Overestimates Distances 

Languages

The two biggest language oriented news items of the year were the open sourcing of .NET including the compiler for C#, Visual Basic and F# and the open sourcing of Apples Swift. Both events haven't really played out just yet and we will have to wait for 2016 to get underway to see how both settle down but Swift is having a much bigger impact than you might have expected from such a modest language. Yes Swift is better, easier, then Objective C but it really doesn't offer much that cannot be found in other languages. For Apple iOS programmers moving to Swift makes a lot of sense but for other environments it isn't clear what the fuss is about.

The open sourcing of .NET is perhaps more important and yet is made less of a splash - perhaps because it is a much more extensive system and the situation is much more complicated. 

The other notable language event of the year was the release of JavaScript 6 under the name ECMA 2015. The use of the year in the release is part of the intention to keep producing new versions of the language as often as once per year.

Even the Oxford English Dictionary noted the event and added JavaScript to its list of words. At the same time TypeScript developed along side JavaScript to reach version 1.7 by the end of the year. With Microsoft's help TypeScript seems to be the logical alternative to JavaScript. 

Also important was the release of PHP 7 the first major update of the language for a while. It promises to be faster and more logical and an all together better language. For most programmers however PHP's reputation for being a mess continues. What is most important about the language is its vast infrastructure and wide ranging function libraries. PHP isn't used so much because its it elegant but because if you want to do X you simply have to look for a function that does X in the library even if X is fairly complicated. 

Other languages progressed. Rust made version 1.0 and version 1.4 by the end of the year. Ruby made it to version 2.3, Python got to 3/5 and iPython made version 3 and changed its name to Jupyter.

The big surprise was the announcement of WebAssembly a sort of real assembler for the web. However if you know what an assembly language looks like this one doesn't fit the bill. It is simply a coded up abstract syntax tree - it will be interesting to see how this turns out.

And finally right at the end of the year Perl 6 was finalized, ending years of jokes about when it would be ready. If anyone will use it we will have to wait and see, but it clearly doesn't stand much chance of being as popular as the original Perl. 

.NET Goes Open Source 

Apple Open Sources Swift 2 

Apple's New Language - Swift  

JavaScript 6 EcmaScript 2015 Final Approval 

TypeScript 1.7 

Rust Releases New Versions

Rust Hits Stable 1.0 - So What?

PHP 7 Released 

Python 3.5 Released 

Jupyter 4.0 Completed By Release of IPython 4.0 

Rust 1.3 Released 

WebAssembly Has Mozilla, Microsoft,Apple and Google Backing It 

Progress On WebAssembly 

Perl 6 First Official Release 

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info