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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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$ ...
-1
votes
0answers
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-...
0
votes
0answers
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 ...
1
vote
1answer
41 views

Time complexity of combinations of n pairs of parentheses

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

Advantages of Preemptive Scheduling

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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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 ...
2
votes
1answer
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/...
7
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
5
votes
0answers
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 ...
0
votes
0answers
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 ?
0
votes
0answers
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
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
2
votes
0answers
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)$ ...
4
votes
1answer
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)$, ...
-2
votes
0answers
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
4
votes
1answer
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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
1
vote
0answers
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.
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
4
votes
1answer
97 views

Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

Suppose I have an algorithm whose running time is $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$ And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\...
3
votes
1answer
401 views

Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
0
votes
1answer
32 views

Calculating match % and ranking according to that

I'm creating a website like where users will answer some yes/no questions set by me, up to them how many of those questions they want to answer. After a user submits his answer(s), he will be shown ...
0
votes
0answers
18 views

Traversing/comparing tree structures with only parent references

Consider a tree structure with nodes containing references to only their parent. So, the root node's parent will be null. This tree represents a class hierarchy. The goal is to search such a tree for ...
-2
votes
0answers
53 views

Describe a Turing machine which decides for any two words w,v in {a}* whether or not their lengths have the same parity [closed]

Describe formally (by means of a transition function) a Turing machine which decides for any two words $w, v \in \{a\}^*$ whether or not their lengths have the same parity (i.e., either both lengths ...
8
votes
2answers
372 views

Minimum number of swaps in sorting sequence

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array? I've been struggling with this problem for a ...
-1
votes
0answers
34 views

Online algorithm to output the number of good subsegments

Is it possible to do this problem online: https://codeforces.com/problemset/problem/997/E? All the AC solutions use offline sorting of queries. Here is the problem statement: Given a permutation $p$ ...
1
vote
1answer
41 views

Max heap and array relation

This question is about max heap and array Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at ...
1
vote
1answer
23 views

Upper bound on the average number of overlaps for an interval within a set of intervals

Let $\mathcal{I}$ be a set of intervals with cardinality $L$, where each interval $I_i \in \mathcal{I}$ is of the form $[a_i, b_i]$ and $a_i, b_i$ are pairwise distinct non-negative integers bounded ...
0
votes
0answers
19 views

Is it the right way to find preorder successor in a binary search tree?

I am confused about the case when the given node is a leaf. The code below does seem to work, but if someone asked me to prove the correctness I'd probably fail. Basically, can someone tell me why <...
1
vote
1answer
64 views

Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
0
votes
0answers
23 views

faster heap construction cost equation

can someone try to explain the following formula? I don't understand what does "<=n" and "<=2n" mean in this formula , it is my first time look at summation formula with inequality signature. ...
0
votes
0answers
15 views

Is there an algorithm to switch from classical notation to concatenative stack-based notation?

Reading a bit about Joy, I was wondering if there wasn't an algorithm to switch from classical notation and style to concatenative and stack-based style. Of course, for simple mathematical ...
0
votes
1answer
52 views

Understanding $O(2^n)$ time complexity due to recursive functions

Consider the following binary recursive fibonassi program: ...
2
votes
0answers
35 views

Proving that the Bellman-Ford algorithm contains negative circuit

Let $D=(V,B), n=|V|$ be a directed graph. Then the graph contains a circuit of negative length from $s$ if and only if $f_n(v) \neq f_{n-1}(v),$ where $v \in V,$ and $f_k(v)=$min$\{l(P)|P$ is an $s-v$ ...
0
votes
0answers
69 views

Prove an estimator

Consider an undirected graph $G=(V,E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
4
votes
1answer
122 views

Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after ...
4
votes
0answers
86 views

Is there a data structure that can perform range modulo additions and range minimum queries?

It is well-known that the Segment Tree performs range additions and range minimum queries in O(logN) each. Let each element in the array have value V[i], M[i]. We define a "range modulo add" as the ...