Dec. 14th, 2015

gareth_rees: (Default)

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

Instances of this problem often arise in the solution of combinatorial problems … )

gareth_rees: (Default)

The story so far: I wrote a solver for a generic exact cover problem in Python, and used it to find polyomino tilings. The reason for using Python was because Python’s simplicity, terseness, and flexibility makes it easy to write solvers for other combinatorial problems. So let’s have a look at a second problem … )

gareth_rees: (Default)

When I had interviewed for the job, the interviewer had explained that I was needed to work on their JavaScript engine. The company was a web development tools startup, and they had spotted that it would be a good idea to have JavaScript code running on the server as well as on the client, so that you could share your business logic and validation code between the client-side and server-side parts of your application. There are now lots of products in this space but twenty years ago was probably too soon for this to be a success.

Anyway, the interviewer told me that the JavaScript engine was nearly done, but there were one or two features that were missing, and it was running a bit slowly, so I might have to do a bit of optimization. Sure, I said, that sounded like it would be fun … )

Profile

gareth_rees: (Default)
gareth_rees

December 2015

S M T W T F S
  12345
6789101112
13 141516171819
20212223242526
2728293031  

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 10:13 pm
Powered by Dreamwidth Studios