# 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
Filter by
Sorted by
Tagged with
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$? ...
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 ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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  \...
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 <...
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 ...
64 views

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 ...
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), ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
12 views

...
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. ...
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 ...
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,...