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
vote
1answer
18 views

For QuickFind, which sub problem we should consider

Question: Suppose we have the following array where we want to find the smallest $i$th smallest element in the array using QuickFind algorithm (similar to QuickSort): $$ QuickFind\left( A,n,i \right) ...
0
votes
1answer
48 views

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?

For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase? For example, for the SAT problem, the first question is whether the Boolean ...
0
votes
0answers
26 views

Removing and adding edges from spanning tree

Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
1
vote
1answer
29 views

In a sorted subarray $Z_{ij}$ elements $i$ and $j$ get compared when either $i$ or $j$ is pivot

This is related to the discussion of average case of quick sort. Given that we have a sorted sub-array $Z_{ij} = i, i+1, \dots, j$ where $i < j$. Claim: $i$ and $j$ are compared if and only if, ...
0
votes
0answers
32 views

Randomized Quick Sort Discussion

I would just like to discuss with you first part of the proof for quick sort please unless you need more details. Probabilistic fact: For a quick sort please, given that the expected number of coin ...
0
votes
0answers
17 views

Binning a set into subsets deterministically

I have an unordered set of n unique, positive integers. I want to partition it into ceil(n / k) unordered sets of up to ...
2
votes
0answers
177 views

Produce a Dynkin system from a finite set of finite sets

[Updated question] A Dynkin System is, provided all sets are finite, a collection of subsets of a universal set closed under complements with the universal set and closed under union of disjoint sets. ...
1
vote
1answer
51 views

Merging sorted arrays stored as linked lists

I have $k$ sorted arrays stored as linked lists. I need an algorithm to merge them into one single sorted array, also stored as a linked list. How can I do that? My Code: ...
0
votes
0answers
22 views

Finding a full collision within a large array

I apologize for the vagueness of the title, but this question is quite difficult for me to describe. For that reason, I'm unable to directly convey my problem. In an effort to circumvent this, I've ...
1
vote
0answers
114 views

Approximating the number of triangles using $\ell_0$ sampling

How do you solve the following question, from this assignment? Question 2. Consider a stream that consists of the $m$ (distinct) edges of a graph on $n$ nodes. Let $T$ be the number of triangles in ...
0
votes
0answers
12 views

Incorrect average turnaround time calculated for FCFS schedule?

I am trying to solve the following problem: If all of the jobs listed below are scheduled FCFS (First Come, First Serve) with no switching overhead, the average turnaround time is going to be: ...
0
votes
1answer
30 views

Bin packing problem and optimality proof

Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
2
votes
0answers
25 views

Algorithm for stacked orders in food delivery (Pick up and deliveries)

I am trying to implement stacking orders While the most optimal solution would be to consider picking up orders from nearby restaurants that have similar food prep time AND nearby delivery locations. ...
-1
votes
0answers
35 views

form sub-array from an array

I have an array A = (0,1,0,1,1,2,0,1) where A[i] = (1.....n). I need to find intervals of array index which contain all three numbers {0,1,2} i.e the above array can have many sub-arrays. If we ...
0
votes
1answer
39 views

prove sub array has a definite form with distinct end point integers

An array has elements from set {0, 1, 2}. A span SP of an array is any interval [start S, end E] such that the sub array must contain all elements from {0,1,2}. For example: in Array A = (0,1,0,1,1,2,...
1
vote
0answers
34 views

Can smoothed analysis be studied on the batch dynamic model?

I was reading about the batch dynamic CONGEST model for distributed computing. This model assumes a fixed communication network, but where local inputs to nodes may change over time. It aims to study ...
0
votes
0answers
46 views

Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
0
votes
1answer
56 views

Sorting by boolean algebra (hardware) instead of algorithm (software)

Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11] Maybe that case seems complicated,...
0
votes
1answer
101 views

Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
1
vote
0answers
22 views

Postponed sieve algorithm with start logic [closed]

Based on the answer by Will Ness, I've been using a JavaScript adaptation for the postponed sieve algorithm: ...
0
votes
0answers
31 views

From roots to coefficients of a polynomial [duplicate]

Polynomials are usually written as a sum of powers (or various products of generators) and Google gives me lots of results on how to get from that to the form that is a product of degree-$1$ ...
2
votes
0answers
30 views

Space-Efficient Online Computation of Quantile Summaries Lemma 3

I am reading the paper Space-Efficient Online Computation of Quantile Summaries and get really stuck trying to understand Lemma 3 onwards. I am sorry it sounds like a lot of questions - this just ...
1
vote
2answers
71 views

Find neighbour objects in a 3d grid

I have points in a 3d world where their position is defined by 3 integers: X, Y, Z. I'm searching for an algorithm / data structure to store these points in a way I can quickly find (e.g.: O(log(N)) ...
2
votes
1answer
45 views

Why is this greedy strategy always correct for this problem?

I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/ My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all ...
0
votes
1answer
36 views

Comparison sort algorithm

Consider the following algorithm: The given items are inserted one by one into a list by performing comparisons like a binary search for the right position. Example: Imagine six elements are already ...
1
vote
1answer
42 views

House Robber DP Algorithm (Not three in a row)

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
4
votes
0answers
54 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
1
vote
1answer
41 views

Proving that deterministic approximate counting uses log(n) space

We just saw the Morris algorithm in class and we were asked the following: In class, we saw a constant factor approximate randomized counting algorithm with space complexity $O(\log \log n)$, where $...
0
votes
0answers
33 views

Solving $T(n) = T(0.01n) + T(0.99n) + cn$ [duplicate]

How to solve the below relation? $$ T(n) = T(0.01n) + T(0.99n) + cn $$ This will not be a balanced tree. For $k$ levels I have something like $\bigl(\frac{1}{100} + \frac{99}{100}\bigr)^k \cdot cn$. I ...
0
votes
0answers
20 views

Resampling an array of objects

Context I have an array of objects (or a list of dictionaries), sorted in order based on a property of each object, say, time. In JSON, it would look something ...
1
vote
1answer
103 views

Why is the space complexity of finding anagrams in a string O(1) instead of O(n)?

In the problem find-all-anagrams-in-a-string, one tries to find all anagrams of a string $p$ (of length $k$) in a string $s$ (of length $n$) and return a list of the anagrams' starting indices. The ...
0
votes
1answer
102 views

Master Method: Divide and Conquer

According to my evaluation ,the overall asymptotic running time of the below algorithm is O(n) ,since x (number of recursive ...
1
vote
1answer
42 views

Why we need topological ordering for finding shortest paths

This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering. ...
3
votes
1answer
41 views

Comparing different versions of Steiner Connected Component Subgraph problem

Problem 1 Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected ...
0
votes
1answer
90 views

What could be the most efficient algorithm to find index in an array that matches given conditions?

I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1]. Example: ...
3
votes
0answers
37 views

How to achieve a "balanced" min-cost flow solution

I'm not too familiar with minimum cost flows, so please bear with me. I need to calculate the minimum cost flow for a network that looks like this: (The numbers in parentheses next to nodes indicate ...
3
votes
1answer
102 views

Maximum interval scheduling - Circular Variation

Consider a variant of interval scheduling except now the intervals are arcs on a circle. The goal is to find the maximum number of arcs that do not overlap. Let $C$ be the circle on the plane centered ...
1
vote
1answer
40 views

Detecting odd cycle using mod operator and breadth first search algorithm

If we want to detect and odd cycle if an undirected graph $G=<V,E>$. Suppose we run BFS algorithm from CLRS book as follows, Q: Now my question is suppose we have the following graphs: The ...
0
votes
0answers
10 views

Ensuring radial symmetry when distributing a vectorial quantity on arbitrary particle configurations

I come from a physics background, and I am trying to find some more information on this problem that I am encountering, and which I describe below. I don't know whether this sort of problem has some ...
0
votes
1answer
44 views

Inversions of Insertion Sort and Bubble Sort

An array with bubblesort time $\Theta(n)$ is nothing but a sorted array like: A = 1 2 3 4 5 No swaps are done so only $n - 1$ comparisons. An array with insertionsort run time $\Theta(n^2)$ is a ...
0
votes
1answer
93 views

What is the meaning of the pipe symbol here?

I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
0
votes
2answers
46 views

inversions in array

If the worst case arrays {5 4 3 2 1} have number of inversions as Θ(n^2) => n(n-1)/2 swaps The best case arrays {1 2 3 4 5} have number of inversions 0(no swap) What kind of arrays have number of ...
0
votes
0answers
23 views

Prove that $d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=1,2, \cdots, r-1$ on queue $Q$ based on BFS algorithm

Given the following lemma first: Lemma 1: Let $G=<V,E>$ be a directed or undirected graph, and let $s \in V$ be an arbitrary vertex. Then, for any edge $(u,v) \in E$, $$\lambda(s,v) \le \lambda(...
0
votes
1answer
30 views

sort is equal to inversions logic

In Bubble sort, the number of swaps/comparisons is equal to the number of inversions. 1st pass it will do (n -1) comparison 2nd pass it will do (n-2) comparison....so on (n-1)n = n^2 - n Worst case ...
3
votes
3answers
122 views

Algorithms question: Largest contiguous subset selection

Q. Given two arrays, $A$ and $B$, of equal length, find the largest possible contiguous subset of indices $[i,j]$ such that $\max(A[i: j]) < \min(B[i: j])$. Example: $A = [10, 21, 5, 1, 3], B = [3, ...
0
votes
0answers
23 views

Algorithm to find roots of a "bidimensional function"

The object I am studying is a bit more complicated than a bidimensional function, but I think I can explain what I need better with a simplified example. I can provide more details if asked. So ...
0
votes
0answers
19 views

When do I use inversions in an array?

In problems like the 15 Tile Problem or Larry's Array problem, we use inversions in the array as a method to solve. But what's the principle behind this method and how do I know when to use inversions?...
1
vote
1answer
34 views

Algorithm to find approximate position of element from a noisy sorted list

Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x In a sorted list ...
0
votes
1answer
27 views

simplified into asymptotic notation

I have a function that needs to be represented in theta form. The below is my answer. But the correct answer is 𝜃(n.2^n) Can someone please explain me how??
0
votes
1answer
31 views

The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...