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.
7,443
questions
-1
votes
0answers
11 views
Number of swaps and comparisons in sorting algorithms
i was reading the comparison algorithms(bubble,insertion and selection). i followed this linklink1,but if someone asks what is the number of comparison and swap in these algorithms, what should i say ?...
0
votes
0answers
5 views
Solved “Generate Parentheses” using Bit Manipulation - is my algorithm faster than other known solutions?
It's a famous old question, LeetCode #22 "Generate Parentheses": Given an integer n, generate all valid permutations of n pairs ...
0
votes
1answer
16 views
Binary Search Symbol Table
Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem:
...
1
vote
1answer
22 views
Algorithm for commonalities across related objects
I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application.
The problem is give the data below (two columns) ...
-1
votes
0answers
13 views
How to know a specific coordinate on Google maps is in a road or a building?
Is it possible to know if a specific coordinate is located in road or a building?
For example, if I take this coordinate 52.5047252, 13.3569516 do I need to type it on Google and verify it's position ...
0
votes
0answers
10 views
Recurrence Formula for Bitonic Sorter Runtime
A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
0
votes
1answer
56 views
+50
Merging nodes of a DAG
I would like to merge connected nodes with a specific attribute of a directed acyclic graph.
After each merge operation, the graph should remain acyclic.
Let's say my graph contains blue nodes and ...
0
votes
1answer
41 views
Are every problems in EXP karp reducible to any EXP-Complete?
According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$...
0
votes
1answer
36 views
algorithm for correctly rounded floating point radix conversion
Is there any generic algorithm which implements a floating point radix conversion?
Lets say we have a $p$-digit FP number
$A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$
in radix $\beta$ and with $0 \leq ...
1
vote
1answer
43 views
Finding constrained random time intervals with a constrain also on their sum
I'm searching to devise an algorithm that finds a set of n time intervals with a random duration between min and max. On top of that, the total duration is also given (tot).
For example:
n = 15
...
0
votes
2answers
397 views
What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?
If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at ...
1
vote
1answer
28 views
Solving/mitigating the free rider problem without requiring identification?
Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification?
In a web system, I want to distribute exactly one virtual dollar per day to each ...
4
votes
1answer
221 views
An algorithm for a minimization problem, How to minimize the wasted length of combination of multiple items with different length and number
Suppose there is an unlimited number of pipes, each has length $x$ meters.
There is a list of requirements of pipes with shorter length than $x$. The number of these items are also given.
For example ...
6
votes
2answers
210 views
Find if a sequence of node is a result of a binary tree preorder traversal
Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence ...
0
votes
0answers
10 views
What recursive T(N) function typically can conclude the algorithm is O(n ^ 2), O(n log n), O(n), and O(log n)?
Is it true that some common forms of recursive T(n) can give the following conclusions?
When
T(n) = T(n/c) + b where c is a constant > 1, b is any constant
...
1
vote
2answers
33 views
Time complexity of finding predecessor for a dictionary implemented as a sorted array
I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it ...
0
votes
0answers
8 views
Graph with arboricity a, all verteces are marked active
So I came across this problem that I would like help solving/explaining:
We have a graph with arboricity a (can be partitioned to a min of a trees).
We run the following algorithm on the graph:
- All ...
0
votes
0answers
8 views
Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls
I have an algorithmic problem that requires some lengthy explanation, which follows below.
tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
2
votes
4answers
1k views
minimum subset of dominating 2D points
From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?
$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
0
votes
2answers
50 views
What is the official name of a specific type of combination algorithm
Say that I have the following set of variables:
[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]
The values represent a list of variables from a dataset. ...
10
votes
1answer
302 views
Shift-resolve parsing - questions
I've recently came across a paper describing the parsing technique
mentioned in the title. Unfortunately, the terminology used in said paper
is somewhat beyond my comprehension, so I've been ...
1
vote
0answers
20 views
How to implement minimization of maximum regret?
We run a report, but for one of our big clients, it is taking too long. There is a loop where it loops for a list and fetches it upstream 1by1. We're making this a bulk operation now, but some items ...
13
votes
1answer
326 views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
0
votes
1answer
58 views
Modify max value multiple times of a list
I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C_i=A_iB_i$ for each element $A_i \in A$ and $B_i \in B$.
Now I have ...
16
votes
3answers
986 views
Algorithm to test whether a language is context-free
Is there an algorithm/systematic procedure to test whether a language is context-free?
In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
0
votes
0answers
12 views
Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1
While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is :
𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1}
In overhead approach, ...
1
vote
0answers
611 views
Task scheduling algorithm (minimize wait time)
Let's say that I have one task to perform $n$, $n<250000$ times and it takes $p$, $p < 700000$ time to complete it once.
I have list of time constraints ${t_1, t_2, ..., t_n}$ where $t_1\le t_2\...
2
votes
1answer
40 views
Check if possible to perform n tasks, each between moment b(i) and e(i) and taking 1 time unit
I have such a task at university:
we have $n$ tasks, the $i$-th of them can be done between moment $b(i)$ and $e(i)$. If we decide to perform a task in moment $x$, we finish performing it in moment $x+...
-2
votes
0answers
20 views
How to create a square root program without using math library in c++ [on hold]
I need help to finish my activity in data structures and algorithms. Need help 😅
19
votes
1answer
791 views
Compression of domain names
I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
7
votes
2answers
2k views
Time Complexity analysis for Map-Reduce model
I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms.
As a ...
1
vote
1answer
18 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 ...
4
votes
1answer
65 views
Intersection of O(n) expanding circles with line from the origin
I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution.
Consider yourself as a point located on the origin $(0,0)$ of an infinite
two-...
2
votes
1answer
19 views
How to prove an implication about an upper bound mentioned in the proof of master theorem?
How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"?
For given constant b and j, the implication in green makes sense. If the upper bound of j ...
1
vote
2answers
35 views
Big-O Notation and Calculus?
I was wondering if there are any calculus relationships implicit in Big-O notation.
For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
3
votes
1answer
52 views
Problem in downvote system
Problem
For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
0
votes
1answer
32 views
What is meant by a preemptive algorithm?
The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.'
So, how does this relate to an algorithm, especially the ...
-1
votes
1answer
10 views
Recurrence Relation of Ternary search and the number of comparisons with binary search
i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
1
vote
1answer
27 views
Student Course Allocation Problem with Many Constraints [on hold]
Problem statement
In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.
$i$-th section has:
A student capacity: $cap_i$.
Two lecture timings. (Formally, each ...
5
votes
1answer
164 views
Predicting next action to take to reach a final state
Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data?
For example, a robot starts at a certain state, ...
3
votes
1answer
84 views
Building maze to maximize shortest path, may be given waypoints and teleports
How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
1
vote
1answer
20 views
Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?
Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting ...
0
votes
0answers
11 views
1
vote
1answer
95 views
Minimizing sum of recursive pairwise sums
What is the best algorithm for this?
We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
0
votes
0answers
40 views
Counting number of apples in an apple tree with given number of layers
This problem comes from a competitive programming question, and it seems to require dynamic programming.
There are several layers of apples arranged in a formation with each apple having a value ...
1
vote
1answer
23 views
What is the time complexity of a binary multiplication using Karatsuba Algorithm?
My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity.
In general, the Karatsuba Multiplication is said to have a time complexity of ...
-1
votes
1answer
117 views
Find variance within one pass
Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity?
0
votes
0answers
15 views
Design a greedy algorithm by intermingling two sequences [duplicate]
I find myself solving problems for a test and the next problem I still can't solve it.
There are n ordered sequences, $S_1$ to $S_n$. It is requested to intermingling them to obtain a single sequence,...
0
votes
0answers
18 views
How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)?
What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more ...
2
votes
2answers
59 views
What is the best way to avoid using goto statements in the pesudocode for an algorithm?
What is the best way to avoid using goto statements when writing the pseudocode for an algorithm?
I want to avoid it and use another way to replace it.
