# All Questions

41,511 questions
Filter by
Sorted by
Tagged with
12 views

### Dynamically compute the union of polygons

Shorter version of my question: Is there any polygon union algorithm that allows me to change one of the polygons quickly? Longer version: Currently the major performance bottleneck I'm facing in one ...
10 views

### Task scheduling with the constraint of pairs of objects being present in a cache

I'm writing some software that involves processing a large collection of images that are arranged spatially. It basically involves loading pairs of images into caches and computing an operation on the ...
10 views

### What is the return value of the following code R(n) = 2R(√n) + n?

Algorithm rec(n) { if (n ≤ 2) return 1 else { return (2*rec(√n) + n) } } Return value recurrence relation, I want to find the exact value and not ...
56 views

### What does it mean for a computer to be general-purpose?

There is a lot of Turing machine out there. Most of them are purpose-specific. What make universal Turing machine universal? How do we know or prove if a computer is universal? Edited: Is ...
19 views

### How to prove that the generalized assignment problem (GAP) is NP-hard?

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...
14 views

### minimum insertions and deletions required to ensure that each value X occurs X times

I would like to brainstorm/get some advice/tips regarding the following question. Given an array,you can either insert elements or you can delete elements from it.Note the insertion/deletion must be ...
20 views

### What is the approximation ratio of this bin-backing algorithm?

Consider the following algorithm for bin packing: Initially, sort the items by their size. Put the largest item in a new bin. Fill the bin with small items in ascending order of size, up to the ...
63 views

### An “easy” graph problem I can't solve

The question is: A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2) And a origin vertex s. Write an efficient algorithm that finds the ...
31 views

### Automatically find a set of equations

Let $A$ be a finite set of variables. Let $B$ be a finite set of equations of the form $(\sum_{x \in C}x - \sum_{x \in D}x = a)$ where $C$ and $D$ are two disjoint subsets of $A$, and $a$ is an ...
44 views

55 views

### Is it possible to recover induction for nat from W-types?

W-types generalize the type of well-founded trees, i.e., possibly infinetely branching trees. I understand that inductive types may be encoded as such in dependent type theory (CIC, MLTT, etc), this ...
107 views

### Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
33 views

### Determine if for given some $L$, $S_L={L(M) : <M>\in L}$ then for any $L$, if $S_L=RE$ then $L\in R$ is True or False and explain

Determine if for given some $L$, $S_L=\{\ L(M) | <M>\in L \}$ then for any $L$, if $S_L=RE$ then $L\in R$. Correct or Incorrect and explain why. I think the claim is incorrect, and I'm trying ...
49 views

### Is there a difference between extremely slow growing functions and constants with respect to computable functions?

So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...
30 views

### Counting substrings of a string that do not contain a given string

Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
46 views

### Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time

We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just ...