Computer Science Weekly Newsletter - Thursday, January 29, 2015

Computer Science newsletter

Top new questions this week: Why is this argument for $P\neq NP$ wrong? I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some ... complexity-theory p-vs-np oracle-machines   asked by Ariel 10 votes answered by usul 9 votes Arbitrary precision integer square root algorithm? Are there any known subquadratic algorithms for calculating the floor of the square root of an n bit integer? The naive algorithm would be something like def sqrt(x): r = 0 i = ... algorithms numerical-algorithms   asked by Antimony 7 votes answered by D.W. 3 votes Who coined the term "machine learning"? I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ... terminology reference-request machine-learning history   asked by robguinness 7 votes Efficient algorithm to compute the $n$th Fibonacci number The $n$th Fibonacci number can be computed in linear time using the following recurrence: def fib(n): i, j = 1, 1 for k in {1...n-1}: i, j = j, i+j return i The $n$th Fibonacci ... algorithms time-complexity recurrence-relation   asked by augurar 7 votes answered by Yuval Filmus 10 votes Determining if $G$ contains $K_4$ as a minor in polynomial time I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of ... algorithms graphs lower-bounds   asked by Lester X 6 votes answered by Pål GD 1 vote Is this combinatorial optimisation problem similar to any known problem? The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ... algorithms optimization combinatorics approximation   asked by fiftyeight 5 votes Common method for solving satisfiability problems which lie in P I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific ... complexity-theory satisfiability polynomial-time sat-solvers   asked by Ari 5 votes answered by Yuval Filmus 4 votes Greatest hits from previous weeks: How to implement two stacks in one array? I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and ... data-structures arrays stack   asked by Suyash Gupta 11 votes answered by G. Bach 6 votes How can I teach computer science without using computers? In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages ... education   asked by Abhimanyu 17 votes answered by David Richerby 20 votes Can you answer these? Proving $CVal$ is $RP$-hard Let CVal be the language of all $<C,s>$ where $s:\{x_1,...,x_n\} \rightarrow \{0,1\}$, such that $C$ is a variable-free Boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and it outputs ... complexity-theory complexity-classes   asked by TheEmeritus 1 vote How to find (real-valued) roots of matrix polynomial Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial $$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$ Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ... algorithms complexity-theory matrices polynomials root-finding   asked by R B 1 vote Constructing a TM from empty string Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ... algorithms turing-machines strings nondeterminism   asked by user4325010 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