Computer Science Weekly Newsletter - Thursday, August 28, 2014

Computer Science newsletter

Top new questions this week: Simulate a fair die with a biased die Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a … probability-theory randomized-algorithms random-number-generator   asked by Gilles 11 votes answered by usul 2 votes Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve? So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty … algorithms machine-learning board-games sudoku   asked by user2566092 6 votes answered by Pseudonym 7 votes Why does the solution of an NP problem have to be polynomial size? I've read in "Introduction to Algorithms" (CLRS) that formal language $L$ is NP-language if and only if there is a polynomial verification algorithm $A(x, y)$ and a constant $c$ such that … complexity-theory np   asked by Alexander_KH 5 votes answered by David Richerby 12 votes Base conversion puzzle Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows: Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its … reference-request base-conversion   asked by Rick Decker 5 votes answered by D.W. 3 votes Complexity of Pythagorean triples We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit … algorithms complexity-theory linear-algebra   asked by R B 4 votes Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I … algorithms reference-request optimization parallel-computing matrices   asked by Shaktal 4 votes answered by user3483902 1 vote Do computers actually use carry-lookahead adders? There's plenty of details about carry lookahead adders such as Kogge-Stone, Lander-Fischer, etc. in college CS courses. They are described as "common in the industry". However, I can't find any … computer-architecture   asked by qwr 4 votes Greatest hits from previous weeks: Evaluating the average time complexity of a given bubblesort algorithm. Considering this pseudo-code of a bubblesort: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN … algorithms time-complexity sorting average-case   asked by Sim 7 votes answered by jmad 6 votes Why does a processor have 32 registers? I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the … computer-architecture   asked by Matt Capone 18 votes answered by Wandering Logic 52 votes Can you answer these? Applications of min spanning trees What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. … graphs spanning-trees weighted-graphs applied-theory   asked by D.W. 3 votes Max Flow on low depth DAGs I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG … efficiency network-flow dag   asked by G. Bach 2 votes Boyer-Moore with Don't Cares I have been doing a lot of research into pattern matching algorithms. For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual … algorithms search-algorithms strings   asked by James Monagan 1 vote

Subscribe to more Stack Exchange newsletters Unsubscribe from this newsletter or change your email preferences by visiting your subscriptions page on stackexchange.com. Questions? Comments? Let us know on our feedback site. If you no longer want to receive mail from Stack Exchange, unsubscribe from all stackexchange.com emails. Stack Exchange, Inc. 110 William St, 28th Floor, NY NY 10038 <3