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

Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

Given a graph with $V$ vertices and a set $K$ of $k$ vertices of $G$. Let $c(u)$ be the distance (in BFS-like) of the vertex $u \in V$ to the closest vertex $k \in K$. How to choose the set $K$ such ...
user avatar
0 votes
1 answer
32 views

Finding a Hamiltonian Cycle in a directed graph - graph problem

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
user avatar
  • 29
0 votes
1 answer
17 views

Is there an algorithm for mapping two ambiguous and unrelated data sets?

I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets. So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
user avatar
  • 1
1 vote
1 answer
25 views

Find the largest subset of unpaired elements [duplicate]

I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired? Example ...
user avatar
  • 113
0 votes
0 answers
30 views

Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
user avatar
1 vote
1 answer
51 views

Formal Proof on why Greedy isn't working on one Particular Problem

Problem You are given two integer arrays nums and multipliers of size n and ...
user avatar
2 votes
1 answer
70 views

Is $m \log^2 n$ complexity too much?

I have been struggling for a few hours in terms of finding the right solution for the following problem: Suppose we have a file that contains integers where each represents a user of a service. By ...
user avatar
  • 195
2 votes
2 answers
45 views

Delete consecutive characters and add zeros at the end with a restriction

Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character, The restrictions: $...
user avatar
  • 21
0 votes
0 answers
26 views

Wrong Solution for `Spanning tree with chosen leaves` problem

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ ...
user avatar
  • 1
3 votes
1 answer
162 views

Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $

The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
user avatar
1 vote
2 answers
51 views

Find largest set of players that never played against eachother

I have an interesting problem I need to solve. I have a list of about 200k two player matches containing about 22k unique players. I need to find the largest set of players that never played against ...
user avatar
2 votes
1 answer
117 views

Sorted list of counters in constant time

Summary. A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements. ...
user avatar
1 vote
1 answer
31 views

Sum in counting satisfying assignments

Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of ...
user avatar
0 votes
0 answers
19 views

Is this how Interval Partitioning Problem aka interval graph coloring problem works?

You can refer the problem on later part of section 4.1 in "Algorithm Design Book by Jon Kleinberg and Éva Tardos" Problem: We have "n" lectures and we our job is to assign all of ...
user avatar
0 votes
2 answers
44 views

Optimizing an arbitrary function of 10 variables

Let us be given a function $f(x_1,\dots,x_{10})$ of multiple variables $x_1,\dots,x_{10}$ given that $\sum_{i=1}^{10} x_i \leq 7$. How do we solve the following problem? $$ \begin{equation} \begin{...
user avatar
0 votes
0 answers
22 views

What is the best algorithm to flip a triangle?

I'm trying to flip a triangle like this in the following image: there are two constraints in flipping it: 1- flip it with the minimum circles moves 2- the circles is sliding from a place to another ...
user avatar
  • 1
0 votes
1 answer
47 views

Algorithm for generating sorted lists of random floats

More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output ...
user avatar
1 vote
0 answers
20 views

"Icebreaker problem": Dividing set into partitions that maximize pairwise shared memberships?

Suppose I have a set of N*L elements. I wish to generate a sequence of k partitions of size L such that I maximize the number of pairs of elements that share membership of the same partition. What ...
user avatar
  • 163
2 votes
0 answers
25 views

Understanding MTD-f

In the MTD-f algorithm: ...
user avatar
  • 123
1 vote
3 answers
55 views

Difference between an exact and Big O Notation for worst case runtime

I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm. This is what I'm struggling to ...
user avatar
1 vote
1 answer
52 views

Is Set Cover problem with subsets of size ≤2 solvable in polynomial time?

I came across the below question where the polynomial time solution to the "Set Cover Problem" is discussed when the subsets are of size EXACTLY 2. Set cover problem with sets of size 2 The ...
user avatar
1 vote
0 answers
42 views

A Single Row GUI Layout Algorithm

I need a layout algorithm and use it in the GUI, but I can't use existing GUI toolkits at the moment, so I would like to find a layout algorithm. I only need to do a single row layout, and here is the ...
user avatar
  • 11
0 votes
2 answers
42 views

Is there any open resource to study randomized algotithm?

I am a student want to study randomized algorithm. Someone recommend cs271 to me, but it's restricted now. Can someone recomend a good resource to study randomized, thank you a lot.
user avatar
  • 113
1 vote
1 answer
27 views

Complexity of finding $d$ largest eigenvectors of a symmetric matrix

I know that for $n \times n$ matrix, it takes $O(n^2)$ time complexity to compute the largest eigenpair of the matrix using Power method or etc. I'm interested to further extend the case so that now ...
user avatar
-2 votes
0 answers
44 views

Prove or disprove f(n) + ω(f(n)) = Θ(f(n))

I am so confused by how to begin proving or disproving this. Any help would be much appreciated.
user avatar
1 vote
1 answer
26 views

What is a good load factor for seperate chaining (closed addressing)?

For open addressing, I know that once you have around 70% table being filled you should resize because more than that you get collision. But for closed addressing, I read that load factor should not ...
user avatar
  • 11
1 vote
1 answer
46 views

Randomized Algorithm Lemma

Hello I am struggling with proving a lemma, it goes as follows: Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose ...
user avatar
  • 25
-1 votes
0 answers
16 views

Time complexity of FPT reduction [closed]

I'm at a loss about how to approach this issue: Suppose that we know that parameterized problem $B$ can be solved in time $\mathcal O^*(3^k)$. Furthermore, there is a parameterized reduction from ...
user avatar
3 votes
2 answers
277 views

Number of Inversions found in Selection sort vs Exchange sort

Exchange sort is similar to selection sort, just swaps "overly eagerly" instead of finding the minimum and doing only one swap. And the swaps affect how often the ...
user avatar
1 vote
1 answer
29 views

Variation of Assignment Problem to maximize amount of agents working

I'm looking at a problem similar to an assignment problem. There are both agents and tasks. Each agent has a list of tasks they are able to do, and cannot do any task not within that list (note that ...
user avatar
0 votes
0 answers
18 views

Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
user avatar
2 votes
2 answers
511 views

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
user avatar
  • 145
2 votes
1 answer
209 views

Show all chains per user

Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it. You have a chains of reservations from AirBnb: ...
user avatar
0 votes
1 answer
31 views

Find matrix local minimum - two analysis which seem to get contradictory runtimes

Suppose you have an $n\times n$ matrix and you want to find a local minimum. To find it you scan the middle row and column and identify a minimum. If it is a local minimum, you're done; if not, you ...
user avatar
  • 283
3 votes
1 answer
23 views

optimal search algorithm for finding parameters and thresholds

I have the following problem: There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'...
user avatar
0 votes
1 answer
47 views

equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
user avatar
-1 votes
0 answers
24 views

Amortized analysis definition confusion

In wikipedia, I was reading about amortized analysis and I read the following definition: " Instead, amortized analysis averages the running times of operations in a sequence over that sequence.&...
user avatar
  • 169
0 votes
1 answer
75 views

Is there an edge whose removal will extend the shortest path? - graph problem

Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal ...
user avatar
  • 29
0 votes
0 answers
27 views

Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as - F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
user avatar
-1 votes
0 answers
8 views

lightest path from s to t that goes through vertex v even number of times [duplicate]

Given a directed simple graph G=(V,E) and two vertices s,t and a vertex v∈V−{s,t}, we would like to find the lightest path from s to t, that passes through v even number of times. for every edge there'...
user avatar
1 vote
1 answer
42 views

Subdivide a graph into non-crossing triangles with maximum edge weight

Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum ...
user avatar
  • 283
1 vote
1 answer
57 views

What does the following recurrence formula represent

I know that : $T(n,k)=T(n−1,k−1)+T(n−1,k)$ is the Pascal triangle. But what is this then: $T(n,k)=T(n−1,k−1)+T(n,k-1)$ Is there any name for it? I am trying to learn about it's time complexity etc, ...
user avatar
  • 169
0 votes
1 answer
25 views

Does FPT allow for doubling the parameter?

I have recently come across a result that showed that a given problem is in FPT when parameterized by the treewidth of a graph. However, they did this by showing that the problem is in FPT when ...
user avatar
  • 145
0 votes
1 answer
36 views

What is this task type?

There are people and the food they prefer: John -20> Apple John -10> Pear Ethan -20> Apple Ethan -5> Orange Michael -10> Pear Michael -10> Limon The numbers indicate how strongly ...
user avatar
1 vote
2 answers
158 views

Problem size and how it's different than the input for an algorithm

I am trying to understand how the input size, problem size and the asymptotic behavior of an arbitrary algorithm given in pseudo code format differ from each other. While I fully understand the input ...
user avatar
  • 169
1 vote
0 answers
29 views

Master Theorem but with 2 different T's from two different recurrent trees

I am studying the Master Theorem, but there is a case in which I have no knowledge on how one should proceed. If it's given: $T_1(n)= 1$ if n=1 $T_1(n)= 4T_1(\frac n2) + \sqrt{3n}+1$ otherwise. For ...
user avatar
  • 169
1 vote
0 answers
52 views

Is there an alternative method to using Gaussian elimination in order to solve 3-XORSAT

I have a large system of $3$-$XORSAT$ constraints (i.e. up to $3$ variables per constraint) and this can be represented in matrix form as a linear algebra problem $Ax=b$ $mod$ $2$. Solvability (i.e. ...
user avatar
  • 11
2 votes
2 answers
83 views

Decision tree for searching element in sorted-array

Given the problem of having a sorted array $A$, an element $x$ to be searched for in the array $ A $, what is a lower-bound on the process of finding $x$ in $A$? The answer is $ \Omega(\log n) $ ...
user avatar
-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
2 3 4 5
210