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
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
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
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
20 views

Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition". My course ...
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
25 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 ...
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
3answers
58 views

Minimum index Array Product

Given an array A(1 indexed based) of positive integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(...
-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 ...
1
vote
1answer
35 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. ...
0
votes
1answer
33 views

How to move spheres in 3d without collision

Is there an algorithm that gets as an input 2 arrays (arr_origin, arr_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to ...
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
94 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 ...
0
votes
0answers
39 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&...
1
vote
1answer
48 views

Finding efficient randomized algorithm

I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve. Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ ...
0
votes
2answers
84 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 ...
2
votes
1answer
46 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 ...
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: ...
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 ...
2
votes
2answers
72 views

How can I solve this problem using dynamic programming?

I'm stuck in this problem and I would need some help: Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. ...
4
votes
2answers
127 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
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 ...
2
votes
1answer
56 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 ...
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}, (...
5
votes
2answers
120 views

If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
1
vote
0answers
14 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
39 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. ...
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 ...
1
vote
1answer
13 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 ...
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: ...
1
vote
1answer
35 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 ...
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 ...
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: ...
0
votes
1answer
38 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, ...
2
votes
2answers
80 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
3
votes
2answers
183 views

Invariant on “Find K Closest Elements” problem

I run across this problem: Given a sorted array, two integers k and x, find the k closest ...
5
votes
1answer
86 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
-1
votes
0answers
47 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 ...
2
votes
1answer
34 views

Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it. Python starts from the end of the array to the start. Looking at the algorithm I didn't see any ...
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 ...
1
vote
1answer
64 views

Divide a number in k powers of 2

Example N = 9 and K=3 4 + 4 + 1 = 9 . What I have tried. We can not go on dividing with 2. We can use unbounded knapsack with array elements from 2^0 to 2^32.
5
votes
3answers
758 views

Maximum set packing and minimum set cover duality

I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the ...
0
votes
2answers
32 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 ...
7
votes
3answers
13k views

What is “rank” in a binary search tree and how can it be useful?

I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me. What I have ...
1
vote
1answer
35 views

Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows: ...