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
3
votes
1answer
180 views

Shortest subsequence containing all elements

Given a sequence $a_1,\ldots,a_n$, find the shortest subsequence $a_i,\ldots,a_j$ such that $\{a_1,\ldots,a_n\} = \{a_i,\ldots,a_j\}$. I came up with three solutions: The most straightforward brute-...
0
votes
1answer
55 views

Proof of the Bubblesort algorithm

I'm studying The Algorithm Design Manual and I was having some difficulty in the proof exercises, so I asked a question here. Based on the answer I got in that question(which was not the a complete ...
0
votes
0answers
48 views

Maximum matching to find the minimum edge cover

Suppose that I have an edge cover for the graph $G=(V,E)$ with non-isolated nodes to be a subset of $E^1$ of $E$ such that every vertex $v∈ V$ is incident to some edge in $E^1$. The size of an edge ...
2
votes
1answer
50 views

Matrix chain multiplication recurrence and its solution

We want to calculate $A_1 \times A_2 \times \cdots \times A_n$, where $A_i$ has dimensions $d_{i-1} \times d_i$. In the classical matrix chain multiplication problem, we wish to minimize the total ...
0
votes
1answer
35 views

Shortest Path with a twist

We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can ...
0
votes
1answer
29 views

Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly?

Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything ...
2
votes
0answers
18 views

Repairing a perfect binary merkle forest

Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, ...
0
votes
0answers
28 views

0/1 Knapsack problem. How does the total weight does not exceed the limit?

I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing. On the left is the [val,weight] and on the ...
1
vote
1answer
26 views

Membership in 1, 5, 2, 13, 10, … (recursively defined sequence)

Find if a given integer is in the series $1, 5, 2, 13, 10, \dots$ in the most efficient way, where the sequence is given by $$ f(n) = \begin{cases} 1 & n=1, \\ 2f(\tfrac{n}{2})+3 & n \text{ ...
1
vote
1answer
56 views

Is Dual Graph of a Triangulation of a Polygon Tree?

I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the ...
1
vote
0answers
15 views

Different definitions of Exponential Time Hypothesis

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it: Statement 1 There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables. Statement ...
2
votes
1answer
152 views

Bellman Ford facts and specific question

The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following: $d(v)>d(u)+w(u,v)$ holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)...
3
votes
0answers
18 views

Spanning hypertree which connects the vertices as slowly as possible

I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
0
votes
0answers
41 views

What is the difference between type theory and logic programming (in terms of declarative programming and specification)

How is does type theory (coq, lean, agda), and logic programming (prolog, datalog) differ from each other. Logic programming is a way of declarative specifying an algorithm, using classical 1st order ...
0
votes
1answer
46 views

MST and some facts via an example

$M$ is an MST of the Weighted Graph - $GR$. Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}. Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}. If $e$ is a edge ...
0
votes
0answers
26 views

Bellman Ford Algorithm in One Sweep

I'm trying to find an efficient algorithm (running time of O(|V|*|E|)) that finds for any graph an order of the edges that allows Bellman-Ford algorithm to run in a single sweep (iteration). I was ...
0
votes
1answer
94 views

design a strange data structure, is it possible?

I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible? When just find min is important (not removing) there is lots of $O(1)$ ...
0
votes
1answer
36 views

An algorithem for finding the number of primes of the form 4k+3 under some n

I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...
0
votes
1answer
37 views

What's the name of this sorting(?) algorithm?

Given the options of: Red Orange Yellow Green Blue Violet You want to find your favorite color by comparing all pairs to each other, like so: Red vs... Red vs Orange = Orange Red vs Yellow = Red ...
0
votes
0answers
17 views

Best algorithm / method to determine path length from noisy GPS points

i am analyzing a series of GPS points (with time stamps) which are noisy meaning have an accuracy of about 15 meter radius (sometime even more), and i need to extrapolate the distance the vehicle has ...
0
votes
0answers
20 views

Obtaining a set of $O(log n)$ classifiers using multiplicative weights algorithms

I'm trying to find an algorithm that uses the multiplicative weights algorithm to obtain a set of $O(logn)$ classifiers that classify a set $X=\{x_1, x_2, ...,x_n\}$ where the set of labels is $l \in\{...
1
vote
0answers
44 views

Proving that every graph has an order such that Bellman Ford can run in one iteration

I need to prove that for every given graph, that doesn't contain negative cycles, there is an order of edges so that Bellman-Ford algorithm will finish running after one iteration. I could only solve ...
0
votes
1answer
85 views

Count the possible plans for nurses

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below: The director of a hospital want to schedule a working plan for a nurse in a given period of N ...
0
votes
0answers
28 views

Gain the Mastery of prooving NP Complete Problems [duplicate]

I want some piece of advice on how can I improve my capability of proving NP-completeness of problems. I am well known with all the concepts theoretically but when it comes to solving down, I get ...
0
votes
1answer
45 views

How to determine if 2 rays intersect?

We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a ...
0
votes
0answers
68 views

What's the fastest time complexity algorithm for finding maximal paths in an unweighted directed graph?

I see a lot of interest online to the problems of finding shortest paths, longest paths, and all simple paths. I'm interested in implementing a state-of-the-art algorithm to find all (simple) maximal ...
1
vote
1answer
42 views

Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS

Trying to prove the following problem: Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in ...
5
votes
1answer
56 views

Mergesort and some claims on comparison

suppose for $n$ elements we using mergesort. each number compared at most $O(\log n)$ = False in average each element compared with $O(\log n)$ elements = True there exist an element compared with $\...
1
vote
2answers
38 views

Random restart technique definition

I have stumbled across this question about the Random restart algorithm in search problems: Random restart is technique which used for: a)algorithms for search in space state when they get stuck b)...
2
votes
1answer
28 views

What is the SetHorspool string searching algorithm and how is it implemented?

What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice? This has been implemented in 2 libraries I have come across: https://app-...
0
votes
0answers
16 views

Write recurrence for cost minimization

So I am trying to find the recurrence for this problem but I feel like it is missing something. An ice cream shop is looking to minimize their operation costs, under the given constraints: They are ...
1
vote
1answer
30 views

Determining the intersections of a line segment and grid

Problem: Given a line segment on the cartesian plane, determine where and which order it intersects a regular grid. This sounds simple, but is actually quite a tough problem. It's related to, but ...
0
votes
0answers
16 views

sort array using oracle computes number of elements in one partition that are smaller than given element in O(1)

excuse me for the long title. My goal is to find an algorithm to sort an array of n elements, with an oracle, which must be used O(logn) times. Given a partition of our array (resulting in two subsets,...
1
vote
0answers
70 views

What does this mysterious code do?

I came across some code and I'm trying to crack the case as to what it does: for $0 \leq f \leq l < len(A)$, the function is ...
0
votes
1answer
65 views

reduce k-colorable to 3-colorable graph problem

given a graph G = (V, E) of n vertices, decide whether G is k-colorable. if I were to have an oracle that solves for 3 color, how do I use it to solve the k color graph problem?
1
vote
1answer
80 views

Return 3 smallest elements in a list

How would we find the three smallest elements in a list and return it as a tuple (a,b,c) using divide and conquer? So far I've considered the following: ...
0
votes
0answers
35 views

The minimum three elements from two tuples of size 3

If I have two tuples (a1,b1,c1) and (a2,b2,c2), where we know each is ordered from smallest to largest, how would I return a ...
0
votes
1answer
31 views

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard Let $G$ be a cyclic group of size $m$, and let $g ...
0
votes
1answer
21 views
1
vote
0answers
13 views

Tracking approximate values of specific percentiles

At the moment I use HdrHistogram to track approximate distribution of a stream of values. But I don't really need all percentiles, just three of them. Is there some algorithm to track specific ...
0
votes
0answers
11 views

Can I have 2 free adjacent nodes in the fit algorithm for data management

so I know we can have 2 busy adjacent nodes for the fit algo since there'll always be free memory available, but what about when it comes to 2 free adjacent nodes? Is it possible to have 2 adjacent ...
1
vote
1answer
17 views

Optimal way to pack items with multidimensional weight such that the number of items is minimized?

I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, ...
0
votes
0answers
26 views

data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations

I've got this question from an exercise and i'm not sure if it is possible to do so Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
0
votes
2answers
22 views

PRECISE DPLL algorithm definition

I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently: In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M....
0
votes
1answer
19 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
2
votes
1answer
163 views

Minimum cost problem of breaking containers in $O(n\log n)$

Can anyone kindly give me some hint on solving this? There are $n$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with ...
-2
votes
1answer
59 views

Greedy algorithm for problem asking for solution of size *at most* $k$

Given an integer $k$ and a complete weighted bipartite graph with sides $A,B$ in which the weight of the edge $(i,j)$ is $c_{ij} \geq 0$, we want to find a set $S$ of at most $k$ edges that maximizes $...
0
votes
2answers
50 views

Infeasible linear programming reduce errors to find solution

Most normal linear programming problems look like this: We choose some point in the double shaded area that solves our optimizer and we're good to go. However, I've come across a problem where it's ...
0
votes
0answers
7 views

How can I create an algorithm in pseudo-code generating a sequence of numbers in such an order that they only are different at one position by 1?

Let's say we want to create sequences of the numbers {0,1,2} which are all at length n What I want to create is an algorithm which generates (and outputs) such sequences that they are only different ...
1
vote
2answers
39 views

Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find if there are two individual capacities that sum to a total capacity within a range of plus and minus the total capacity? Optimize for runtime over memory complexity. ...