# Tag Info

### Efficient search of a large set of documents to find documents that only contain a particular set of words

You are trying to compute the set $$E = \{e \in D \mid e \subseteq K \land e \cap S \ne \emptyset\}.$$ There is a naive algorithm. Store $K,S$ in a hashtable (using a hash function that maps each ...

### Allocating m rooms of varying capacity to n booking requests of varying sizes

One plausible approach is to use integer linear programming. Introduce 0-or-1 variables $x_{q,r}$, where $x_{q,r}=1$ means that room $r$ is assigned to request $q$. Then you can write down linear ...
1 vote

### Counting the number of parenthesization

The split in a product is between the two outermost pairs of parantheses. For example, in $((a*b)*(c*d))*(e*f)$, the split is between the $d$ and $e$ because the last multiplication that is performed ...

### Counting the number of parenthesization

Suppose you have $n$ matrices $M_1, M_2, …, M_n$. The product of all matrices is $M_1\times M_2\times…\times M_n$ and since the matrix product is associative, there is no need for parentheses from a ...
Accepted

### Formal Proof on why Greedy isn't working on one Particular Problem

To prove that the greedy algorithm is not optimal, it suffices to give one counterexample, i.e. one problem instance $nums$ and $mult$ such that it is possible to obtain a value that is larger than ...
1 vote

### Optimizing an arbitrary function of 10 variables

There are only 19448 combinations of $x$'s that meet the constraints. If $f$ is arbitrary, the best you can do is enumerate all 19448 combinations and see which leads to the largest value of $f$. ...
Accepted

### Time complexity analysis for dynamic programming using memoization

The time-complexity of dynamic-programming with memoization Here is the simple principle. Suppose an algorithm applies dynamic programming to solve a problem, with the majority of running time spent ...

### Optimizing an arbitrary function of 10 variables

I do not see a dynamic programming solution. I highly doubt there is one (especially, a polynomial time).

### Factor a number in the longest possible product of distinct numbers

A nice problem. You will have to do some rather exhaustive / exhausting search :-) First, ignore the number 1. Make all your factors products of one or more primes, and add the number 1 at the end. ...
1 vote

### Solve modified knapsack problem using dynamic programming

Let $C \ge 1$ be the capacity of the knapsack and let $G_1, \dots,G_k$ be your groups, where each group is a non-empty collection of items, i.e., $G_i = \{ x^{(i)}_1, x^{(i)}_2, \dots \}$. Groups are ...
Accepted