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
0answers
18 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
2
votes
1answer
43 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
30 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
31 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
84 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
40 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
19 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
104 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
22 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
30 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
28 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
22 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
17 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
31 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
85 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 ...
0
votes
0answers
47 views

Algorithm for slicing multidimensional array [closed]

Given a multidimensional array of values and a slice (start:end:step) for each dimension, how to apply the slice over the array? I know both the shape of the array and how many dimensions it has (...
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
39 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
52 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
46 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
43 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
55 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 $ ....
3
votes
2answers
77 views

Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other

Problem Statement Given a list of XY coordinates of length N ( e.g. [(1,2),(3,4)] ) check if there is a subset of coordinates of length S where each coordinate of ...
12
votes
5answers
5k views

How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

I understand the textbook explanation of how to use dynamic programming to find the minimum edit distance between 2 strings but how do we get to pick the 2nd string? I don't think the entire ...
-1
votes
1answer
34 views

Proving existence of an optimal substructure for the DP problem "Equal" from HackerRank

Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank? Problem statement: My attempt: Let $ A = [ a_1,a_2,...,a_n ] $ be our ...
0
votes
0answers
36 views

Longest path in a tree [duplicate]

Given an undirected weighted tree with $n$ vertices, how can I design an algorithm that is $O(n^2)$ and other that is $O(n)$ for finding the longest path between two nodes in the tree (without ...
1
vote
1answer
26 views

How to arrive at correct preconditions and postconditions?

I read about Hoare's logic and algorithm correctness and how mathematicians prove an algorithm is correct,But I think how does one arrive at the required precondition and postcondition?(Inductive ...
0
votes
1answer
35 views

How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
-1
votes
0answers
30 views

What is the smallest value of x for which this holds?

I'm learning I/O Efficient Algorithm on Coursera and struggling on the question: Suppose we run an algorithm Alg on a machine with internal memory size MM that uses the LRU replacement policy, and we ...
0
votes
1answer
69 views

my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself) [closed]

Write best case, worst case and average case time complexity of following categories of algorithm– a. Constant time b. Linear time c. Logarithmic time d. Polynomial time e. Exponential time (this ...
1
vote
1answer
17 views

find the minimum cost conversion between currencies A and B, given a matrix of currency conversions

Given a matrix of currency conversions, find the minimum cost conversion between currencies A and B (ex. maybe min cost conversion is A->C->D->B) I was thinking of this as some sort of max ...
1
vote
1answer
43 views

Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?

In dynamic programming: 1. what is the definition of the space of subproblems? does it have a mathematical definition? 2. why is it necessary to have an arbitrary index for the subproblem to vary? To ...
3
votes
2answers
80 views

Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...

1
2 3 4 5
198