# Tag Info

0

Uniform cost search is a tree search algorithm related to breadth-first search. Whereas breadth-first search (BFS) determines a path to the goal state that has the least number of edges, uniform cost search (UCS) determines a path to the goal state that has the lowest weight (minimum value).

0

The reason why your algorithm produces desired sequences in a very low rate is that you are generating random numbers that are too large on average. A simple remedy is to change line 2) of your pseudocode to 2) generate random number between 1 and 55, let's say rand = 24 Here 55 is slightly bigger than 48 = 99//4 *2, where 4 = 5 -1 is the number of ...

0

STL maps are stored in a data structure which is effectively sorted by key, typically some kind of binary search tree. BSTs have the property that finding the smallest key and finding the next larger key are both amortised O(1) (assuming you can find a node's children in constant time). So doing your merge is similar to merging n sorted arrays, which has ...

1

The problem you are describing is a special case of the (weighted) 3-dimensional matching problem.1 Unlike regular 2-dimensional matching, maximum cardinality 3-dimensional matching is NP-hard, which means that weighted 3-dimensional matching is NP-hard. Therefore, solving this problem exactly in polynomial time doesn't seem feasible, unless the specific ...

0

-- generate ALL sequences of n natural numbers with given sum -- should be called with n<=sum gen(n,sum): for i in 1..sum-n+1: -- next number in sequence is i gen(n-1,sum-i) -- generate ALL possible sequences of remaining numbers

0

Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one. for i: if a[i] != a[i-1]: if run[x] - run[x-1] >= 3: x-- // avoid copying the run into output array if a[run[x]] != a[i]: x++ run[x] = i On ...

0

Not sure if I get your question right, as you didn't specify whether this is a theoretical problem or a practical. Assuming it is practical problem, there are quite some algorithms (e.g. TCP) depending on which layer your messages are being send (if they are being send at all). Assuming it is more of a theorectial problem you can use stuff like the ...

0

Implying that they have usual line length (10-100 chars on average), I will sort both files. It can be done almost in-place using technique Fast, stable, almost in-place radix and merge sorts

3

7 is the least number of questions that you can ask to guarantee to find the treasure. the idea of binary search Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search. the binary search on ...

1

Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation. The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. ...

0

There is a neat way to solve this with dynamic programming. First of all we can notice that the minimal number of moves will always be at most $9 * \lg(N)$. Let's denote this number as $B$. Now let's have the a recursive function $f(u, d)$, which returns true or false depending on whether there is a path of length exactly $d$ from $Start$ to $u$ (in our ...

0

Actually, no algorithms, efficient enough for you to be interested in, are available. Your problem is exactly the membership problem for the class of linearly separable boolean functions (which are the indicator functions of your sets), and it is known to be co-NP-complete.

0

doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list. merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.

-3

You can just traverse the graph in dfs manner and check if(distance[dest] > distance[source]+cost[source_to_destination]){ distance[dest] = distance[source] + cost[source_to_destination]); } Here is the link for full solution

0

If you are looking at theoretical results, they are theoretical. If you are looking at practical results, the one that is more important is the one that keeps you from getting results. For the price of a small new car, I can buy a computer with $2 \cdot 10^{12}$ bits of RAM, which can perform about $5 \cdot 10^{15}$ operations per day. With that computer, ...

1

This is a question in combinatorics, and can be calculated in a closed formula. The key settings are: "Down" is not allowed Visiting previously visited square is not allowed From the two requirements, we can draw the following conclusions: Up is always a valid move (since we never went down, going up is essentially revealing a new square) Left is not ...

0

Obervations : As you only allow for up and left/right moves, when you leave a row (by going up), you can't come back to it. As you cannot revisit the same node in a given path, when you go right on a row, you can't go left afterwards. I think this can lead to a direct formula for paths of length $n$, but you can first try to compute the paths with $k$...

2

To add to what Apass.Jack said, in most computational models (e.g. Turing Machines, maybe RAM as well, I don't know), space used is bounded by time : you need to do at least one operation per unit of memory to "use" it. For example you won't find algorithms with $O(n^2)$ time complexity and $O(2^n)$ space complexity. Space complexity is usually studied/...

2

In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon which applies to the cryptography as well. There are much more about time-complexity to talk about in computer science and software industry while space-...

3

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes. Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. ...

1

It can be solved in $O( V + E)$ We initialize distances to all vertices as minus infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear ...

1

I think that the fastest approach with modern CPUs is i = num & 255 j = num >> 8 *x = x1[i] + x2[j] *y = y1[i] + y2[j] That is 4 arithmetic ops plus 4 loads

1

The answer depends on what you mean by a sorting algorithm. The usual meaning is: A sorting algorithm is an algorithm that gets a list $L$ of comparable objects, and sorts them in (say) nondecreasing order. The algorithm could only work for a certain class of objects. If you use this definition, then PageRank isn't a sorting algorithm. But it's up to you....

0

The given algorithm is correct. The flow network constructed need to be directed, and the value of a $S$-$T$ cut only considers edges going out of the vertex set $S$.

1

First, note that for any $a$, since XOR is associative: $$(a \oplus b) \oplus b = a \oplus (b \oplus b)$$ Since $b \oplus b$ is $0$ and $0$ is neutral for XOR, we get that: $$(a \oplus b) \oplus b = a \oplus (b \oplus b) = a \oplus 0 = a$$ In other words, there is no point performing XOR operation more than twice, for any $a$ with any $Q$. You can either ...

0

Yes, there are ways to improve the efficiency greatly. Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages, ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$. ...

1

This problem is call "$X$-satuated bipartite matching" or Hall's marriage problem, which is discussed at here on Wikipedia. Consider each item as a woman. Each bag is a man. If item $a$ is allowed to be placed in bag $x$, it means woman $a$ and man $x$ can be married happily. Only one item can go in each bag corresponds to the assumption of monogamy, a man ...

1

We have $z^\lambda$ has the form of $$f(z)u(z) + p^ev(z) + 1$$ where $p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$ and $v(z)\not\equiv 0\pmod p\$ (*) You misunderstood the definition of $a(z)\equiv b(z)\pmod {f(z)\text { and }m}$. If $z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$ for some $u(z), v(z)$. There ...

0

For a partition $p$ of some numbers into $N$ parts, let $\delta(p)$ be the largest difference between the sums of numbers in the same part, i.e., $\delta(p)=\max_j S_j - \min_j S_j$, where $S_j$ is the sum of numbers in $j$-th part, $1\le j\le N$. This answer gives an approximate algorithm that is about as fast as possible and as simple as possible. It ...

3

Step 1. Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point. Step 2. Define a mapping $M$, where the key will be a closed integer interval and ...

0

You may want to look at "Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows" by David Karger and Serge Plotkin (STOC 1995). They find a $(1+\epsilon)$ approximation in ${\tilde O}(\epsilon^{-3}kmn)$ time, where $k$ is the number of commodities, $m$ is the number of edges, and $n$ is the number ...

1

Sort the points indexes on increasing $x_i$ (time complexity $O(N\log N)$). Then, with one loop on this sorted list, you can create the following structure: $GX$, list of sublists where points in the same sublist share the same $x$ value. $AX$, array of size $n$ giving for any $i$ the index of the sublist that contains $i$ in $GX$. Once it is done, sort ...

1

The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).

0

Define $f(x) = x/3, g(x) = 2x, h(x) = x+7$ and $D = \mathbb{N}$ for the functions $f,g,h$. I presume that the question is the following: Given $x,y \in \mathbb{N}$ is there a transformation sequence $s_{(n)}:= (f \circ g \circ h) ^{n}$ such that $(f \circ g \circ h) ^{n}(x) = y)$ with the restriction that always $3 | (g\circ h)(f \circ g \circ h) ^{n-1}(x)$ ...

1

I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item". Let's call $t_{max} = max(D[i])$, the end horizon of your problem. Create a vector $A$ of size $t_{max}$, $A_i[t]$ ...

0

An array is the only thing that will get you consistent lookup in constant time. Removal cost: n Insertion cost: n log n Of you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal

1

If $A$ and $B$ are two set of points, the geometric median of $A \cup B$ does not necessarily lie on the line passing between the geometric mean of A and the geometric mean of $B$. In the following example the points of $A$ are red and the one in $B$ is blue. The geometric median of $A$ is the red square. The green line connects the geometric means of $A$ ...

1

Okay, I will attempt to give a new approach. Note that I am not sure to understand all features and issues. Moreover, the most adapted strategy probably depends strongly on data. Assumptions I make the following assumptions, i can eventually adpat my answer if one is wrong. there are $N$ persons to group ($N \approx 1000-5000$) each person $p$ has a time ...

2

"Average < threshold" is equivalent to "Sum < 10 times threshold". Find all subsets of five integers, and sort them in ascending order by their sum. That takes O (N over 5) space and O (N over 5, times log N) time. Let S be the first, second, third subset and so on, as long as the sum of S is less than 5 x threshold. For each S find a subset T ...

2

If you have implemented breadth first search correctly, you should have found that 1889 can be reached. $\quad 2019+7\to 2026$ $\quad 2026+7\to 2033$ $\quad\quad\cdots\quad$ (add 7 repeatedly) $\quad 4238+7\to 4245$ $\quad 4245 \div 3 \to 1415$ $\quad 1415 * 2 \to 2830$ $\quad 2830 * 2 \to 5660$ $\quad 5660 + 7 \to 5667$ $\quad 5667 \div 3 \to 1889$ It ...

4

For constant $p>0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order. In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, ...

2

Your problem has been considered by Braverman and Mossel in their paper Noisy sorting without resampling. The paper has generated quite a lot of follow-up work, some of which might be more practical than the original algorithm suggested by Braverman and Mossel.

1

This formula can more insightfully be written as $$p = \frac{1}{e^{\dfrac{\Delta E}{T}}}$$ where, in the context of SA, $\Delta E$ is the difference between the "energy" (or quality) of two possible solutions and $T$ is the temperature (which is either a constant or a function of the input size). So, the higher the energy difference $\Delta E$, the ...

2

This is a polynomial time algorithm: Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$). Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as: $$\begin{cases} ... 2 This can be modeled as a convex program$$\begin{align} \text{min.} \qquad & ||x-p||_2^2,\\ \text{s.t.} \qquad & Ax\leq b,\\ & x\in\mathbb{R}^3. \end{align} and solved (in reasonable time) by standard solvers. Here's example code in julia using Convex, SCS # generate random problem data m = 5; n = 3 A = randn(m,n); b = randn(m,1); p=randn(3,...

1

You want the algorithm for constructing a Graeco-Latin square, or any of the algorithms described in https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

2

Another solution that doesn't require modifying the algorithm (so you can do it with an off-the-shelf implementation): Have two copies of the graph, one called even the other called odd. The idea is that when the total path-length so far is even/odd, you'll be in the even/odd graphs respectively. Then you only need to consider the start/end nodes on the ...

1

First of all, note that you should use pseudo-code in your question to make it readable by anyone. You cannot treat this problem by just listing possible ends and give them equal probability. Consider this trivial case with no tunnel: %AO* the frog does not have a total 50 % to escape. On first move it has 50 % to go left to exit and 50 % to go right. But ...

0

See the Wikipedia article on the maximum subarray problem for applications to genomic sequence analysis, computer vision, and data mining.

1

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows. Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$. At moment $e$ process $P_i$ have received a confirmation from $P_k$....

Top 50 recent answers are included