Problem Detail: I can think of functions such as $n^2 sin^2 n$ that don’t have asymptotically tight bounds, but are there actually common algorithms in computer science that don’t have asymptotically tight bounds on their worst case running times? Asked By Read More …
Author: ignougroup
[Solved]: If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?
Problem Detail: If all infinite r.e. languages have an infinite recursive subset, then can we logically take co-r.e. languages to not have such subsets by complemence? Asked By : user2896468 Answered By : Yuval Filmus In one word: no. It doesn’t follow logically. Read More …
[Solved]: Floating point rounding
Problem Detail: Can an IEEE-754 floating point number < 1 (i.e. generated with a random number generator which generates a number >= 0.0 and < 1.0) ever be multiplied by some integer (in floating point form) to get a number equal Read More …
[Solved]: Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$
Problem Detail: I’m trying to solve exercise 6.5 on page 309 from Richard Crandall’s “Prime numbers – A computational perspective”. It basically asks for an algorithm to factor integers in randomized polynomial time given an oracle for taking square roots modulo Read More …
[Solved]: Is this an instance of a well-known problem?
Problem Detail: Context I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I would like to get Read More …
[Solved]: How to perform alphabetically ordered DFS?
Problem Detail: I’ve been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. Read More …
[Solved]: Voronoi diagram algorithm with non-euclidean metric
Problem Detail: Do you know any easy to implement algorithm for constructing a Voronoi diagram from a given set of points on a surface, using some different metric (taxicab, for instance)? It can be some modification of Fortune’s algorithm. Asked By Read More …
[Solved]: What’s a uniform shuffle?
Problem Detail: What does it mean exactly a “uniform shuffle” algorithm ? Is this method considered a uniform shuffle ? public void shuffle(Comparable[] a) { int n = a.length; int k, j; for (int i = 0; i < n; i++) Read More …
[Solved]: A logic function that is true iff the first operand is less than the second operand
Problem Detail: In my computer organization class I have been given a series of problems. One I’m stuck on currently is below: Assume that $X$ consists of 4 bits, $x_3 x_2 x_1 x_0$, and $Y$ consists of 4 bits, $y_3 y_2 Read More …
[Solved]: Can the human brain be considered Turing complete?
Problem Detail: I’m not a student in computer science, but from what I understand from the Wikipedia article on the topic, a programming language is Turing complete if it can emulate another Turing complete language’s algorithm. Now if we consider that Read More …
