Given an array of integers having at least two elements, compute the sum of squares of the difference between all pairs of elements. It is not hard to quickly write up a O(N²) program using nested loops, which, I have to confess, is what I would do before reading Kaldewaij’s book and realised that it is possible to do the task in linear time using one loop.
Research
Agda Approximation Bidirectional Updating Burrows-Wheeler Transform Concurrency Converse-of-a-Function Theorem Curry-Howard Data Structure Dependent Type Fibonacci GADT Galois Connection Greedy Theorem Haskell HaXML Imperative Programs Indirect Equality List Homomorphism Logic Logic Programming Optimisation Problems Program Derivation Program Inversion Quantum Programming Quine Regular Expression Segment Problems Termination Thinning Theorem Types XML Streaming λ calculusRecent Comments
- wren ng thornton on Proving the Church-Rosser Theorem Using a Locally Nameless Representation
- Smit Patel on The Maximum Segment Sum Problem: Its Origin, and a Derivation
- Jeremy Gibbons on The Maximum Segment Sum Problem: Its Origin, and a Derivation
- Hao Deng on Calculating Programs from Galois Connections
- José Oliveira on Calculating Programs from Galois Connections