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
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
110 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
67 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
89 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
49 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
139 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 ...
2
votes
1answer
276 views

O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list: Initialize an array of integers "colors" with V elements being 1 Using ...
0
votes
0answers
29 views

Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
1
vote
1answer
68 views

Finding a winner in a “long list”

This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win" markets for 13 games. A punter can select any combination of the possible ...
3
votes
1answer
58 views

Number of ways n can be written as sum of at least two positive integers

I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. ...
4
votes
0answers
65 views

How was the four color theorem proved using brute-force search?

I recently learned some graph theory in Discrete Structures for Computer Science, we learned about the Four Color theorem, I realize there is a mathematical proof for this topic, but how was it ...
-1
votes
1answer
61 views

A single heap nim game

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game. A set P = {p1,p2,…,pk} determines the allowed moves....
2
votes
1answer
40 views

Picross solving: matching checked cells to their clues

I am writing a picross solver, and I am going with the "human logic" solving, which attempts to reproduce the reasoning a human might have when confronted to such a puzzle, in an iterative manner. ...
1
vote
1answer
794 views

How can ideas like Lagrange Multipliers and Penalty Method be applied for solving algorithms?

I have a programming assignment which I was told that is solvable with some DP algorithm. The question involves some $k$ which is essentially a constraint. In particular the question is a variant of ...
0
votes
0answers
29 views

Enumerating special Matrices

Is there an efficient algorithm for enumerating binary $n\times n$ matrices which are such that each row has 𝑘 1's and each column also has 𝑘 1's? Related - https://math.stackexchange.com/questions/...
9
votes
0answers
168 views

2D interval scheduling problem

Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{...
2
votes
1answer
44 views

(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

The following question is taken from Leetcode entitled 'Combination Sum' Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique ...
3
votes
1answer
404 views

Shortest paths between given red vertices and arbitrary blue vertices

Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the ...
2
votes
0answers
32 views

Find sub-matrix containing the maximum number of elements consisting only of 1's [closed]

I am trying to get help on it here, originally posted first at: https://stackoverflow.com/questions/59446920/find-sub-matrix-containing-the-maximum-number-of-elements-consisting-only-of-1s Basically ...
1
vote
1answer
176 views

Counting number of paths between two vertices in a DAG

I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
0
votes
0answers
15 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
0
votes
0answers
30 views

Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
3
votes
1answer
177 views

find the union of all min cuts of a flow network

I'm trying to solve the following question : Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and ...
1
vote
2answers
264 views

Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
3
votes
2answers
91 views

Coloring an interval graph with weights

I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
3
votes
0answers
58 views

Finding all feasible solutions to a multiple-knapsack program

How can I find all feasible solutions to a 0-1 integer program that I have based on a knapsack-style problem? I have $n$ items and $m$ knapsacks. Each knapsack has a space limitation and each item ...
1
vote
0answers
40 views

Algorithm to find a all valid matrix permutations [closed]

I have an array of $N^2$ numbers like $ a = \{ a_1,a_2, ..., a_{N^2} \}$ where all $a_i < F$ where $F$ is a fixed number. I am looking for all permutations where if I put values in $A$ in order (...
9
votes
2answers
195 views

Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E) $, and as long as you ...
4
votes
1answer
57 views

Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
-2
votes
1answer
82 views

Algorithm for smallest number in array larger than threshold

We define the problem SmallestAbove as follows: Given an array $A$ of $n$ integers and a value $v$, compute the smallest value in $A$ that is strictly greater than $v$. Return $\infty$ if no such ...
0
votes
0answers
20 views

edmond karp proof

which contradicts our assumption that ıf $d_f'(s,v)<d_f(s,v)$. We conclude that our assumption that such a vertex exists is incorrect I can't comprehend the proof above for edmond karp algorithm ...
2
votes
2answers
53 views

What algorithm may be used to solve the re-assembly of shredded papers?

I was once given this question in an interview: Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so ...
4
votes
1answer
45 views

Generating all equal-sized set partitions

Minor disclaimer: This is my first question here, so I hope it is the right place to put it. Question: Is there an algorithm to exhaustively generate all set partitions of equal size? That is, I ...
1
vote
0answers
52 views

Optimal ordering - Dynamic programming on subsets

We have a set T of n elements and m subsets $R_i \subset T i = 1,...,m$. The $S_i$ are not assumed to be different. We also define an ordering of T, a one-to-one mapping $\pi$ of $T$ onto the set of ...
1
vote
0answers
61 views

Loop invariant of a search algorithm

I have to come up with a proof of correctness of the following algorithm: GuardedSearch(A; v) Input: an array A of n numbers and a number v Output: an index i such that A[i] = v, or NotFound if no ...
0
votes
0answers
11 views

learning the private key by reusing same random variable k in ELgamal

i wonder: if for some reason, someone, say alice, sends unencrypted messages to bob and signs it using elgamal signature, can oscar,the adversary, gain knowledge of the private key if alice reused the ...
1
vote
2answers
58 views

A special case of subset sum

I came across the following problem in my complexity-theory course: Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such ...
0
votes
0answers
12 views

Can solid voxelization be done with 1-direction raytracing if the raytracer is watertight? Does the direction matter?

This article and some others mention requiring the following when voxelizing: 1: Shooting rays from multiple directions (maybe with a voting system to decide if the voxel is active?) 2: Shooting ...
0
votes
1answer
40 views

How to remove cycles from a directed graph by edge contraction?

We have cyclic directed graph (possibly disconnected). For cycles consisting of two vertices A->B and B->A, we replace them by a single vertex. In case of A->B, B->C, C->A we also replace them by one ...
1
vote
0answers
19 views

Dynamic programming for subsequence metric

Let $a = a_1, \ldots, a_n, b = b_1, \ldots, b_m$ be sequences of positive integers and for any respective subsequence of length $k$, we consider $\sum_{i=1}^k (a_{x_{i}}-b_{y_{i}})^2$. Given a bound $...

1 3 4 5 6 7 163