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

I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between ...
1
vote
2answers
56 views

Is there a formal definition for iteration?

I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. ...
-1
votes
0answers
13 views

How to select M max Sum from N stack

We are given N stacks of variable length. We need to choose M element such that sum is maximum. example 3 3 stack a) 1 2 200 stack b) 5 10 7 stack c) 4 6 the answer will be 1+2+200 = 203 .
0
votes
0answers
27 views

Using Hoare logic to show an invariant holds or using induction?

I want to know if given a while loop: x = 0 while(x < 5){ x = x + 1 } I want to show that x (at the a ith iteration of the loop), the value of i is ...
0
votes
0answers
15 views

Is it interesting to make an FPT algorithm for a P-Space completer problems?

I have done a course on paramertized algorithms. For NP-Hard problem, Most of the researchers try to design an Fixed parameter Tractable algorithm. Let $P$ be a some P-Space complete problem. ...
0
votes
0answers
22 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
1
vote
1answer
56 views

How to remove objects from an array most efficiently?

I am wondering if I can rearrange an array faster when I would like to delete more than one object. You are given a List: 1 2 2 3 4 5 7 And now you want to delete every "2" in the list. So what I ...
1
vote
1answer
17 views

Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
1
vote
1answer
41 views

How to count all integers less than a given integer and having two contigous digits as $y$?

Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
0
votes
0answers
14 views

Review of fast 2D strip packing algorithms?

It seems to me that strip/bin packing algorithms must balance between two criterion: 1) how long it takes to perform the packing 2) how area-efficient the packing is (i.e. how minimal wasted area is)...
1
vote
2answers
18 views

Algorithm for producing array of objects according to the given distribution

I have a set of objects, and each object has (let's say) a color. Given a distribution such as: ...
0
votes
3answers
48 views

Time Complexity To find Kth smallest element in a min heap

In a min heap of n elements, the Kth smallest element can be found in? O(n) O(nlogn) O(logn) O(1). According to me ans should be O(n), say we can have a case ...
2
votes
1answer
41 views

Divide grid so that each box has only one object

Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image. I have come ...
1
vote
0answers
14 views

How can I match handwritten character segments (including the direction they are written)? [closed]

I am trying to test Chinese character production by having users draw the characters on their device. There are plenty of data models that include the character information already, so I will have ...
1
vote
0answers
31 views

Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
2
votes
1answer
44 views

How do I minimize the cost of some algorithm that performs some operation on a list?

I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
0
votes
0answers
37 views

I have a function on a computer lg(X) and how many times can X be plugged into lg(X) in exactly one second? [on hold]

If I'm given an algorithm and it has a speed of lg(X), how many times does input X get plugged into lg() to retrieve a time of exactly one second and why? I tried approaching this problem in this way,...
1
vote
1answer
42 views

How to cover given entries in a matrix with minimum number of rows and columns?

We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates. example 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 ...
0
votes
1answer
37 views

Is there a free online computer calculator that is more powerful than wolframalpha.com? [closed]

I need a calculator that accepts inputs using product notation, can compute the following, and can return the result in scientific notation: $$\dfrac{\prod_{i=1}^{3.1536\times10^{16}}(52!-i)}{52!^{3....
7
votes
1answer
289 views

Checking whether the win-loss standings of a league are possible

You're hosting a 1 v 1 basketball league with a game schedule. At the end of the league you have each player report their supposed win-loss record (there are no ties), but you want to check whether ...
0
votes
0answers
30 views

If I think I have a publishable idea on a certain problem, how do I publish and proceed? [migrated]

I'm new to research. I'm working on a certain problem that has sort of been abandoned by all researchers (as far as publications go). Anyway, I like it for its simplicity and easiness to grasp. ...
1
vote
1answer
54 views

State true or false --> x = Θ(n⁴), y = Θ(n²) therefore x/y = Θ(n²)

State true or false $x=\Theta(n^4)$, $y=\Theta(n^2)$ therefore $x/y=\Theta(n^2)$ I think the ans is true,but in the book it says false. What is the explanation? My reason for thinking it to be true ...
1
vote
0answers
53 views

Diff list with unique elements - Algorithm review

in the past few days I've been working on a diff algorithm for a UI library I'm working on. My use case only target lists with unique elements. The main goal is to find the minimum amount of ...
1
vote
1answer
48 views

Recursive Bubble Sort Complexity

I have this code for a recursive bubble sort: ...
1
vote
0answers
13 views

Generating a set of divergence-free basis

I'm trying to derive an algorithm that would generate a set of divergence-free vectors, which shall be used as basis vectors later on. Using a simple example, a 2D second-order divergence-free basis ...
2
votes
0answers
40 views

Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
1
vote
0answers
22 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given $$ a_1 X_1 + \dots + a_n X_n = b $$ where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,...
1
vote
1answer
82 views

Is there a solution set for Knuth's The Art of Computer Programming series? [closed]

Is there a solution set for the books in The Art of Computer Programming series written by Donald Knuth? I've found solutions for Concrete Mathematics using Google, but not the above series.
2
votes
1answer
49 views

Range of each building in array

I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, ...
3
votes
1answer
62 views

Efficient algorithm to simulate dealing cards from a large deck of cards?

In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i...
0
votes
2answers
41 views

largest subset of pairwise intersecting intervals [closed]

Given a set of intervals on the real line, compute the largest subset of pairwise intersecting intervals (an interval in the subset must intersect with every other interval in the subset). Design a ...
0
votes
0answers
11 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
0answers
10 views

Processing RSS content from different providers based on priority

I have multiple RSS provider URLs. Each RSS provider posts articles from time to time. Each article has a published date. Some RSS providers post more often than others. I have to go through the list ...
2
votes
0answers
33 views

When does knowing the number of solutions help (improve the running time)?

Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm ...
0
votes
1answer
41 views

Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$. For $n=1$ we ...
-1
votes
2answers
30 views

Any array takes at least log(n!) compairs to be sorted [duplicate]

I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using ...
0
votes
1answer
31 views

time complexity of Sieve of Eratosthenes

For https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithmic_complexity, why time complexity = O(n*log(log n)) ?
0
votes
1answer
50 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
1
vote
1answer
47 views

Number of nodes in Van-Emde-Boas tree of universe size u?

The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level. The height of the tree is $h = \lg \lg(u)$ ...
0
votes
0answers
30 views

Maximum Pairwise GCD of an even subsequence

I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to choose a subsequence of the array whose pairwise gcd is maximum given that the ...
1
vote
1answer
35 views

Gas Station problem : Fixed path variation

Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
0
votes
0answers
17 views

Solving sequential multi-knapsack problem

Suppose I have $n$ items, each with value $v(j)$ and weight $w(j)$, and $m$ knapsacks each with capacity $c(i)$. If I make the assumption that $w(j-1)$ evenly divides $w(j)$, then there's a nice ...
0
votes
0answers
40 views

Minimum number of moves to reach a grid point by modified knight in variant chessboard

I apologize if this is not the right board to post this question but I'm cross-posting from the mathematics board. I am dealing with a computational question that extends the question posed in https://...
1
vote
1answer
20 views

How to get to the efficient solution of a problem on buying with exchange policy

I was working through some coding challenges at hackerrank.com and got to this one. I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. ...
2
votes
1answer
96 views

How to search an almost sorted array faster than O(n) time?

Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1. Develop an efficient ...
0
votes
0answers
15 views

How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
0
votes
2answers
57 views

minimum moves for Knight on a infinite chessboard [duplicate]

You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible. I can ...
1
vote
1answer
24 views

What easy algorithms are there for calculating products of cycle decompositions?

Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade. ...
0
votes
0answers
13 views

Looking for a similar graph algorithm to generate a graph given the edges a path took

I'm looking for some help on algorithms that may help generate a directed non-cyclic graph from a list of leaf nodes and the incomplete set of edge nodes taken to get to the leaf node. For example, ...
0
votes
0answers
19 views

How is ellipsoid method a polynomial-time algorithm for LP?

I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...