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
2k views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
0
votes
0answers
52 views

Can't reach a balance in a DFS search?

Below is a question based on CLRS, about using an algorithm to reach a balance between a group of friends. I figured the best way to do this, is through the use of a DFS algorithm. Below the question ...
0
votes
2answers
456 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 ...
0
votes
1answer
644 views

Proving if a function is an upper bound

Let $f(n) = (\log n)^n$ and $g(n) = n^2$ By taking a large value, I could make out that $f(n) > g(n)$ . I want to know if $f(n) \in \Theta(n^2)$ . For proving this, I need to find out the ...
0
votes
0answers
26 views

How to decode multiple-digit gamma codes and get the gap sequence? [duplicate]

How to decode gamma code ($\gamma$ code): 1110001110101011111101101111011 and get the gap sequence? Detailed information about Gamma codes ($\gamma$ codes) ...
0
votes
0answers
1k views

Shortest Path using DFS on weighted graphs

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- Here if we follow ...
0
votes
1answer
139 views

Minimum descending stacks

Assume a randomly ruffled pack of n cards with numbers from 1 to n. Each time we pick the top card from the pack (while there are still cards) and we put them according to the following rules: The ...
0
votes
1answer
366 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
1answer
96 views

Remapping values to bias a uniform set towards a certain curvature [duplicate]

I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices. I came up with this: ...
0
votes
1answer
2k views

Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems ...
0
votes
1answer
1k views

How can, e.g., Dijkstra find all shortest paths in linear time?

As I understand one can modify BFS for unweighted graph or Dijakstra for weighted graph to find all possible shortest paths from $s$ to $t$ in linear time. But how can this be, when there are $O(...
0
votes
2answers
521 views

Algorithm analysis question in growth of functions

How would I solve the following. An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500? Can anyone help me ...
0
votes
0answers
318 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
53 views

Time Complexity of the below code? [duplicate]

here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part. What is the time complexity ...
0
votes
1answer
404 views

A special case for the subset sum problem: selecting from powers of two

Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$. (This question is ...
0
votes
1answer
99 views

Are these two algorithms the same?

An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct). If two algorithms can take the same set of inputs, and for each input, they generates the ...
0
votes
1answer
142 views

Does my Algorithm Qualify as MergeSort?

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...
0
votes
1answer
102 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,...
0
votes
1answer
537 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
106 views

Detemine if two DFA's are non-disjoint in polynomial time?

Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time. My idea is this: Let's say WLOG ...
0
votes
0answers
15 views

algorithm performance with insufficient input, part 2

In a previous post, I have asked: Generally speaking, an algorithm takes some inputs and provides some output. I would like to understand how the algorithm performs when the inputs are incomplete for ...
0
votes
1answer
961 views

Binary counter amortized analysis [closed]

This is a question I have stumbled upon in my textbook, and didn't really know how to approach: Given a $k$-bit binary counter. We have an operation Increment, which adds 1 to the counter. We add a ...
0
votes
1answer
505 views

Stable marriage problem preferential to asking side

Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning ...
0
votes
1answer
910 views

Evaluating Statements Using a Parse Tree

I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, ...
0
votes
1answer
491 views

Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident ...
0
votes
4answers
8k views

How to reverse a subarray of an array

Edit: found solution with $O(1)$ look for my answer at here I have an array of elements, and I wish to reverse the order of elements between indices $i$ and $j$. Example: Let the array contain ...
0
votes
1answer
233 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
111 views

Maximum matching blossom algorithm

https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf Why do we use blossom contrast in maximum matching? The examples that I have seen can easily be solved by just ...
0
votes
1answer
235 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
0answers
266 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
0answers
66 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
2k views

Normalizing edge weights and the effect on Dijkstra's algorithm [duplicate]

If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would ...
-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
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
1answer
150 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 (...
-1
votes
1answer
277 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
2answers
124 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 ...