Questions tagged [algorithms]
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.
9,271
questions
0
votes
1answer
19 views
Assign few binary variables to make all polynomials identically zero
I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$
for any $i \in [1,50]$. I want to assign few variables so that all $f_i$ will be
identically zero. ...
6
votes
1answer
5k views
What is an optimal algorithm?
I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
0
votes
0answers
21 views
How much faster are out machines (generally) than Arthur C. Clarke's machine in 1953's “The 9 Billion Names of God”?
In Arthur C. Clarke's short story, "The 9 Billion Names of God", two software/hardware engineers are contracted by a monastery to generate 9 billion string permutations from a 13-character ...
1
vote
1answer
42 views
Cashier Scanning Algorithm Problem
I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.
A cashier only has x time to scan a person's goods. The ...
-3
votes
0answers
27 views
parameterized complexity
Given a SAT formula $φ$ where no variable appears negated, decide if there exists a satisfying assignment which sets at most $k$ variables to value 1.
Show that this problem can be solved in roughly $...
1
vote
1answer
34 views
Find the recurrence relation for the following algorithm
The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.
\begin{align}
&\text{SORT}(A[0\dots n-1])\colon\\
&\quad \text{...
0
votes
1answer
48 views
Efficient way to implement periodic events
I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple ...
2
votes
1answer
46 views
Find a list of actions that result in desired state
I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem.
In the system we have a list of actions that a ...
1
vote
2answers
77 views
Proving that a preorder traversal of a rooted tree can be performed in linear time
Definition:
Let $T(V, E)$ be a rooted tree with root $r$.
If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$.
If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
2answers
95 views
Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$
I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$
...
1
vote
0answers
32 views
Group same objects using multiple stacks
I am trying to write an algorithm to solve the following problem.
Let's say we have $n$ (6<=n<=14) buckets each with capacity 4. There would be exactly $n-2$ type of objects. The initial state ...
1
vote
1answer
24 views
Way to solve 5-dimentional Linear assignment problem [closed]
I faced a problem that looks very hard, the problem is this:
We have 5 people putting dots on a whiteboard, each person uses colored dots with a different color (there are 5 colors, 1 for each person)...
0
votes
1answer
45 views
Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?
I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations.
What I'm trying to calculate:
I have number of items. Lets call items a1, ...
-3
votes
1answer
19 views
How to simulate two counters using one (FIFO) queue?
How to simulate two counters using one (FIFO) queue? (In terms of algorithms, unary stack.)
1
vote
0answers
14 views
Better version of heavy-light decomposition: always draw path to largest subtree
Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ).
The problem: given any tree of size N, find a way to split it into ...
0
votes
0answers
9 views
How to implement the synchronous part of the paper “Concurrent Cycle Collection in Reference Counted Systems”
I have been looking at how to implement this paper, which I've outlined the main algorithm below. This paper is about how to implement reference counting in a way that handles cycles.
What I'm ...
1
vote
1answer
46 views
Issue triangulating a font glyph for a specific scenario
I am trying to triangulate TTF glyphs for drawing in opengl. The below image shows an example glyph (Taken fron FontForge application). The X represent control points of a bezier spline, circular and ...
1
vote
0answers
13 views
Measure divergence in Particle Swarm Optimization
I'd like to monitor divergence/diversity in my swarm during the particle swarm optimization algorithm to measure when the swarm search space is converging.
This would be used as one metric to be ...
1
vote
1answer
53 views
Perfect matching problem
Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*...
2
votes
0answers
23 views
Optimal Item Locations given Traversal Paths
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a ...
2
votes
2answers
112 views
How to find an array of probabilities that give equal products
I'm trying to figure out if there is an algorithm which can solve the following:
Given an array of randomly generated values, for example: $$[54.6, 1.96, 5.0, 31.31]$$
Find an array of equal length, ...
1
vote
1answer
86 views
Runtime of weighted interval scheduling dynamic programming algorithm
Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:
...
2
votes
3answers
15k views
Brute force method to solve the 0-1 knapsack problem
I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:
If the brute force ...
0
votes
0answers
22 views
How to known which algorithm is the best for what situation, when sorting numbers?
Is there some kind of "universal list" of performance of different algorithms in different situations?
I have different databases that save user input (numbers). However some of these sets ...
4
votes
1answer
48 views
Las Vegas algorithm for finding 00000 in bit string
Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
28
votes
7answers
11k views
Generating Combinations from a set of pairs without repetition of elements
I have a set of pairs. Each pair is of the form (x,y) such that x,y belong to integers from the range [0,n).
So, if the n is 4, then I have the following pairs:
<...
0
votes
1answer
64 views
Disjoint Set Connected Components With Weighted Graph
I have been trying to solve this HackerRank problem (link).
The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
2
votes
1answer
93 views
Mutli-Path Collision Avoidance
I need an algorithm which can do the following:
Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
8
votes
4answers
3k views
Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop
The Floyd-Warshall algorithm is defined as follows:
...
0
votes
0answers
29 views
Minimum cost bin assignment
I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
1
vote
1answer
27 views
Number of substrings with exactly k distinct characters
Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
-1
votes
0answers
26 views
W(n) = W(n/2) + W(n/4) + 0.999n
how can you solve W(n) = W(n/2) + W(n/4) + 0.999n using the brick method and get the asymptotic bound? I have no idea where to start.
0
votes
2answers
75 views
Average case running time of quick sort
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
1
vote
4answers
105 views
If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?
Suppose there is a polynomial time reduction from problem $A$ to $B$.
Why is the following false?
If $B$ is NP-hard then $A$ is NP-hard.
Can some explain this intuitively?
0
votes
2answers
50 views
Given a sorted array with n integers, how to find the element that has no duplicates?
I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-...
1
vote
0answers
32 views
Why doesn't the assignment of processors contribute to runtime in a PRAM algorithm?
The following algorithm for computing the number of nodes in a linked list appears in this thesis on common algorithms in the PRAM model for parallel computation.
The author then argues that this is ...
0
votes
1answer
26 views
How to work out the odd case?
I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to ...
1
vote
3answers
41 views
Is $n \log n$ in $O(n^{1.46-\varepsilon})$?
I am trying to figure out the solution of the recurrence relation
$$T(n) = 5T(n/3) + n \log n$$ using the Master Method.
I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
3
votes
0answers
36 views
Hardness of an instance of a problem independent of algorithms?
The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
-2
votes
0answers
80 views
Why do delta x is multiplied in bresenhem line drawing algorithm
In derivation of bresenhem line generation algorithm( https://getsetcg.blogspot.com/2018/10/bresenham-line-drawing-derivation.html?m=1 ) why do they multiplied delta x or in some they use dx to ...
-2
votes
0answers
67 views
Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case runningtime of O(nlogn)
Suppose we have an array A[1 :n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank (A[i]), as the number of elements in A that are strictly smaller than A[i] ...
0
votes
2answers
18 views
Sorting an interval
Given that array has $k$ elements (all distributed uniformly).
Its length is exactly $3$ somewhere in $[0, k)$.
For example, if $k=100$ then, we have $100$ numbers and they can be in $[10,13)$, but ...
3
votes
1answer
56 views
Justifying a claim in the proof of the master theorem
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.
My argument is as follows:
Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
-1
votes
0answers
32 views
Assignment of Nodes to Multiple Queues
You are given $n$ customers at $n$ nodes and each node is at a variable distance away from all queues. Also each customer is processed in a constant amount of time $c$ when it is in a queue. Assuming ...
23
votes
1answer
967 views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
1
vote
0answers
168 views
Total running time expressed in O notation of a word ladder program all words same length
I am trying to figure out a big O expression for the running time given $V,E,F$ for a word ladder or word chain program that I have written in Java. I am using undirected graphs with BFS.
What is ...
1
vote
1answer
68 views
In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?
See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
0
votes
0answers
68 views
$O(n)$ algorithm to find a sequence of 3 or n tennis players with ratings in decreasing/increasing order
This problem is a follow up from this.
At a certain (unrealistic) event, we have infinitely many tennis players lined up who are conveniently numbered $(P_1,P_2, \cdots)$. Each player has a certain ...
1
vote
1answer
28 views
Determine saving moves for a checked king
In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and ...
0
votes
0answers
14 views
How to set up a recurrence relation to analyze number of execution of the basic operation of this algorithm? [duplicate]
This an algorithm to count inversions in an array, this is a divide and conquer algorithm, I ...