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
-1 votes
0 answers
44 views

Make maximum number of numbers with $n$ digits

Let $A=[1..n]$ be an array of $n$ decimal digits. $A[i]$ contains one number from $\{0,1,\dots,9\}$. We can put adjacent elements of $A$ beside them to form a number in which, created number should ...
user avatar
  • 1
-2 votes
0 answers
34 views

Finding longest subsequence in a given sequence

Suppose given a sequence $X$ of numbers. We want to find the longest subsequence $X′$ of $X$ in which, for each $i$,$$ 2X′[i]<X′[i−1]+X′[i+1].$$ I think this problem is related to the longest ...
user avatar
  • 1
1 vote
1 answer
57 views

Are there invariants in text processing problems?

I have read that when programming it is good to identify relations -- invariants -- that should hold true throughout the program, and it is good to insert assertions throughout the code to check that ...
user avatar
0 votes
1 answer
44 views

Performant way to find all leaf nodes in a undirected graph

I am trying to find a better way to find all leaf nodes in my undirected waypoint graph. This is how I define a leaf node: A leaf node is a node that is never part of a cycle and so has to meet one of ...
user avatar
  • 137
-1 votes
1 answer
63 views

Largest number of disjoint paths of length $k$ and maximum reward in a tree

Consider exercise 23(c) of chapter "Greedy Algorithms", Algorithms by Jeff Erickson. Given a tree $T=(V,E)$ in which each node has a reward, and $k\in\mathbb{N}$, our goal is to find a set $...
user avatar
  • 1
0 votes
1 answer
29 views

Greedy algorithm for postive interval covering

Consider this problem from Jeff Erickson Algorithm that already in this site, there is a this post about it where it want us prove a lower bound for it. The question is: Suppose you are given an ...
user avatar
  • 1
1 vote
1 answer
41 views

A recursive relation for the number of well formed nested parentheses of length $n$ and depth $\leq d$

Consider a function $C(n, d)$ which counts the number of well formed, i.e, balanced, parenthetical 'words' of length $n$ and maximal nested depth $\leq d$. That is, $(())$ has $n = 4, d = 2$. $()((())(...
user avatar
1 vote
0 answers
17 views

Deterministic Algorithm for searching for object $d$ units down one road in a $k$ road intersection

Suppose we are at the centre of a $k$ road intersection (i.e, there are $k$ different roads radiating out from where we are standing, infinitely). Suppose along one of these roads is a treasure. This ...
user avatar
2 votes
1 answer
54 views

NP-completeness of some problems on assigning candidates to departments

Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
user avatar
  • 21
-1 votes
0 answers
59 views

Count number of point dominated by another points

Suppose given set $S$ of $n$ points in the plane. We say point $a=(x,y)$ dominate to $a'=(x',y')$ if and only if $x\geq x'$ and $y\geq y'$. For each point $b$, we try to compute number of points that $...
user avatar
  • 1
1 vote
1 answer
132 views

Find a path with given weight and the minimum number of edges on a tree

Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ ...
user avatar
  • 1
0 votes
1 answer
33 views

Tweaking Floyd-Warshall Algorithm to detect cycles

Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
user avatar
0 votes
0 answers
21 views

Compute equation $X^Y=n$ for given $n$ [duplicate]

Suppose given natural number $n$, we try find $X$ and $Y$ such that $$X^Y=n.$$ Is there any lower bound that show us, we cant solve the equation in $O(\log^k n)$ for some constant $k$? I think we can ...
user avatar
  • 1
3 votes
1 answer
41 views

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...
user avatar
0 votes
1 answer
95 views

Find largest number of disjoint paths with lenght $k$ in a tree

Consider this problem from Jeff book Given a rooted tree $T$ and an integer $k$ as input, and it should compute the largest possible number of disjoint paths in $T$ , where each path has length $k$. ...
user avatar
  • 1
1 vote
3 answers
475 views

Batch rounding with preservation of a sum

I have a sequence of floating point numbers. I want to map each of them to one of their closest integers. There is one rule: Sum of integers must be as close to the sum of original numbers as possible ...
user avatar
3 votes
1 answer
374 views

Count the number of intersections of n chords of a circle in O(n log n) time

Suppose you are given two sets $\{p_1, p_2,\dots , p_n\}$ and $\{q_1, q_2,\dots , q_n\}$ of $n$ points on the unit circle. Each point $p_i$ is connected to $q_i$ by a line segment. How could we count ...
user avatar
  • 1
0 votes
2 answers
87 views

Dynamic Programming - Difficult Jumping Frog Problem

Given a set of $n$ stones, arranged in a row at equal distances from each other. The stones are numbered from $0$ to $n-1$. A frog that is on stone number $0$ has to get to stone number $n-1$. A jump ...
user avatar
  • 29
2 votes
0 answers
29 views

How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?

I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it. So a k-core of a ...
user avatar
0 votes
1 answer
53 views

Time complexity of Euclidean algorithm

Consider Euclidean algorithm to find $GCD(a,b)$ as follow: $$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}.$$ I read this link, suppose $a\...
user avatar
  • 1
-2 votes
2 answers
45 views

What is the BigO of a C# function when runtime is 3n - logn + 1

I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
user avatar
  • 5
1 vote
1 answer
37 views

Use induction to prove the correctness of shortest path algorithm

Suppose given a directed graph $G=(V,E)$ with positive weights and we try to find shortest path $d(s,t,\ell)$ from $s$ to $t$ such that we traverse at most $\ell$ edges ($\ell$ is even). Let $w(u,v)$ ...
user avatar
  • 1
1 vote
1 answer
39 views

Can we show that #3CNF is in FPTAS

If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
user avatar
  • 33
-1 votes
0 answers
19 views

Proving that BeliefRevision is in APTime

We define the belief revision problem for propositional logic as follows. Let $F$ be a set of propositional formulas and let $ϕ$ and $ψ$ be propositional formulas. Given propositional interpretations (...
user avatar
-5 votes
1 answer
64 views

Implementing Flajolet–Martin algorithm in Python

I am stuck on what to do. I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
user avatar
0 votes
0 answers
25 views

Does P.M.I. stand for point wise mutual information or something else in the context of algorithm analysis?

The following comes from Exercise 2.3-3 of “Introduction to Algorithms, 3rd Edition by CLRS” Here is a solution to that exercise that solution says at the end “By P.M.I., T(n)=n lg n, when n is an ...
user avatar
  • 576
-1 votes
0 answers
26 views

Potato cutting algorithm

Given a potato that has a finite volume and a real $k$ and given that the potato's surface is triangulated (made up of triangles). Generate a set of $n$ planes that when used to cut the volume in $n+1$...
user avatar
0 votes
0 answers
10 views

Applying Divergence to Kinetic Data Structure

Problem statement :- There is a moving source($s$) and other moving points ($p_{1}.... p_{n}$). There are fixed obstacles and a fixed destination point($d$). In each time step I have to query "Is ...
user avatar
  • 157
-1 votes
0 answers
42 views

Returning two elements with minimum diference from $m$ sorted arrays

Suppose we have $k$ sorted arrays $A_1[1..n_1],A_2[1..n_2],\dots,A[1..n_m]$ that $$\sum_{i=1}^m n_i=n.$$ We try to select set $K$ from arrays such that contains exactly one element from each array ...
user avatar
  • 1
1 vote
2 answers
45 views

the load factor in hash table

What is numerically the best value or range of values used as a reference for the load factor used in the hash table? What is the pseudo-code of the “rehashing” method, which is applied when many ...
user avatar
  • 11
0 votes
0 answers
19 views

Algorithms for computing "optimal set growth order"

Imagine you have a collection of possible "components" (C) and a set of "recipes" assembled from those components (...
user avatar
  • 101
1 vote
1 answer
79 views

How to find wiggle sortable arrays? Did I misunderstand John L.s' answer?

I have read following answer and question How to wiggle sort an array in linear time complexity?. But while reading I came up with a question. I can't comment on answers yet, so I decided to make an ...
user avatar
1 vote
0 answers
22 views

How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?

I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
user avatar
  • 1,853
1 vote
1 answer
27 views

Proving 2SAT is in P vs algorithm for finding a satisfying assignment

I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
user avatar
  • 113
1 vote
0 answers
63 views

Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?

If you have an $\alpha$-approximation algorithm $A$ for some problem $f \in \#P$, such that (for $0 < \alpha \leq 1$) $$ \alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha}, $$ does that automatically ...
user avatar
  • 33
1 vote
1 answer
34 views

What is a de Bruijn sequence exactly?

I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess). There are two good resources I ...
user avatar
  • 1,853
1 vote
1 answer
84 views

Is there a simpler solution for this recuurence?

Consider this recurrence relation, $$T(n)=T(n-\sqrt{n})+1$$ I try to show that $T(n)=O(\sqrt{n})$. Also, I read this link, but my question is, can I claim that, at each step $n$ decreased by at least ...
user avatar
  • 1
1 vote
0 answers
17 views

Given a set, generate all permutations whose sums are less or equal to a given number

I am looking for a way to generate every permutation (so order does matter) of a set of positive numbers whose sum is less than (or equal to) a given limit. I need to find the permutations themselves, ...
user avatar
  • 121
1 vote
3 answers
63 views

Minimum number of query to find Largest sum of a contiguous subarray

Consider this post, the problem is given an array $A[1..n]$. We don't have direct access to $A$, but we can query what is the sum of $A[i..j]$ for every interval $i..j$. We would like to find the ...
user avatar
  • 1
0 votes
0 answers
12 views

Can you give an example of Metropolis and Metropolis-Hastings algorithm?

I have studied many books and tried to understand both the Metropolis and Metropolis-Hastings algorithm. Everywhere it is written in the context of the Ising model or Lenard-Jones Energy. I am having ...
user avatar
0 votes
0 answers
27 views

Algorithm for tracking the movement of nodes in a directed adjacency list

I have a directed adjacency list of node's. The structure of a node is Node { id: integer; order: integer; parentId: integer | null; } and the following ...
user avatar
  • 101
0 votes
2 answers
62 views

Find the largest MinHeap subtree in a given Tree

We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
user avatar
  • 21
1 vote
0 answers
45 views

The Longest Sequence of Blocks

We have n block $B_i$ $(1 \le i \le n)$, each block has 6 faces and each face material, is one of the k types (k is an input parameter). In addition, each block $B_i$ has the weight $W_i$. the ...
user avatar
  • 21
-2 votes
0 answers
23 views

Algorithm to find a path of length at least $\Omega(\log n/\log \log n)$

Suppose that an undirected graph G has a Hamiltonian path. Give a polynomial-time algorithm to find a path of length at least $\Omega(\log n/\log \log n)$. Does someone know how works this algorithm?
user avatar
2 votes
1 answer
37 views

Differences between DFS based cycle detection algorithms

I have seen several variants of DFS algorithms used to check existence of cycles in graphs. They all have the same structure : do a DFS in the graph. There is a cycle in the graph if and only if there ...
user avatar
  • 131
1 vote
1 answer
54 views

an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices

Given B and C operations. B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices. C-operation: When one edge ...
user avatar
2 votes
1 answer
20 views

Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$

Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the ...
user avatar
-1 votes
0 answers
39 views

Need help writing an algorithm with specific complexity

i need help writing an algorithm with complexity log^(k)n where k>0 and log has a base of 2. Thanks
user avatar
0 votes
0 answers
47 views

Lower bound of solving a optimization problem [duplicate]

Suppose given $k$-sorted arrays of numbers that contains total of $n$ elements. we try to choose $k$ elements in $k$ arrays (each arrays exactly one element) such that minimize difference between ...
user avatar
  • 1
0 votes
0 answers
23 views

How do I get $T(n) \leq cn^{lg(3)}-2n$ from $T(n) \approx n^{lg(3)}$?

I'm learning "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein", referencing the solution to Exercise 4.4-1 I know the ...
user avatar
  • 576