The 2024 Developer Survey results are live! See the results

# Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

1,850 questions
Filter by
Sorted by
Tagged with
84 views

### Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?

I'd like to know if the following generalization of min-cost perfect matching is NP-hard. As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}_{\geq 0}$. In addition, ...
• 639
55 views

### What is the proper name for a tree whose edges hold more than one symbols?

To supplement the title, edges from one node may hold strings with the same prefix. For example, a node may have two edges, apple1 and ...
• 113
43 views

### Can an m * n matrix be given Young Tableau property in O(1) space?

If it can be done with heaps why not Young Tableaux? [1] I know that the analogy is too simplistic but for learning sake, let us consider it. The only limitation I noticed is that while heaps exhibit ...
109 views

### Time complexity of square root floor

Given a square number in $n$ bits can we compute its square root in $O(n)$ time? In general can we compute $\lfloor\sqrt{a}\rfloor$ in $O(\log a)$ time?
• 13.1k
127 views

### Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

It is known that many-tape Turing machines can be simulated by a one tape Turing machine with extra runtime costs. Furthermore, a single-tape Turing machine with a larger alphabet can be simulated by ...
48 views

### Big O of evaluating expression under RAM model

I have a CS theory problem and want to figure out the Big O of my algorithm. Let n be the input size. In the algorithm, I pre-process up to n expressions and these expressions grow in length (i.e. ...
261 views

### Is parity of GI easy?

Given graphs $G,H$ let $N(G,H)$ be the number of isomorphisms between them. Is there polynomial time algorithm to compute $N(G,H)\bmod 2^t$ for every fixed $t\geq1$?
• 13.1k
63 views

### Quickest known integer relation algorithm in the case of signs

Let $x_1,\cdots,x_n,k$ be integers such that $|k|\le\sum_{i=1}^n|x_i|$. What is the quickest known algorithm to determine $w_i\in\{-1,0,1\}$ such that $k=\sum_{i=1}^nw_ix_i$ where they exist? What is ...
1 vote
114 views

### Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
1 vote
55 views

3k views

### What are examples of recent relatively simple 'toolbox algorithms'?

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such ...
44 views

### Effective algorithms for finite lattices of (higher-order) monotonous functions?

I am looking for references on effective algorithms on finite lattices or posets, and in particular on lattices of monotonous functions between two lattices, with higher-order structure -- monotonous ...
• 2,040
363 views

### Condition Number dependent algorithms for matrix operations

Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where \$\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
• 958
95 views

### How is memory being used by an algorithm, to define its space complexity? [closed]

In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...