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

7,999 questions
Filter by
Sorted by
Tagged with
21 views

### Artificial ant colony algorithm for graph

let's assume we have ant at node $1$ and she has $\{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $p_{ij}(k)$ is the probability of $k$-th ant at node $i$ choose $j$ ...
17 views

### Given a network flow find if there's a min cut that only one of the given edges lay on it

Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$, and given 2 edges $e_1 , e_2$. find if there exists a min-cut such that only one of the edges belongs to the min-...
13 views

### Count to infinity problem (routing) between unsynchronized stations(tricky)

i was wondering, will count to infinity can occur in the following cases? if so, will it necessarily occur or can the routing tables stabilize themselves? Distances: From A to B - 3 from B to C - 4 ...
41 views

### Time complexity of combinations of n pairs of parentheses

I have the following code snippet for combinations of n pairs of parentheses. ...
12 views

I'm currently studying for an exam which includes operating systems. I'm solving the exams from previous years and I'm stuck on a particular question: "One of the advantages of preemptive scheduling ...
34 views

### A deck drawing problem

Given two decks of cards (ammount of cards in each deck is n) where each card holds a character, removing a card from the top of one of the decks counts as one action. If both decks show the same ...
22 views

### What is the run time of this algorithm, written in pseudocode?

count = 0 for i = 1 to n: for j = 1 to i: count += 1 So from my understanding, we can break this up into 2 summations, by nesting the $j$ loop as a ...
50 views

### Dynamic programming

Got a question and can't manage to find an answer, so help will be appreciated. I should design an algorithm, using dinamic programming, that gets as an input a matrix, named A, with n rows and k ...
6 views

### What is the difference between backtracking and forward checking / lookahead?

What is the difference between backtracking and forward checking / lookahead? Can you please give me explanation and simple example in programming language C, NETLOGO... I am trying to solve N-QUEENS ...
34 views

### What is the correct complexity of All paths from Source to Target DFS solution?

The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order." The DFS solution is described here. https://leetcode.com/...
86 views

### Find vertices of a convex polytope, defined by intersecting half-spaces

I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces that define it. In my special case the polytope is constructed by the ...
47 views

### How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the ...
21 views

### Dominating set in bounded degeneracy and bounded degree graphs

I believe Minimum Dominating Set (MDS) is NP-hard for bounded degeneracy and their subset bounded degree graphs, but a paper appear to suggest tractability. Enumeration of Minimal Dominating Sets and ...
54 views

### Even Odd problem

"A" represents all the odd natural numbers and "B" represents all the even natural numbers. For a given integer v, we can reduce it either by A0 or (A0)+1 then B0 or (B0)+1 and so on until the value ...
11 views

### Learning algorithm analysis

Im learning order of algorithm For x>=2, and rand(x) is function that return 1 value from 1 to x-1 which have uniform probability $\frac{1}{x-1 }$ And max(x,y) output bigger value and min(x,y) output ...
114 views

### Greedy Algorithm on Knockout Tournaments: Proof of Correctness

You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
20 views

### Chernoff Bounds (upper tail)

For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 . Like in this paper ([see this link ]) 1. Can you tell me why ?
12 views

### Cutting matrix in 2 congruent pieces [closed]

I have a matrix with 0 and 1. The 1 resembles a pattern , a shape. Cut the shape in 2 congruent pieces and make it in the matrix with 2 and 3. In c++ and keep it simple pls
65 views

### Sorting algorithm

I want to know from this picture which one is bubble sort, insertion sort and selection sort? My answer is: bubble sort algorithm, insertion sort algorithm, selection sort algorithm. Is it this ...
49 views

### Time complexity of a 2-heap question

The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window. arr = 1, 3, 5, 10, 6, 9, 2 k = 3 would yield ...
36 views

### Boruvka algorithm in Elog(log(V)) complexity

I am trying to implement Boruvka algorithm with the use of fibonacci heaps. My idea is the following: Since Boruvka's algorithm operates like this: Input is a connected, weighted and un-directed ...
12 views

### Algorithm to find Bayesian Nash Equilibria

I am working on a model in politics and economics using Bayesian games (modeling election behavior). I have little knowledge of programming, but given the complexity of the equations I feel the need ...
21 views

### Blossom's Algorithm or Maximal Matching [closed]

I am given a complete weighted graph and I need to make pairs among the vertices so that the sum of weights is maximum. (If I have vertices $v1, v2, v3, v4$ and if I make pairs $(v1,v2)$ and $(v3,v4)$ ...
75 views

### Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output

An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, ...
49 views

### Prove big-Oh by induction

How can I prove by induction that C * O(1) = O(1) For every C > 0 while C is a const and for every f, g function
238 views

### Find if there is matrix that satisfying the following conditions

Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an ...
33 views

### What are some variants of the rod cutting problem?

I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?
85 views

### A sort of job scheduling problem

I have been thinking about the following problem: Let $J$ be a set of jobs that need to be performed. Each jobs comprises of some number ($>1$) of tasks, and a job is considered finished when all ...
33 views

### Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
66 views

### How can I improve my algorithmic ingenuity?

During undergrad I felt my education was mostly comprised of applying existing theory to real world problems (ie. algorithm design/analysis). I've seen derivations of many algorithms and proofs of ...
51 views

### apply the method of conditional expectations

For a Randomized vertex cover problem Why there is not much hope of deriving an efficient, deterministic version using the method of conditional expectation? I can assume the problem is not ...
40 views

### Algorithm for sorting pairs of items

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem ...
97 views