# Tag Info

18

This problem (more formally its decision version) is NP-complete. NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard. In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a ...

14

What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and ...

7

The answer depends heavily on what operations you allow to appear in the trees. If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm. Basically, you pick random values for $a,b$ and check whether both trees return the ...

6

Thanks to "user2357112 supports Monica" for pointing out issues! Now fixed. Let's formulate the decision problem form of this problem, which I'll call Tree Scheduling (TS): Given a number $k$, and a rooted tree with tasks $t_1, \dots, t_n$ for vertices, each having some integer duration $l_i$ and requiring some resource $r_i$ from a set $S$ of ...

5

Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see problem 2). So in that sense it's not really a modification, it's how Dijkstra himself described the algorithm to begin with. As Wikipedia puts it: Dijkstra's original algorithm found the shortest path between two given nodes,[6] but a more common ...

5

If you're looking for algebraic structure, then you should look at the field of denotational semantics. This is exactly what you describe: using algebra, and often Category Theory, to model computation mathematically. Some examples: Domain theory provides a mathematical model of the untyped lambda calculus, which is powerful enough to capture all computable ...

4

Python-specific questions are probably off-topic here, but this question can be seen as a language-agnostic algorithmic task: given two arrays $A$ and $B$, each representing a multi-set, return an array containing the elements in the multiset $C = A \cap B$. Here an element $x$ that has multiplicity $a$ in $A$ and $b$ in $B$, has multiplicity $\min\{a,b\}$ ...

4

Just for fun, I've constructed the TM sketched by Rodion, you can simulate its behaviour here. Observe that I assume $p$ (or $m$, which is the same) strictly positive; moreover one actually has to use two cells outside the input, namely the cell immediately to the left of the first symbol of the input and the one immediately to the right of the last symbol ...

4

This problem can be solved in two steps. First, you need to work out the $k$ by repeatedly "dividing" the string by $3$, and storing how many times this was repeated. For example, each "division" will process the zeros in triplets. Each triplet will replaced by one zero, and in the first triplet processed you store a "1", as an ...

3

Obviously, $f(n)+o(f(n))=\Omega(f(n))$ (clearly, I'm assuming all functions being positive), so you need only to prove that $f(n)+o(f(n))=O(f(n))$. But a function in $o(f(n))$ is definitevely smaller than $f(n)$, so for sufficient large $n$ you have $f(n)+o(f(n))\leq 2f(n)=O(f(n))$. Actually, in the same way you can easily prove also this stronger claim: $f(... 3 While Steven's answer is correct, it runs in time$O(n \log n)$. Here is a Pythonic way of doing it that uses dictionaries and runs in linear time. from collections import Counter A = [2, 2, 4, 5, 4, 5, 6] B = [2, 3, 4, 4] CA = Counter(A) CB = Counter(B) solution = [] for e in CA: occurrences = min(CA[e], CB.get(e, 0)) solution += [e]*occurrences ... 3 Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph$G$, to define a polynomial$P_G$which is nonzero iff$G$has$k$disjoint triangles. If you could evaluate$P_G$on an arbitrary point in the underlying field$\mathbb{F}$in time$2^{3k}n^{O(1)}$then Schwartz-Zippel gives ... 3 Use a product construction, to construct a new graph whose vertices are given$(x,y,z,k)$, where$k$counts the index into the sequence of colors (i.e., we are currently at$k$th vertex in that sequence). Then, find the shortest path in this new graph using any standard shortest-path algorithm. If all weights are non-negative, you can use Dijkstra's ... 3 In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this). However, if you know more about the structure of the array, there are plenty of things you can do. For example, imagine the array has the following property: its elements are sorted increasingly up to a ... 3 If the algorithm terminates at all then$A[i] = i$for$i \leq n-1$, and so$A$is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching$i = i_0$, we know that$A[j] = j$for$j < i_0$, and so$A[i_0],\ldots,A[n]$is a permutation of$i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices ... 2 There sure is. Some sort of backtracking program will do the job. If you want the minimal number of moves, perhaps the (memory expensive) way to go is breadth first search. Maybe you can squeeze some performance out of it by adding conditions to cut off impossible branches or stop expanding when the current path is longer than the current best, or heuristics ... 2 I can give you the intuition behind Bellman-Ford. It is beautiful! I'm going to do it in an indirect way. I want to share a warm-up puzzle that might seem unrelated, but stay with me. Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the ... 2 This is a very simple question, I will explain steps-by-steps: First, you need to count total elements and total comparisons in your tree Second, you need to know that for each element in the tree, it takes$\frac{total \ comparisons}{total \ elements}$average comparisons to search for an element in the tree. Third, if the problem gives you a probability to ... 2 Knuth wrote a chapter on this, as part of the new volume 4 of his Art of Computer Programming. The simplest algorithm uses the following recursion to generate all combinations of length$m$of a set$x_1,\ldots,x_n$: If$m = 0$then output the empty set. Otherwise, for each$m \leq i \leq n$, generate all combinations of length$m-1$of$x_1,\ldots,x_{i-1}$,... 2 Count the number of times each of the 5 new element is moved in the array: The areay is of length$n$, and thus each of the 5 elements move at most$n$times. The place of all other elements is correct, and thus there is at most$5n$swaps required to "correct" the array, hence$O(n)$swaps. 2 It's widely known, that$f=\Theta(g)$we understand as "one direction" equality i.e.$f \in \Theta(g)$. But when we write something like$\Theta(f) = \Theta(g)$, then situation becomes slightly different: now it is equality between sets, so need proof in "two directions". Equality$f+o(f)=\Theta(f)$formally considered as equality between ... 2 If I correclty understand the algorithm, your TM starts "marking" the first$a$, then it finds the first$b$and marks it, then it comes back the the first unmarked$a$and so on. So, assuming that you have in input a string$w$of lenght$n$that belongs to the language$L$, you have$\frac{n}{2}a$'s that have to match with the same number of$...

2

Here is a cleaner and better way to solve the problem. # Return the smallest index where the element is bigger than A[start_index]. # If len(A) is returned, no element is bigger than A[start_index]. def next_bigger_element(start_index, A): lo, hi = start_index, len(A) while lo + 1 < hi: mid = (lo + hi) // 2 if A[mid] == A[...

2

Let's denote the indices by $l,h,m$. If $l \leq h$ and $h-l$ is even then $m = \frac{l+h}{2}$ and so in the following iteration, the new values $l',h'$ will either be $\frac{l+h}{2}+1,h$ or $l,\frac{l+h}{2}-1$. In the first case $$l'-h' = \frac{l-h}{2}+1 \leq 1,$$ and in the second case $$l'-h' = \frac{l-h}{2}+1 \leq 1.$$ If $l \leq h$ and $h-l$ is odd ...

2

I think you might have misunderstood the heuristic function. It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$. The closer this estimate is to the true value, the better A* will perform. The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $... 2 Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave. There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still ... 2 Interpreting your problem as finding a computable$f$such that$f\big(\langle M\rangle\big)=\langle M'\rangle$with the property that$M'$enumerates all programs equivalent to$M$, i.e. all$M''$with$L(M'')=L(M)$, the answer is no (such$f$does not exist). One way to show this is to observe that such$f$would place the language$\left\{\big(\langle M_1\...

2

The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step. The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case. You can solve your problem in $O(n)$ worst-case time as follows: create a max-heap with the elements in the ...

2

It is NP-Hard as others have said, but... sometimes there is an easier way to solve it. You can do a Lagrangian relaxation to essentially remove the NP-hardness solve that problem, and then use that as an initial guess for the original problem. Pekny and Miller essentially did something like to for the Asymmetric Traveling Salesman problem. They reduced it ...

2

While I cannot answer your question (MOOC for Dasgupta et al), I will make a different recommendation. Since you seem to like the more intuitive and slightly informal approaches to learning, rather than the more formal and proof oriented approach, I think you might like the algorithms book series by Tim Roughgarden, Algorithms Illuminated. Algorithms ...

Only top voted, non community-wiki answers of a minimum length are eligible