Gassa
  • Member for 7 years, 10 months
  • Last seen this week
Algorithm: Given a large semiprime number N, find the smallest value of $A$ such that $N + A^2$ is a square
6 votes

In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$. Then we have $N + B^2 = A^2$. Thus $N = A^2 - B^2 = (A - B) \cdot (A + B)$. What's left is to look at the pairs of divisors of $N$. If $N =...

View answer
Cover k edges to minimize the length of the longest uncovered path in a tree
Accepted answer
6 votes

(This answer expands on Albert Hendriks' approach from the comments.) First idea: let us turn the problem around. As stated, we fix the number of covered edges, $k$, and minimize the maximum length ...

View answer
Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))
Accepted answer
4 votes

The basic idea, when we don't know $k$, is to ask for elements with an exponentially growing index. The most natural here is some use of powers of two. For example, we can ask for elements with ...

View answer
Does the space complexity of a recursive algorithm depend on the total no of recursive calls?
Accepted answer
3 votes

Yes, that's right. The statement "space complexity is $f(n)$" means that, if we had only $f(n)$ memory and no more, it would still be possible to run the algorithm. As an example, say we are ...

View answer
What is the complexity of comparing point sequences?
3 votes

Here's a start: an upper bound is $O(n^3)$. Note that we need either $0$ or $1$ moves: any two moves could be expressed as one. Furthermore, this one move is commutative with all other operations: it ...

View answer
Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori
Accepted answer
3 votes

This sounds as follows. The answer is that the optimal number of children in a tree is $e$. What was "optimal" in the question? One such question is as follows. Let us construct a tree of $N$ nodes....

View answer
Complexity of Longest Palindromic Subsequence Algorithm
Accepted answer
3 votes

The dynamic programming approach is indeed O(n^2). However, the recursive solution is exponential in n: any time two characters don't match, a subproblem of size k is converted into 2 subproblems of ...

View answer
Given n numbers How to find out a set of numbers whose sum equal to a certain given number
2 votes

One possible solution is based on knapsack. Consider the list elements $a_1$, $a_2$, $\ldots$, $a_n$ in any fixed order. Calculate the following boolean function: $f (k, t)$ is true if it is possible ...

View answer
Which algorithm can calculate an optimal allocation of students to projects?
Accepted answer
2 votes

This sounds much like a problem for minimum-cost maximum flow. Construct a network. The nodes will be the students, the projects, and the added source and sink. Add an edge with capacity $1$ and ...

View answer
Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?
Accepted answer
2 votes

You are right: if we have to find a particular place and then insert a value there (for example, insert an element in a sorted list), it is $O(n)$ for a linked list. However, the Wikipedia article ...

View answer
Minimise given size using dynamic programming
Accepted answer
2 votes

A dynamic programming approach would be: $f (p, k)$ is the minimum size when we considered prefix $\{x_1, x_2, \ldots, x_p\}$, and selected exactly $k$ items from it, the last one being $x_p$. We add ...

View answer
How to restore diagonal-symmetric matrix that has been shuffled?
1 votes

First, note that the matrix can only be restored up to a permutation of the diagonal. To illustrate on your example, when we swap two bottom rows and two left columns, the resulting matrix is also ...

View answer
Egg dropping puzzle - clarification of problem statement
Accepted answer
1 votes

Imagine this as a game of two players: the experimenter vs. nature. The egg breaking limit is not chosen in advance. Instead, the players together form statements about its possible values, all the ...

View answer
If it's Possible to Create the If-Statement from Simpler Primitives
Accepted answer
1 votes

This is perhaps most clear at the assembly level. There is an instruction pointer, which normally moves to the next instruction after executing the current one. Any instruction that interferes with ...

View answer
minimum and maximum nodes of MultiWay tree of height h
1 votes

This looks correct. Note that the sum of the geometric series can be expressed more concisely: $$\sum\limits_{i = 0}^{h} M^{i} = \frac{M^{h + 1} - 1}{M - 1}$$

View answer
How to find MST for each source
Accepted answer
1 votes

Here is a slight modification of Kruskal's algorithm which can solve this. Sort all edges by non-decreasing weight. Maintain a disjoint set union to track which vertices are connected, as usual. ...

View answer
Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted
Accepted answer
0 votes

The minimum number of comparisons to tell whether an $n$-element array is sorted is indeed $n - 1$. However, we don't have to sort the array to arrive to a conclusion. Here is how to check an array $...

View answer