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
7
votes
3answers
134 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
57 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
22 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
57 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
15 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 ...
6
votes
0answers
138 views

Correctness of a greedy Algorithm on Knockout Tournaments

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 ?
1
vote
1answer
72 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
58 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
64 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 ...
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
90 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)$, ...
4
votes
1answer
249 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
36 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
89 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
35 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
74 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
54 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
102 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
427 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
2answers
42 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
19 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 ...
9
votes
2answers
396 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
vote
1answer
48 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
25 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
22 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
69 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. ...
1
vote
0answers
16 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
55 views

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

Consider the following binary recursive fibonassi program: ...
2
votes
0answers
40 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
70 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
89 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 ...
0
votes
1answer
75 views

How to get Algorithm complexty based on another 2 algorithms?

I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively. Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (...
4
votes
1answer
176 views

Search for maximal value smaller than V in an array composed of K linear functions

Sorry for the lack of clarity in the question description. I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $[...
0
votes
1answer
23 views

Partitioning a set based on binary predicate

Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which ...
0
votes
0answers
19 views

Find expectation and calculate Chernoff bound [duplicate]

We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same 2 tasks to every ...
3
votes
1answer
266 views

Find expectation with Chernoff bound

We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every ...
2
votes
1answer
42 views

Image segmentation of a high resolution 2D binary image into clusters, threads and points

I use python3 script to find out the area proportion of pixel clusters, threads and points in my image. They are originally 8-bit greyscale TIFF images with a resolution of 2048x2168 pixels. I have ...
-1
votes
1answer
220 views

Proof for clustering in a network of friendship

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 ...
1
vote
2answers
749 views

min vertex cover to access k edges in a tree

I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices. For example, if $N=9$ and $K=6$ and we have ...
0
votes
0answers
29 views

Find a longest path with k vertices in a directed graph

Given a weighted directed acyclic graph $G=(V,E)$, find a path (with $k$ vertices) so that the sum of edge-weights is maximum.
1
vote
0answers
24 views

Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
2
votes
1answer
78 views

Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)

I am struggling with exercise from the old algorithmic exam: $d$ is const for the whole structure. Propose a structure for which you can do: Init(S) //called only 1 time Insert(x, S):: $ S := S \...
2
votes
0answers
22 views

FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
1
vote
1answer
551 views

Derandomization of vertex cover algorithm

I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set: Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$. Add to ...
1
vote
1answer
46 views

Find number of awesome substring of a given binary string

A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it. ...
1
vote
1answer
24 views

Dijikstra's algorithm with “hull” value catch

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here. Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...