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
2
votes
1answer
73 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
424 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
41 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
68 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
262 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
219 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
747 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
549 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
23 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$, ...
4
votes
0answers
26 views

Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
1
vote
1answer
52 views

What strategy should I use to sovle this interview problem? May I apply DP on this?

The problem description is as below and it feels like a DP problem but I am not sure, thank you for helping! You have a certain dose of a drug, say, 200 milliliters, and now some patients need this ...
1
vote
0answers
19 views

Algorithm to position samples minimizing error

We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the ...
1
vote
1answer
164 views

Error lower-bound for an algorithm for vertex cover

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 = \...
3
votes
1answer
108 views

Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

I was doing a few dynamic programming problems and I am struggling to understand the thought process required to come up with recurrences. The first problem I solved was longest palindromic substring ...
2
votes
1answer
66 views

Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ ...
3
votes
0answers
81 views

Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ...
-1
votes
1answer
48 views

How can i modify Dijkstra algorithm for equal situation?

I have a question below In Dijkstra’s Algorithm, if there is more than one possible shortest path from u to any vertex v, any one of the paths can be the output of the algorithms as a shortest path. ...
1
vote
0answers
26 views

Find closest points in a polygon

I have a 2D polygon defined by a list of $n$ points: $A$, $B$, $C$... These points are sorted in clockwise order. Example: I would like to find the most performant algorithm to detect all points ...
3
votes
0answers
33 views

Estimating number of points in 1D space

There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for ...
2
votes
1answer
138 views

Find shortest path of R,G,B Graph

Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. ...
0
votes
0answers
11 views

How to set width and depth of an attractor in hopfield network?

As far as I know hopfield network stores patterns as it's attractor states. But the width and depth of basins of attraction is not determined by user. Is it possible to make hopfield network to set ...
9
votes
1answer
217 views

Subset sum problem for permutations

Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
3
votes
1answer
49 views

Thirty-one game. Prediction of the winner

I have a problem with creating an algorithm to predict a winner of thirty-one game. Players from a deck of cards, take the Ace, 2, 3, 4, 5, and 6 of each suit. These 24 cards are laid out face up on ...
1
vote
0answers
22 views

Number of ways to pass edges of a cycle exactly n times [closed]

Consider an undirected network consisting of a single cycle with 6 nodes according to the below image with a given starting node. Is there a way to get an expression for the number of paths one may ...
2
votes
1answer
28 views

Edmonds-Karp Algorithm with both directed and undirected edges?

How would this work and be implemented? If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have ...