Glider from the game of Life, rising from the left

Unity

Archives

Blogroll

Topic: #algorithms

How Graphical Programming Languages Look to Me

2018-05-24⊺09:44:12-05:00

“IDEA — Nonverbal Algorithm Assembly Instructions”
Sándor P. Fekete, Sebastian Moor, and Sebastian Stiller, IDEA, May 24, 2018
https://idea-instructions.com

#algorithms #programming-languages #humor

Machine Learning Sorting

2018-05-15⊺11:52:14-05:00

“An O(N) Sorting Algorithm: Machine Learning Sorting”
Hanqing Zhao and Yueban Luo, arXiv, May 11, 2018
https://arxiv.org/pdf/1805.04272.pdf

The authors propose a new method for sorting a gigantic array of arbitrary values in linear time: Select a fixed number (say 1000) values from the array and sort them. Using these values as a training set, train a three-layer neural network to estimate the position in the sorted array that any given value will occupy. Set up an array of buckets equal in size to the original array. Feed each value in the array into the neural network and put it in the bucket corresponding to the network's prediction of the value's position in the sorted array. A linear-time amount of post-processing can now ensure that every value is in a bucket that is within a fixed distance of its position in the sorted array. Apply insertion sort on the almost-sorted values in the array of buckets to build the actual sorted array. Since insertion sort runs in linear time on almost-sorted arrays, the whole process, including the training of the neural network, takes linear time.

I wouldn't have thought of that one.

Next month in arXiv: Adversarial sorting examples.

#algorithms #machine-learning #connections

An Ethics Checklist for Black-Box Deciders

2018-05-07⊺16:51:40-05:00

An attempt to identify and explain the ethical preconditions for replacing social policies with algorithmic models. It's incomplete, but the questions that are included are relevant and salient, and the cautionary tales and links are thought-provoking.

“Math Can't Solve Everything: Questions We Need to Be Asking Before Deciding an Algorithm Is the Answer”
Jamie Williams and Lena Gunn, Deeplinks, Electronic Frontier Foundation, May 7, 2018
https://www.eff.org/deeplinks/2018/05/math-cant-solve-everything-questions-we-need-be-asking-deciding-algorithm-answer

#black-box-deciders #ethics-in-daily-life #algorithms

Sums of Palindromes

2018-04-10⊺13:37:27-05:00

“Every Positive Integer Is a Sum of Three Palindromes”
Javier Cilleruelo, Florian Luca, and Lewis Baxter, arXiv, June 17, 2017
https://arxiv.org/pdf/1602.06208.pdf

The authors provide an algorithm for finding the palindromic addends but don't include any source code. The algorithm works for any integer base greater than or equal to 5.

#discrete-mathematics #recreational-mathematics #algorithms

It's Time to Get Serious about Algorithms

2018-01-29⊺11:33:37-06:00

For decades now, lazy programmers have relied on ever-faster processors and ever-larger memories to avoid learning about subtle but efficient algorithms and fast data structures with intricate invariants. Now the jig is up.

“Death Notice: Moore's Law. 19 April 1965 — 2 January 2018”
Mark Pesce, The Register, January 24, 2018
https://www.theregister.co.uk/2018/01/24/death_notice_for_moores_law/

The computer science behind microprocessor design has therefore found itself making a rapid U-turn as it learns that its optimization techniques can be weaponized. The huge costs and Meltdown and Spectre — which no one can even guess at today — will make chip designers much more conservative in their performance innovations, as they pause to wonder if every one of those innovations could, at some future point, lead to the kind of chaos that has engulfed us all over the last weeks.

One thing has already become clear: in the short term, performance will go backwards. The steady … improvements every software engineer could rely on to make messy code performant can no longer be guaranteed. …

Going forward, the game changes from “cheaper and faster” to “sleeker and wiser.” Software optimizations — despite their Spectre-like risks — will take the lead over the next decades. …

From here on in, we're going to have to work for it.

#spectre #Moores-law #algorithms

Hashtag index

This work is licensed under a Creative Commons Attribution-ShareAlike License.

Atom feed

John David Stone (havgl@unity.homelinux.net)

created June 1, 2014 · last revised December 10, 2018