Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
746 views

Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
1
vote
1answer
45 views

Checking if several sets of pairs covers a given set of pairs

Suppose we have $N$ arrays of pairs, e.g. for $N=3$: $A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$, $A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and $A_3 = [ [4,1], [5,1], [5,...
1
vote
1answer
98 views

Ways to implement a decision making process involving complex rules [closed]

I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with ...
1
vote
1answer
1k views

Confusion related to a divide and conquer problem

I have some confusion related to a divide and conquer problem. Here is the problem You’re consulting for a small computation-intensive investment company, and they have the following type of problem ...
1
vote
1answer
227 views

Maximum weighted disjoint set union

I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this ...
1
vote
1answer
74 views

Bit distance and disruption [duplicate]

Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question. True or false? For 1-point and 2-point ...
1
vote
2answers
73 views

Find a recurrence relation for merging of sublists of an array

There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list. My Approach Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$,...
1
vote
3answers
246 views

Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
1
vote
1answer
217 views

Efficient algorithms for finding a region in $\mathbf R^2$

This question is an extension of a previous question I've asked. Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 (...
1
vote
1answer
356 views

Can Floyd-Warshall algorithm be used in an undirected graph with negative edges?

So i know that it cannot be used if the directed graph has negative cycle, but what about the undirected graphs with negative edges? is it going to always work, or sometimes or never?
1
vote
1answer
531 views

Finding maximum-cardinality independent set with a particular oracle

We suppose we have a polynomial algorithm which receives a graph $G$ (any graph) and returns a stable set of $G, SA(G)$ with the following property: $\alpha(G) − |SA(G)| \leq k$ , for every natural $...
1
vote
0answers
64 views

Known algorithms: subgraph with highest/lowest diameter?

Let be $G=(V,E)$ a directed graph without self loops, where each node has an out-degree of at least $k$. We want to find a $E'\subset E$, so that $G'=(V,E')$ has the following properties: Almost all ...
1
vote
1answer
365 views

Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

My thoughts process: let number of elements in heap be $n$, total height of binary heap be $H$, height of node be $h$, and let number of nodes with height $h$ be $x$. Then number of nodes with height ...
1
vote
0answers
32 views

Classification with optional/catchall attributes

Context Let $S$ be a set of objects, each object $S_k$ containing a set of attributes $A_k\subseteq A$, where $A$ is a global set of attributes. Suppose each attribute $a_k\in A$ can take on integer ...
1
vote
1answer
1k views

Solve a problem through reduction

I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ...
1
vote
1answer
825 views

Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
1
vote
1answer
44 views

Number of steps in worst Case

we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or ...
1
vote
0answers
81 views

Conceptualizing a balance in a DFS traversal [closed]

I'm trying to use the concept of DFS traversal to go through a cycle, and attempt to get a balance of 0 in the end. Each student either owes or is owed some money, so I'm trying to go through all of ...
0
votes
1answer
422 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
451 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
1answer
873 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
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
174 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
51 views

Job scheduling approximation

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
2answers
2k views

Why is T not a minimum spanning tree of G?

The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.    a. True of false:...
0
votes
4answers
7k 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
431 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
2answers
383 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
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
1answer
170 views

Turn MST of G to MST of G with one new edge

Given $T$, an MST of $G(V,E)$ connected and undirected. Assume we add an edge $e'$ with weight $w(e')$. Suggest an algorithm which takes $T$ as input, and outs $T'$ MST of $G'(V,E\cup\{e'\})$.So i ...
0
votes
0answers
55 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
345 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
96 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
2answers
1k 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
278 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
0answers
23 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
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
2k views

Solving recurrence relation with square root

I am trying to solve the following recurrence relation :- $T(n) = T(\sqrt{n}) + n$ using masters theorem. We can substitute $n = 2 ^ m$ $T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$ Now we can rewrite it ...
0
votes
1answer
88 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
83 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
0answers
971 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
140 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
341 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
481 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
1answer
806 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
203 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
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 ...
0
votes
2answers
506 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
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(...
-1
votes
1answer
267 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 ...