New answers tagged algorithms
2
votes
Why is map sort ideology less common?
Instantly put everything in a map and get it back as a $O(1)$ operation.
HashMap operations do run in $O(1)$, but it cannot be used for sorting.
TreeMap can be used for sorting, but its operations ...
- 716
4
votes
Why is map sort ideology less common?
Apples vs Oranges
Quicksort is a sorting algorithm, whereas a map/dictionary/hashtable/hashmap is a container data structure. Use cases of both are widely apart.
As far as your argument is concerned, ...
- 1,074
4
votes
Why is map sort ideology less common?
Inserting $n$ items into a sorted map takes a total of $O(n \log n)$ time, so the running time is not faster than sorting the $n$ items.
D.W.♦
- 166k
1
vote
Closest point on a convex hull in log(n)
Let's at first find a polygon edge, closest to the external (relative to the polygon) query point q. Then, if we really need, we will be able to choose one of the ...
- 3,118
0
votes
Accepted
Ways to compact arrays
Your problem is just compression. The array is irrelevant; you have some data (a sequence of bytes), and you want to compress it. The general approaches are to either use a general-purpose ...
D.W.♦
- 166k
0
votes
build a model with fuzzy prior knowledge and train it
Pragmatically, the most realistic path is probably to build a model to predict y from x1,x2,x3, without trying to make any special use of your knowledge about the correlation structure. Most likely ...
D.W.♦
- 166k
3
votes
Can you determine if a matrix can be made symmetric in poly time?
(Not a computer scientist here) but here is an approach to eliminate many matrices. Starting with the bipartite graph $G$ that you described, let us define by induction a sequence of more and more ...
- 204
1
vote
Do all recursive problems have optimal substructure?
All problems with an optimal substructure can be solved recursively, but not all problems that can be solved with recursion have an optimal substructure. I think you understand the first part of that ...
- 111
0
votes
Showing Dijkstra's algorithm works for bridge negative edges
The standard proof should work.
By induction on the size of $S$, the vertices that have been popped from the priority queue. Base case is the same, induction hypothesis is the same. Induction step is ...
- 17.1k
2
votes
Max number of walks to a goal vertex, each with different starting vertex
You are right that maximum flow problem can be helpful here.
Converting undirected graph into directed is pretty simple for network flow. Just replace every edge $\{\,u, v\,\}$ by two arcs $(u, v)$ ...
- 562
1
vote
Closest point on a convex hull in log(n)
Start of an answer:
Given $P_{new}$ outside
a regular $(2n+1)$gon (simple case):
Pick an edge $e$ and its vertices $v_a$ and $v_b$.
If their distances to $P_{new}$ are equal,
either both are closest ...
6
votes
Accepted
Given $4$-coloring decide $3$-colorability in $P$?
No. 3-coloring is known to be NP-complete for planar graphs. It is known that every planar graph is 4-colorable, and moreover a 4-coloring can be computed in polynomial time. Therefore, your ...
D.W.♦
- 166k
2
votes
Accepted
NP reducibility proof steps
I think you've got things mixed up. Usually, we show circuit-SAT is NP complete directly, by reducing an arbitrary NP problem to it (this is the Cook-Levin theorem). Then, what this tree presumably ...
- 308
0
votes
Analysis of randomized algorithm by number of "failing" inputs
If there are inputs for which your algorithm always gives wrong answer, then your algorithm is not correct unless you suppose randomness of input.
If for every input there is at least some non-zero ...
- 562
0
votes
What is the most efficient, optimal, solution for the multi-way number partitioning problem?
The problem is NP-hard, so you shouldn't expect any general algorithm that is always optimal, always works, and is efficient.
I suspect a pragmatic approach is to use an integer linear programming (...
D.W.♦
- 166k
0
votes
Efficient Algorithm to Count Permutations of Boss Fights with Divisibility Constraints in an RPG Game
State Definition: Let $dp[i][s][k]$ be the number of ways to select elements from the first $i$ items such that:
The sum modulo 4 is $s$ (i.e., $s = (\sum_{j=1}^{i} a_j b_j) \mod 4$)
The number of ...
- 101
0
votes
Set of K elements with minimum cost and GCD=1
State Definition:
We use dp[c][gcd] represents the minimal total B[i] to achieve GCD gcd ...
- 101
1
vote
Accepted
I need help in designing a genetic algorithm for matchmaking in ecommerce
What I've done in the past is to represent a candidate solution as an array of integers, but explicitly not a permutation. Let's say we normally have more buyers (Nb) than sellers (Ns). I'd encode the ...
- 1,086
0
votes
Selecting two subsets of points, minimizing internal distance and maximizing external distance
Use Greedy optimization
start with k random points per class
minimize internal distance , by iterative swapping points to reduce total within subset distance
maxmize enternal distance by choosing ...
- 26
1
vote
A data structure for range minimum queries
With SQRT decomposition you can decrease the value of an element in constant time, and update the block of the element in constant time as well.
Query time is $O(\sqrt n)$.
For more information, ...
- 17.1k
0
votes
Approximation Algorithm for Feedback Arc Set on a Sparse Graph
According to the article FPT-approximation for FPT Problems
Theorem 1.1. Directed Feedback Vertex Set, Subset Directed Feedback Vertex Set, Directed Odd Cycle Transversal (DOCT), and Multicut have $2^...
- 562
3
votes
Set of K elements with minimum cost and GCD=1
This is NP-hard. We will prove this by reduction from the set cover problem.
Consider a set $U$, and a set $S$ of subsets of $U$. The set cover problem asks for the smallest subset of $S$ whose union ...
- 342
2
votes
Accepted
Find a minimal (irregular) boundary over a grid of colored cells
Either I do not understand your problem, or the problem is solved by using a BFS/DFS from the red cells. There must be a unique solution if it exists, since if two areas with crossing boundaries ...
- 17.1k
6
votes
Set of K elements with minimum cost and GCD=1
You can do this with dynamic programming. Let $S$ be the input set, and let $N=\max S$. We define the table $T\in\mathbb{N}^N$ where
$$
T[w] = \min_{\substack{X\subseteq S\\ \operatorname{gcd}(A[X])=w}...
- 4,662
Top 50 recent answers are included