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
16 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 ...
2
votes
0answers
31 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 ...
2
votes
1answer
27 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
22 views

My algorithm to find Longest Palindromic Substring does not work correctly in some cases

Question: Given a string s, return the longest palindromic substring in s. Example 1: Input: ...
0
votes
0answers
30 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
12 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 ...
0
votes
0answers
44 views

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

In this problem (https://leetcode.com/problems/find-all-anagrams-in-a-string/solution/), one tries to find all anagrams of a string p (length k) in a string s (length n) and return a list of the ...
0
votes
0answers
15 views

understanding or recurrence relations in code

I have a piece of code as below ...
0
votes
1answer
44 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
36 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
35 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
51 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
31 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 ...
-2
votes
0answers
29 views
3
votes
1answer
63 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
31 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
0answers
24 views

Desired outcome calculation in a single player game

I have a game. In which we have 2 steps. In the first step we have 3 moves. In the second step we have 2 moves. At the end, we would have 6 outcomes as illustrated in the picture. One (or more) of ...
0
votes
1answer
36 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
88 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
42 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
20 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
22 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 ...
2
votes
3answers
112 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
16 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
32 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
15 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
26 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 ...
0
votes
1answer
32 views

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
1
vote
1answer
37 views

How to count occurences in a Skiplist

If we have an sorted skiplist how can we count the occurences if it is sorted on a effective way? Occurence of the same element in the skiplist?
2
votes
0answers
23 views

Efficient concurrent recalculation of a dynamic subset of nodes & their dependencies in a directed acyclic graph

I'm dealing with a directed acyclic graph representing calculation steps. Imagine it as something like a big excel spreadsheet, where each cell is a node in the graph. A node (cell) can have an ...
0
votes
0answers
18 views

dijkstra with adjacency list and minimum heap as queue vs adjacency matrix and a normal array as "queue"

Which one should be faster? I have written a script comparing both run time, initially the implementation with adjacency list and minimum heap performs faster, but as the number of nodes/edges ...
0
votes
0answers
20 views

using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
0
votes
0answers
32 views

Is the length of the longest balanced parentheses in )()(())()()))())))( 10 and not 12?

In Skiena, S.: The Algorithm Design Manual 3rd Ed., Exercise 3.2 reads as follows Give an algorithm that takes a string $S$ consisting of opening and closing parentheses, say )()(())()()))())))(, and ...
1
vote
1answer
20 views

One-tape Turing machine for doubling words (strings)

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape ...
2
votes
0answers
32 views

Simple efficient algorithm for dynamically maintaining max of special linear functions

Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$ \max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\} $$ in response to ...
1
vote
1answer
88 views

In search of finding an idea that work in $o(n^3)$

Suppose given an array $A[1..n^2]$ that contains positives real values. Also we have a black box that have two input numbers $a,b$ and return true or false, also i know that, for any input, the black ...
1
vote
1answer
22 views

How can you apply dynamic connectivity problem to digital photos?

I started learning DSA recently and I came across the Dynamic Connectivity Problem. One of the listed real-world applications of the Dynamic Connectivity Problem is "pixels in digital photos.&...
2
votes
1answer
28 views

Quadratic probing variant scheme

Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set $\{0, 1, \dots , m-...
1
vote
1answer
39 views

Solving permutation Mastermind

This question is inspired by a recent (imo bad) TV show in German television. Given two finite sets $A$ and $B$ of same size (representing two groups of people) and a bijective map $m \colon A \to B$ ...
0
votes
0answers
16 views

A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining

I would to discuss a proof found in CLRS book please. Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
1
vote
0answers
43 views

Finding optimal path for a reproduction problem

Given a finite set of lists with elements ($e_1, e_2,..., e_7$) and $e_i = True, False$. It is possible to create a new list by taking two lists and apply the $\land$ operator on both lists ($e_i$ in ...
0
votes
0answers
40 views

Gas Station problem proof

I'm trying to prove the solution for the problem Gas Station (LeetCode 134) Let's define $d_i$ to be the difference $g_i - c_i$. Basically it's a greedy solution where you look for the first $k$ s.t. $...
0
votes
1answer
53 views

A question about euclidean graph

I have an Euclidean graph $G$, but i should changes the weight of some edge of $G$ to $+\infty$. My problem is, after this change, $G$ remain Euclidean graph or not?
1
vote
2answers
35 views

Algorithm to get maximum value of tuples from two sets

I have two sets A and B. Each tuple from A x B has a score associated to it. E.g.: I: (A1, B1) -> 5 II: (A1, B2) -> 7 III: (A2, B1) -> 3 IV: (A2, B2) -> 4 I now want to get the ...
0
votes
1answer
48 views

How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?

I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the ...
-1
votes
0answers
44 views

single-tape Turing machine

I am reading an introductory text on Turing machines( https://en.wikipedia.org/wiki/Turing_machine) and I have some questions. The first one is the following: Prove that there is a single-tape Turing ...
0
votes
1answer
43 views

What does x sign mean in functions

I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
0
votes
1answer
56 views

Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank

Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) : In this challenge, you will be given an array $ B $ and must determine an array $ A $ ....

1
2 3 4 5
199