Theory

recent formal proof re: seL4 microkernel
On Sunday 22 November 2009 13:38, David Bernier wrote: "seL4: Formal verification of an OS kernel" presented at Proceedings of the 22nd ACM Symposium on Operating Systems Principles, Big Sky, MT, USA, October, 2009 ... [PEB] < http://ertos.nicta.com.au/research/sel4/ > . --- Having... 23 Nov 2009 14:06

Math/CompSci Interview Question - Thoughts?
I was posed the following question in a technical interview for a Software Engineering position by a major multinational NASDAQ company: [Paraphrasing] "You are given an array of 1,000,000 32-bit integers. One int value x occurs 500,001 times or more in the array. Specify an algorithm to determine x." The as... 4 Mar 2010 04:30

Unhashing int64 to string
A classic string hashing algorithm can be simply described by the following code (C++ like pseudo code) int64 hash(string s) { int64 hash = 5381; for (i = 0; i < s.length; i++) hash = (hash * 33) XOR s[i]; return hash; } Is there any known approach to "unhash" a string (consisting no more th... 19 Nov 2009 18:36

Coins on chess-board puzzle
Hi, I recently heard about a very nice puzzle with a computer science / TCS flavor. The person who told me it had found a solution, but the person who told them didn't even know if there was a solution. Here is the puzzle: ---- A room contains a normal 8×8 chess board together with 64 identical coins, eac... 8 Feb 2010 11:05

Fractional Knapsack Problem
Hello, I would greatly appreciate it if some one could shed some light on this problem. The 0/1 Knapsack problem has been proven to be NP complete for a single knapsack as well as the multiple knapsack cases. The fractional knapsack (single knapsack case) exhibits greedy optimal solution. My questions is as fo... 16 Nov 2009 10:08

Complexity of Knapsack
Hello All. I was wondering if someone could shed some light on this topic. The one dimensional Knapsack problem (0/1) knapsack is a NP complete problem. The fractional version of this problem ( where in you can take a fraction of the item ) is shown to optimal in polynomial time. I have a problem where in i h... 13 Nov 2009 19:59

The real deal: Proof of Cook's Theorem in Unary - Thank you Sci.Math for your patience and kindness
/ ![CDATA[ (function(loc) { var prefix=""; if (prefix && loc.pathname == '/') { return; } var uri_re = /^(?:(?:[^:\/?#]+):)?(?:\/\/(?:[^\/?#]*))?([^? #]*)(?:\?([^#]*))?(?:#(.*))?/; var target_domain = ''; loc.href.replace (uri_re, function(all, path, query, frag) { var dst, src; dst = src = path + (query ? '?' + q... 10 Nov 2009 08:03

Considering the forces of computation: questions for the group, I have three:
1) Imagine if instead of numbers we used colors. This is to say there are arguably as many shades of colors as there are numbers, and for as many as we usually represent in programming, but what if instead, I said instead of five being represented by '5' five was instead 'blue'? Not that I thought five was a partic... 1 Nov 2009 14:23

Monadic Spacing in Binomial Partite
1. Overview 2. String Functions 1. like 2. lower 3. ltrim 4. rtrim 5. ss 6. ssr 7. string 8. sv 9. trim 10. upper 11. vs 3. Mathematical Functions 1. acos 2. asin 3. atan ... 31 Oct 2009 13:16

19990823: General announcements. Goedel's question: if a theorem has a proof of length at most n, can we find it in time O(n^2)? Another question on what can be computed in limited time and space.
19990823: General announcements. Goedel's question: if a theorem has a proof of length at most n, can we find it in time O(n^2)? Another question on what can be computed in limited time and space. Overview of related topics from courses on algorithms, theory of computation, formal logic. Definition of composite. De... 27 Oct 2009 00:29