# 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,547 questions
Filter by
Sorted by
Tagged with
47 views

### worst case scenario for sorting an array using insertion sort given that all elements can only be 0,1,2

were given an array of numbers "A" of size n, any given number in the array can be one of the following: 0,1,2. using insertion sort, what is the worst case scenario, and what is the best ...
14 views

### Calculating nth permutation without repetition efficiently, with variable number of elements

I know I can use the factorial number system to calculate ordered permutations of a set efficiently, given a constant length (for example, ...
• 141
16 views

### Boosting probability of Randomized approximation algorithms

Suppose $A$ is a randomized algorithm with following properties: The expected running time of $A$ is at most $\mathrm{poly}(n)$ When Opt$\geq c$, with probability at least $\mathrm{poly}(n)$ ...
26 views

### Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
71 views

### Minimum number of intervals from a set to cover all intervals of another set

There are two sets of intervals provided to us. target = {{11,13}, {7,10}, {0,3}, {6,6}} space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}} I need to find the minimum number of intervals I can pick from ...
• 23
57 views

### Precise definition of a brute force algorithm

What is the precise definition of a brute force algorithm? Is it one that simply has non-polynomial runtime?
• 154
51 views

### Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
203 views

### How to find a binary vector with minimized distance with a vector set?

Given a set of vectors $S = \{v_1, v_n, ..., v_n\}$, $v_i \in \mathbb{R}^m$. Now I want to find a binary vector $t \in \{0, 1\}^m$ to minimize $\sum_{i=1}^n \text {distance} (t, v_i)$. ...
• 33
25 views

### Is this knapsack variant named / studied? "Online algorithm for farthest-from-previous index"

Problem Statement: Given: an ordered list of N items, which we can refer to by index: [0, N). Goal: Write an algorithm to ...
• 123
1 vote
98 views

### Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
• 11
40 views

• 127
1 vote
20 views

### re-rooting a rooted DAG

A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have ...
• 111
36 views

### Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly. There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
9 views

### Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
• 101
42 views

### Intuition for Using Greedy Approach in Container with Most Water Problem

Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150 if we consider this solution: https://leetcode.com/problems/...
26 views

69 views

### Pseudo random permutation of a very large number of elements

Consider a file $\textbf{F}$ containing $n$ distinct elements, located on a hard drive. Given the large size of $n$, it's not feasible to load the entire file $\textbf{F}$ into main memory. Assuming ...
• 121
1 vote
36 views

### Weisfeiler-Leman Algorithm

We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
33 views

### How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?

Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists ...
• 101
1 vote
16 views

• 35
25 views

### Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...