The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
3
votes
1answer
51 views

How to answer multiple queries efficiently?

I am given a $N$-length integer array. For each integer, I am given 4 values: $$[\mathit{left},\mathit{right},t,\mathit{value}]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$ For each query, I ...
2
votes
0answers
26 views

Transit scheduling using flow networks

I am studying the maximum/minimum flow question, and was given the following problem: A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
3
votes
2answers
119 views

Maximizing sum of numbers within a sequence

Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except ...
0
votes
1answer
16 views

Time complexity of linear iteration bounded by logarithmic iteration?

I was wondering about the time complexity of something like the following loop (where work() is O(1)): ...
1
vote
1answer
23 views

Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
0
votes
2answers
44 views

Range Query with conditions

Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
3
votes
1answer
47 views

is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
1
vote
1answer
16 views

Algorithm for coherent motion. Which bus is app user on?

I am currently working on an app with a map of the city, with markers for each bus. As a feature, the phone should show which bus the user is on. To achieve this I am working on building a function ...
0
votes
0answers
26 views

What is the name of this problem (the dual of the asymmetric k-center problem)

I know $k-center$ problem is, given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of any city to a warehouse. In this ...
-3
votes
1answer
41 views

I want to solve this question for algorithm, please [closed]

Write an algorithm that calculates the monthly payment of a bank loan with a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of years to pay the loan, you can ...
5
votes
0answers
78 views

Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
0
votes
2answers
34 views

An underestimated tradeoff between Memory and the Effectivity of Computation?

Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form ...
0
votes
1answer
43 views

Guess the number from its different base representations

Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or ...
2
votes
0answers
95 views

How to query the tree?

I encountered an interesting problem based on tree-data-structure. We are given a tree which has N nodes, with 1≤N≤105. Time starts from second 1 and it continues for q seconds. At each ...
2
votes
1answer
35 views

reverse string to pattern matching

I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.: Patterns: ...
1
vote
1answer
37 views

How does the slow All-pairs-shortest-paths algorithm work?

I am trying to fully understand the following algorithm from CLRS book: I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
2
votes
1answer
47 views

Algorithm for dividing items into buckets while minimizing total weight

Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of ...
0
votes
1answer
43 views

Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

Here's the start and the vernacular I'm using. ...
0
votes
1answer
92 views

How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an ...
0
votes
2answers
86 views

number of permutation with k inversions

We are given two numbers N and K. N <= 10^9. K<=min{1000,(N*(N-1))/2} We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K. If N was <= 10^3. It would ...
4
votes
2answers
131 views

Could anyone prove why O(n^(log n)) < O((log n)^n)?

Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.
0
votes
0answers
40 views

Making change optimally

Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j&...
2
votes
3answers
164 views

Maximum number of multiples of an array element preceding it

Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$. For example, given the array 36 40 ...
1
vote
0answers
15 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
1
vote
1answer
44 views

Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
0
votes
0answers
15 views

How to compute the predecessor-subgraph in all-pairs-shortest-paths algorithm?

The following slow algorithm (implemented from CLRS book) which runs in $\Theta(V^4)$ works fine for computing shortest paths distances: ...
2
votes
1answer
59 views

find maximum sum of xors

we are given an Array Array size <= 10^4 . 0 <= A[i] <= 15 We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
1
vote
1answer
15 views

Distributed algorithm can be executed in a single process

Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency ...
1
vote
1answer
23 views

Modifying the genetic algorithm

I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm. I have 3 "areas" of optimization, say parameters ...
2
votes
1answer
71 views

Does this shuffle have non-zero probability for all permutations?

I was trying to do some code golf, when I created the following algorithm to shuffle a string: ...
0
votes
1answer
39 views

What is the sequence of numbers for N = 6? [closed]

The numbers in the table below are the result of executing an algorithm that has one parameter N, a non-negative integer, and produces sequences of integers as outputs. For values of N from 0 to 5, ...
0
votes
0answers
10 views

How to efficiently analyze schedule compatibility inside a list?

I have a list of peoples who place dates to meetings on restrained time slots. I can host X (lets say 2 for this example) meetings at the same time slot. How I can efficiently determine the ...
2
votes
2answers
90 views

Minimizing the iterative sum of pairs of numbers in a list

Given the tuple (list, value): $$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$ You may choose two adjacent values in the list to modify the tuple as: $$\left(\left[x_1, x_2, \cdots x_{i-1}, (...
1
vote
1answer
36 views

Range intersection with bounding box?

I have a lexicographical order on integer $n$-tuples, where $(x,y,\dots) > (a,b,\dots)$ if $x>a$ or if $x=a$ and $y>b$, and so on to the end of the tuple (I called it lexicographic because of ...
-1
votes
0answers
48 views

intervals in geometrical points in 2D space

Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
4
votes
2answers
129 views

How to evaluate all possible groups of adjacent tiles in 2D array?

I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain ...
0
votes
2answers
35 views

Time-complexity for basic multiplication and division algorithms

The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen. p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ ...
1
vote
1answer
30 views

Pick a random number in a pool with duplicates in O(1) time and less than O(n) space?

Imagine trying to pick a random number from a pool of numbers that contains: i1 times the number 1 i2 times the number 2 i3 times the number 3 ... etc For example picking a random number in a ...
2
votes
0answers
21 views

How to find a path in maze with navigator physical size constraints?

Assuming a 2D maze, how would one go about solving it for rigid 2D object moving through it? Additional specification: The object shape - it is a single entity, not a swarm/fleet. A shape of ...
3
votes
1answer
49 views

Greedy Heuristics with an Altered Subset Sum/Partition Problem

Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, ...
1
vote
0answers
16 views

How do I compare different optimization algorithms when step-size is unknown?

I wish to compare different optimization algorithms (gradient descent, Newton, quasi-Newton, conjugated gradient, etc) for a particular problem at hand. My main focus is on speed of convergence. The ...
1
vote
1answer
22 views

Directed graph reachability

Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?
-1
votes
1answer
59 views

question about algorithm

as you know we have equivalent condition for graphs so I want to ask a very basic question and please help me what is exactly w1(e1) and w1(e2) and w2(e1) and w2(e1) ? If e1 means path from A to B so ...
3
votes
4answers
87 views

Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people

Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons. The total value of $n$ gifts ...
-1
votes
0answers
37 views

Finding the right algorithm

I am reading the book by Petkovsek et all "A = B". I am wondering which of the algorithms would better work in order to compute (or at least estimate) the following sum: $$ \sum_{m=0}^q\binom{q-m+\...
1
vote
0answers
10 views

Image quantization for grayscale images with alpha channel

I am looking for algorithm that quantize grayscale image that contains alpha to 4-bits (16 colors). I quite like the effect that is used in IrfanView to decrease color depth, however, I dont know the ...
1
vote
3answers
59 views

Derive a while loop runs in $\Theta( \sqrt{n} )$

I know for a fact that algorithm A runs in $\Theta(\sqrt{n})$, but how does one derive that fact? Algorithm A i = 0 s = 0 while s <= n: s += i i += 1 ...
2
votes
2answers
36 views

What does the following algorithm approximate? (Assume m>1,ϵ>0)

x = m; y = 1; While (x-y > ϵ) { x = (x+y)/2; y = m/x; } print(x); The answer is m½, its the Babylonian algorithm for square roots. I understand the ...
1
vote
0answers
41 views

What is the most straight forward, easy to verify algorithm to construct a valid password from a character stream?

Let's say we are given an infinite character stream like the following: nqDoo8NkPsDn0gVf(pAI)dwa^Vq7OfAgt@KDUkjN5ZXY1yK6w7ygW6S&@L0EsUEq9... What is the most ...
3
votes
2answers
35 views

On the hardness of satisfying K number of linear constraints

Background: Normally in linear programing we have some objective function $$\text{maximize}\sum_{i = 1}^n a_i x_i $$ $$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...