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
1 answer
56 views

The average time complexity of linear search with weighted probability

Given array of numbers $A[1..n]$. We search for element $x$ with linear search. Also we know that, element $x$ occurs in $A$ and probability of $x$ be in second half of the array is $3$ times of ...
user avatar
  • 1
0 votes
2 answers
75 views

Why do the pointers in Two-pointer algorithm move only towards each other?

Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number. The solution to the above problem goes like this: With using the ...
user avatar
0 votes
1 answer
55 views

Find $k$ shortest paths in linear time

Suppose given number $k$ and undirected unweighted graph $G=(V,E)$, also given two vertices $s$ and $t$. Can we find $k$ shortest paths between $s$ and $t$ in $O(n+m)$ without term $k$? I read this ...
user avatar
0 votes
0 answers
34 views

Undirected unweighted sub-graph enumeration with threshold on node value

I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive. Given an input threshold $t\in [0,1]$, I ...
user avatar
0 votes
2 answers
86 views

Binary compression algorithm with decompress by index

I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
user avatar
0 votes
1 answer
81 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
user avatar
0 votes
0 answers
24 views

Considering definitions as equalities, what would happen if you continually substituted a word’s definition?

I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer. The idea is to ...
user avatar
2 votes
1 answer
542 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

The problem concerns finding shortest paths in graph from a single source to a single destination. So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
user avatar
0 votes
0 answers
39 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 $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
user avatar
0 votes
1 answer
107 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
  • 71
0 votes
1 answer
23 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
33 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
36 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
125 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
79 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
  • 217
2 votes
2 answers
49 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
67 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
2 answers
211 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
58 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
142 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
0 votes
0 answers
26 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
1 vote
2 answers
54 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
27 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
50 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
21 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
30 views

Understanding MTD-f

In the MTD-f algorithm: ...
user avatar
  • 123
1 vote
3 answers
58 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
59 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
2 votes
0 answers
50 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
  • 21
1 vote
2 answers
75 views

Are there any freely available resources to study randomized algorithms?

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 algorithm, thank you a lot.
user avatar
  • 153
1 vote
1 answer
30 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
1 vote
2 answers
38 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
53 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
  • 37
3 votes
2 answers
295 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
36 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
25 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
524 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
  • 164
2 votes
1 answer
226 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
47 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
  • 293
3 votes
1 answer
25 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
52 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
0 votes
1 answer
112 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
  • 71
0 votes
0 answers
28 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 vote
1 answer
47 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
  • 293
1 vote
1 answer
61 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
  • 173
0 votes
1 answer
27 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
167 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
  • 173
1 vote
0 answers
32 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
  • 173
1 vote
0 answers
63 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