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.
11,333
questions
0
votes
1
answer
37
views
Find combination of elements, one element from each list, whose average is the closest to a target number
Problem:
There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1.
The lists have equal length.
There is a target number T.
Find what is the combination of elements, one element from each ...
- 1
2
votes
2
answers
123
views
What are quines (layman friendly)?
I was going through the Wikipedia page on Quines and did not understand this paragraph -
A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
- 123
0
votes
0
answers
14
views
How to choose cells from a table to maximize their sum, with selection constraints?
I have a table of fixed positive integer values of anything up to several dozen. There are six columns and several hundred rows. I must choose exactly two values from each column, and zero or one ...
- 101
0
votes
1
answer
27
views
Is minimum interval hitting problem NP-HARD?
Consider this problem:
We want to mark some integer numbers such that we mark the minimum number of the numbers and satisfy some constraints. Each constraint wants that at least $k$ numbers in ...
0
votes
0
answers
8
views
The Multi-Room Muddy Forehead Puzzle with Varied Color Perception
Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
- 129
0
votes
3
answers
38
views
Which algorithms could be suitable for solving my disjunctive programming problem?
Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
0
votes
0
answers
33
views
Given a population, find the boolean algebra expressions that most closely evaluate to that population
TL;DR
I have some ideas but am curious to know if there are existing proofs, research, etc. in this area that I can use to guide my algorithm development.
Problem summary
We have a population where ...
- 101
0
votes
2
answers
123
views
Minimum number of comparisons to find $2$nd smallest element
Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$
comparisons in the worst case. (Hint: Also find the smallest element.) [1]
I tried but I have no idea how to, e....
- 129
0
votes
0
answers
25
views
ir - Using document-term [Boolean] incidence matrix for answering a query
The book "Introduction to Information Retrieval" talks about term-document incidence matrix for retrieving documents that contain/not-contain certain tokens drawn from a query. This ...
- 101
0
votes
0
answers
41
views
finding the length of the GCD of two strings
Let's say you have two strings: a and b with GCD c. Why is it that ...
- 171
0
votes
1
answer
54
views
Optimizing findMissingNumber algorithm to O(N)
This problem is from Cracking the Code Interview:
An array A contains all the integers from Oto n, except for one number
which is missing. In this problem, we cannot access an entire integer
in A ...
- 1
3
votes
2
answers
121
views
How to identify Dominant terms in big-O notation and understand Time Complexity of an algorithm?
I understand that Time Complexity is the measure of how an algorithm scales with respect to the input size.
Let us say an algorithm is having a runtime of O($3^n$) + O($n^{20}$)
In order to identify ...
0
votes
1
answer
49
views
Algorithm to generate all N-size variations of natural numbers
For a size N>=1 (an input variable) I need an algorithm to generate all variations (no duplicates allowed) of natural numbers greater than zero.
For N=1, this is trivial:
...
- 155
1
vote
1
answer
61
views
Is variable a constant or a parameter
I am working on the $[1,j]$-dominating set problem defined in this paper. In section 4, they study the problem complexity on degenerate graphs and prove that the problem is W[1]-hard for the parameter ...
- 162
0
votes
0
answers
22
views
Maximum Subset Sum with Pairwise Constraints
(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.)
Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
- 11
0
votes
0
answers
20
views
Subtrees of decision tree for comparison sort are recurrences?
Consider sorting on $n$ distinct elements, where all $n!$ permutations are possible. I think a decision tree for comparison sort can can be uniquely characterized as $T(a,n!)$ where $a$ is the ...
- 129
2
votes
2
answers
82
views
Role of a variable in problem definition in time complexity
I am a research scholar in the field of algorithms and complexity theory. The problem that I am currently working is the $[1,j]$-domination problem. Given a graph $G = (V, E)$, with $n = |V|$, the ...
- 162
1
vote
1
answer
45
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size ...
- 411
0
votes
1
answer
195
views
Proving the correctness of a greedy algorithm for the Circular Scheduling Problem
Consider the following variation on the Interval Scheduling Problem
You have a processor that can operate 24 hours a day, every day. People
submit requests to run daily jobs on the processor. Each ...
0
votes
2
answers
113
views
Is there an algorithm to remap every Int32?
I'm making a web application that can generate unique unsigned Int32 post IDs for posts. Normally I would just make it auto-increment from 0.
But I don't want the ...
- 103
0
votes
0
answers
16
views
Algorithm for computing the vertices of a polytope defined as the intersection of half spaces
There's a very similarly sounding question with an answer already, but my setup is very, very different.
You are given $k$ half spaces in dimension $d$, defined by a point and a direction. You want to ...
- 331
-2
votes
1
answer
24
views
Is this considered a vertex cover?
I'm unsure if this satisfies the definition of vertex cover, the graph is unweighted and undirected:
if not, an explanation would be super enlighting.
- 315
0
votes
0
answers
39
views
Algorithm for leader election in synchronous ring with a known network size $n$ with phases of length $\frac{n}{m}$
Consider the following leader election algorithm election of a synchronous ring with a known network size $n$ (simultaneous wakeup and uni-directional communication):
The leader is the node with the ...
- 315
0
votes
1
answer
37
views
Justify that total running time for the addition algorithm is of the form $c_0+c_1n$
In my reference Page 22, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it says that
given $x$ and $y$ are two numbers of $n$ bits long, then the sum of $x$ and $y$ ...
- 139
0
votes
0
answers
79
views
Best time to buy and sell stocks with multiple buy transactions are allowed and can sell all shares at once
I've been trying to solve a variation of this problem https://stackoverflow.com/questions/62389658/best-time-to-buy-and-sell-stocks-when-allowing-consecutive-buys-or-sells
You are given an input array ...
- 37
3
votes
1
answer
91
views
Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
- 31
0
votes
1
answer
33
views
Help in defining value function for 0/1 knapsack
I would like to set up some type of automation/suggestion tool for buying items on a limited spending budget. To try to somewhat formalise the problem, one could suggest to reduce this to a 0/1 ...
1
vote
0
answers
62
views
Proving the algorithm gives an optimal solution
Very often I see solutions to optimization problems that describe an algorithm but do not prove why the algorithm leads to an optimal answer. For example, the following problem showed up in an online ...
- 111
2
votes
1
answer
51
views
Find directed spanning tree of unweighted directed graph in $O(|V| + |E|)$
A directed tree (also called an arborescence) of $G$ is a directed subgraph of $G$ in which there exists a vertex $v$ such that there is a unique path from $v$ to every other vertex in the graph.
...
- 237
1
vote
2
answers
50
views
Estimating the number of elements shared in two sets using a random sample
Suppose we have two sets $A$ and $B$. The sets share some number of elements between them, but within each set, any item appears at most once. We want to determine how many elements they share in ...
- 837
-1
votes
1
answer
113
views
Design an algorithm to predict words based on a skeleton from a given dictionary
I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words.
I have built and providing here with a basic, working algorithm. This algorithm will ...
- 99
2
votes
1
answer
124
views
Fast $k$-clique checking algorithm?
I have a problem where part of it requires answering the question: does graph $G=(V,E)$ contain a clique of size at least $k$?
Obviously, answering this question is a NP-Complete problem. I am no ...
- 121
0
votes
1
answer
42
views
Can a linear programming method be used to solve systems of inequalities with OR (disparate) compound inequalities?
I recently discovered linear programming and it seemed perfect for a CS problem I wanted to solve a few months ago. This task involved solving a large quantity of inequalities at once.
For example, ...
0
votes
1
answer
60
views
How to allocate memory for prime numbers
I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I ...
- 103
2
votes
1
answer
69
views
Collinear convex hull
Is there an algorithm where I provide a list of non-overlapping squares, for example:
...
- 23
0
votes
1
answer
41
views
Alghorithm to calculate x, y positions of a grid with the following numbers (details inside)
I have a 2D array grid where each cell has a number in it, i would need a alghorithm that returns me the value of that cell depending on the X, Y position (0, 0 is bottom left)
This is the grid in ...
- 101
4
votes
2
answers
77
views
Looking for efficient algorithm to pick out a unique equivalence class representative for 2D arrays with lots of symmetries
Given 2D arrays (number of rows between 0 and 10, number of columns between 0 and 10, elements are integers between 0 and 31)
Two arrays $A,B$ are equivalent $A\sim B$ if $A$ can be transformed into $...
- 43
0
votes
0
answers
27
views
Minimum set cover problem and dual, the maximum set packing
Just like in This thread that was posted here before, I came upon the same issue where I do not understand how are the relaxed maximum set packing problem and the minimum set cover problem are dual to ...
- 1
0
votes
0
answers
58
views
Efficient way of exploiting many symmetries
I have a problem domain that has several kinds of symmetries. I will try to keep this as general as possible. Given an array of strings:
["4533", "1234", ...]
The two symmetries ...
- 43
0
votes
0
answers
40
views
Is my mathematical representation of search in binary search tree correct?
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals <...
- 113
0
votes
1
answer
91
views
Harder variation of light bulb problem (solvable in O(n log n)?)
Problem originally from: https://train.nzoi.org.nz/problems/1311
Every light-bulb is initially off, and O(N^2) solutions are too slow.
Emma is a massive nuisance at school by always meddling around ...
- 26
4
votes
2
answers
87
views
Finding a vector of maximum Hamming distance from a subspace of $(\mathbb{Z}/2\mathbb{Z})^n$
Let $W$ be a linear subspace of the vector space $V = (\mathbb{Z}/2\mathbb{Z})^n$. Let $k = \dim(W)$. For $v \in V$, define the distance from $v$ to $W$ to be $d(v,W):=\min_{w\in W} d(v,w)$ where $d(...
- 141
1
vote
0
answers
21
views
Algorithm for checking whether a set of hyperplanes covers $\mathbb{Z}_r^n$
In what follows, $r \in \mathbb{N}$ is not necessarily prime. $\mathbb{Z}_r$ is shorthand for $\mathbb{Z}/r\mathbb{Z}$.
Given a set of $h$ hyperplanes $A \vec x = b \mod r$, we can check whether the ...
- 378
1
vote
1
answer
93
views
Proof of correctness of some optimization of Heap's algorithm for producing permutations
Good day. Some time ago I found a page on (en.) wikipedia about Heap's algorithm for permutations. Here it is.
Original algorithm can be written as next (copy from (en.) wikipedia):
...
- 11
3
votes
1
answer
132
views
Number of "one neighbourhood" search trees in a graph
Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including ...
- 73
1
vote
1
answer
100
views
High-multiplicity maximum-weight matching
There are $n$ people and $m$ jobs. We would like to assign at most one job to each person.
For each person,job pair, there is a positive value determining the fitness of this person to that job. The ...
- 5,720
1
vote
0
answers
13
views
Correlation between branchless algorithm length (Assembly) and its latency
I have recently reviewed the new article by DeepMind (Google) in Nature named "Faster sorting algorithms discovered using deep reinforcement learning". They claim that branchless algorithms, ...
- 111
1
vote
1
answer
73
views
How can this problem be solved in $O(n^{3/2}log(n))$ time?
I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible?
Let $D[1 .. n]$ be an array of digits, each ...
- 13
-1
votes
1
answer
69
views
Verify $n\log n=\Theta(10n\log10n)$
How do I Verify that $n\log n=\Theta(10n\log10n)$
I think I need to prove that there exists $c_1,c_2>0$ such that $c_1.g(n)\le f(n)\le c_2.g(n)$
Step 1
$$
\log n\le \log 10n\implies f(n)=n\log n\...
- 139
1
vote
1
answer
54
views
Understanding the Internal Stack Frames in a Recursive Function Call
I'm trying to understand how the system's call stack works internally when a
recursive function is called. Specifically, I'm looking at a function that
computes the maximum depth of a binary tree ...
- 113