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
1answer
483 views

A O(n) algorithm for a point set triangulation

I'm currently stuck at the following task: Consider a point set $S = \{ p_1, p_2, ..., p_n \}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have ...
0
votes
1answer
352 views

Using AI / Machine learning to find the most time and space efficient solutions to an algorithm [duplicate]

As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms. Is it forseeable in the future that we have languages or techniques such as AI/...
0
votes
0answers
241 views

Egg dropping problem

Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...
0
votes
1answer
466 views

Why BFS is source vertex specific? [closed]

Take a graph $G=(V,E)$ . As we know both DFS and BFS are graph search algorithms . But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not ...
0
votes
0answers
62 views

2-sat and vertex cover [duplicate]

I've been recently dealing with the classical problem of finding the minimum vertex cover in a bipartite graph. The common approach is to set direction to all edges and run DFS from all vertices of ...
0
votes
1answer
221 views

Quicksort bounds

I found an implementation of Quicksort here, and now I cannot understand why it works with those left and right bounds. Right now the link above is unavailable due to some problems with their hosting ...
0
votes
0answers
307 views

Analyzing the time and space requirements of a Most Significant Digit first radix sort algorithm

In a previous question of mine, I asked how efficient is the Least Significant Digit first radix sort algorithm for sorting 32-bit integers. It turns out that the bounds are: Time: $ \Theta (\frac{32}...
0
votes
1answer
215 views

Array accesses and basic operations

I was looking through some lecture slides on algorithm analysis and found that in general an array access counted as a basic operation, but it did not seem to count as one when accessing the first ...
0
votes
1answer
96 views

For each $i$, find minimal $j>i$ such that $A[j]>A[i]$ [closed]

I have the following problem: Given an array $A$, I need to construct an array $B$ such that $B[i]$ is the minimum $j>i$ such that $A[j]>A[i]$, or Null if no such $j$ exists. For example,...
-1
votes
1answer
2k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
-1
votes
2answers
120 views

Find the index of the next greatest element in the array

I know there is a stack based approach with O(N) complexity and O(N) space. Can B be created using O(1) space? Such as in place using a single loop or even some sorting algorithm ? If so, can you ...
-1
votes
1answer
1k views

What is the fastest way to check if an integer is divisible by another?

What would the Big O be? Can something like this be done in O(log(n)) where n is the number of bits?
-1
votes
1answer
271 views

Custom binary counter supports only increment in $2^i$ values amortized analysis

I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the ...
-1
votes
1answer
149 views

Implementability of a (abstract) data structure/type? [closed]

Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a (...