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,014
questions
0
votes
1answer
53 views
How can I prove the correctness of this exponentiation algorithm using induction?
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
...
0
votes
0answers
4 views
How can I create an algorithm in pseudo-code generating a sequence of numbers in such an order that they only are different at one position by 1?
Let's say we want to create sequences of the numbers {0,1,2} which are all at length n
What I want to create is an algorithm which generates (and outputs) such sequences that they are only different ...
1
vote
1answer
19 views
Inductive proof for Euclid's algorithm
I'm studying The Algorithm Design Manual and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the ...
0
votes
0answers
30 views
How does AlphaGo perform when increasing the size of the board?
I recently watched AlphaGo, a documentary on the recent defeat by the best human player of Go by a computer, AlphaGo.
The commentary the beginning points out this was ten years ahead of schedule (...
-1
votes
0answers
6 views
Two-Sum - Many Sums Algorithm Design Refactor
🧩 How to optimally convert a two-sum item solution to have as many items as possible based on a given capacity?
🚀 Original Two-Sum
Two-Sum: Determine whether there are two items whose length will ...
2
votes
1answer
15 views
What is the best algorithm to find the optimal path in reducing company's real-estate footprint?
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in ...
0
votes
0answers
9 views
Two-Sum - Range Allowance Algorithm Design
🧩 How to optimally find a two-sum solution within a range plus/minus the given capacity?
🚀 Original Two-Sum
Two-Sum: Determine whether there are two items whose length will equal the total length ...
0
votes
0answers
50 views
Two-Sum - Pre-sort Optimization Algorithm Design
🧩 Is it possible to optimize a two-sum solution by receiving a pre-sorted input either in ascending or descending order?
🚀 Original Two-Sum
Two-Sum: Determine whether there are two items whose ...
2
votes
0answers
12 views
Hungarian method: seemingly different algorithms from different sources?
When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and ...
0
votes
0answers
54 views
Distribution Sort - Split elements
I have read from the following references about Distribution Sort:
https://users.cs.duke.edu/~reif/courses/alglectures/vitter.papers/Vit.IO_survey.pdf (5.1. Sorting by Distribution)
https://en....
0
votes
0answers
19 views
Analysis of updating vertex and one example?
I see the following image on google:
And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
0
votes
1answer
613 views
Time complexity of quicksort for arrays in increasing or descreasing order
Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.
Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
-5
votes
0answers
40 views
Solve this problem without code ( Move the block : slide puzzle) [closed]
Consider the game Move the Block (gameplay
https://www.youtube.com/watch?v=6d0NcUougD4). Move the Block : Slide Puzzle is a simple
game whose goal is sliding block puzzle game. The game instructions ...
-3
votes
0answers
51 views
Consider the game move the block slide puzzle [closed]
Consider the game Move the Block (gameplay
https://www.youtube.com/watch?v=6d0NcUougD4). Move the Block : Slide Puzzle is a simple
game whose goal is sliding block puzzle game. The game instructions ...
1
vote
1answer
26 views
Average of all sums of subarrays
I ran into a very hard question.
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding ...
0
votes
1answer
41 views
1-sparse recovery algorithm
In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)?
Algorithm:
Keep track of
$$
\...
3
votes
2answers
1k views
Technique for converting recursive DP to iterative DP
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).
But, I'm unable to convert my recursive code to <...
0
votes
0answers
22 views
How does secondary clustering occur in hashing?
One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear ...
1
vote
0answers
64 views
Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming
If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \...
0
votes
1answer
15 views
Choosing the right function
I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining).
What is a good hasing function that guarantees a good ...
0
votes
0answers
21 views
Algorithm for finding shortest set of paths through a weighted DAG (?)
Short version
What algoithm can find an optimal (or near optimal) solution to the following problem?
Given the following:
a weighted DAG, with one start node (only has outgoing edges) and one end ...
1
vote
1answer
53 views
Algorithm to check Gibbs' Phase Rule
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.
I have ...
1
vote
1answer
16 views
Deterministic algorithms for computational distance between distributions
Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms ...
0
votes
0answers
21 views
Evolution strategies for TSP
I'm trying to figure out how evolution strategies would work for the traveling salesman problem. I've done this with the genetic algorithm already, but am curious about how this would be done using ES....
-3
votes
0answers
37 views
Design a algorithm of graph
Given an undirected graph ${G = (V;E)}$. Three different markers are initially placed at vertices ${s1,
s2,s3}$ respectively. Each round, you may pick a pair of adjacent vertices ${u,v}$ and either ...
0
votes
1answer
26 views
Ensure a vertex has the highest flow in max-flow algorithm
Let's suppose we have a supplier, sorting facilities, shipping companies and
a target warehouse.
We produce n packages of the product, and each goes to a different sorting facility (so every facility ...
1
vote
1answer
48 views
Optimal algorithm to distinguish given black box access
This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total ...
-1
votes
1answer
28 views
Time complexity of a machine which combines Insertion Sort and Quicksort
Given a machine that sorts an array of length $n$ with the following algorithm:
Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort)
Select the median of the whole ...
1
vote
1answer
26 views
Inductive proof for the Bubblesort algorithm
I'm studying Algorithms and Data Structures from The Algorithm Design Manual and I'm having a hard time going through the exercises.
Specifically, the proofs are a bit hard and not really explained in ...
1
vote
0answers
13 views
Strong orientation graph algorithm with Robbins' theorem
I've been asked a question that goes something like this:
Using depth-first search and Robbins' theorem, design and analyze an efficient algorithm to construct a strong orientation of a given ...
-4
votes
0answers
13 views
Max-Flow Problems [closed]
Given the network below, we can formulate the maximum flow problem as a linear program. The general formulation is below:
(a) Reduce the number of constraints in the general formation above by ...
0
votes
0answers
33 views
External Sorting - Calculate passes with different number of disks
Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort)
a) If we have 1 disk find minimum ...
1
vote
0answers
23 views
Does the existence of a matroid structure imply that the greedy algorithm is optimal?
I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The ...
0
votes
0answers
17 views
Why is KMP preprocessing O(N)?
My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
1
vote
1answer
22 views
splitting of people betwen groups with group prioritiy list per person
Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most ...
1
vote
1answer
100 views
Generating project network graph
I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.
Informal description:
Every activity is represented as edge of directed ...
-1
votes
0answers
9 views
How can I simply sum up the values in the third column using numpy in a table? [closed]
box ID fruit name count sold price per fruit ($)
53686 kiwi 3 0.5
57181 strawberry 101 0.2
25274 apple 0 0.8
48800 orange 35 0.6
...
5
votes
2answers
815 views
Exact definition of average time complexity?
Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least.
Here is a definition that I feel comfortable with:
Consider ...
4
votes
2answers
188 views
Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?
Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription.
The question:
Given an undirected tree (tree is not disjoint), ...
0
votes
1answer
31 views
oone exmple in hash topics?
Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
4
votes
0answers
73 views
Finding the Hamiltonian cycle that uses the least amount of straight lines
How can i find the Hamiltonian cycle on an nxn grid that uses the least amount of stright lines (curves left/right as much as possible)?
Here's an example we have devised for 8x8:
Here is an example ...
1
vote
1answer
32 views
How can I make the variance of a multiple sum of set of fixed number of variables minimum?
Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds....
2
votes
1answer
295 views
What is the best solving algorithm for a game with stacks?
Game Explanation: Suppose there is a game with cards that have numbers from 1 to n. Each card has a different number so there are not two cards with the same number. The deck is scrambled. We chose ...
1
vote
1answer
24 views
Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints
I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...
1
vote
1answer
117 views
Finding Conflict algorithm doubt
Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time.
I have to find an event that conflict with maximum number of other events.
Conflicts means interval ...
-1
votes
0answers
12 views
3
votes
2answers
63 views
Right most set bit O(log N)
I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used.
...
1
vote
1answer
41 views
Minimum sum of squared Euclidean distance between two arrays
Question:
Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$.
I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the ...
0
votes
1answer
23 views
SMO, Random forest and Bayes net algorithms: why does Random forest perform better?
I analyzed a dataset using those 3 different algorithms.
As I can see, Random forest performs better in most cases.
My dataset is composed of 4000 instances of two classes (class A 2000 elements, ...
1
vote
1answer
25 views
Distinguishability given black box access to the distribution
Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie,...
