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

Divide and conquer problem:sequence of integers (with possible repetitions)

I was trying to solve this problem. Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$...
0
votes
0answers
59 views

Spliting in AVL tree in $O(\log n)$ times

Suppose we are given a balanced binary search tree $T$, AVL tree, now we want split $T$ at a arbitrary node. Can it be done in $O(\log n)$? First i read following links: Split in AVL tree with ...
2
votes
1answer
159 views

Weighted binary search tree

Suppose we have binary search tree with $n$ nodes. For each node $u$ we define weight of $u$ is number of nodes in sub tree of $u$ with $u$. if ratio of weight of each internal node $u$ of right sub ...
0
votes
1answer
24 views

Bucket sort has uniformly distributed data

Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying ...
1
vote
1answer
37 views

How would I prove that the regular expression rejects string?

Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$. Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused ...
1
vote
1answer
33 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
0
votes
0answers
28 views

How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?

I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about ...
1
vote
1answer
58 views

How do Kruskal's and Prim's algorithms compare to each other?

I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in ...
0
votes
0answers
28 views

Dynamic sampling of thermal images

My master’s dissertation subject is to analyze and implement an algorithm that would sample thermal images from camera with different frequency rates to optimize database size and processing power. Is ...
4
votes
1answer
240 views

FPT algorithm for 1-BDD

Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one. Is ...
2
votes
0answers
21 views

What's an efficient algorithm to check if a binary operator is residuated?

Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in ...
3
votes
1answer
62 views

Minimum-area enclosing equilateral triangle for a point set

We have $n$ points $P$ in $2D$ space. We want to find an enclosing equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose We know that at least on side of $\Delta$ covers at least ...
1
vote
0answers
31 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
4
votes
0answers
61 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
0
votes
0answers
26 views

Grouping Algorithm By Multiple Fields

I'm looking for an algorithm that will group players from the same teams together throughout multiple matches. In my case, every team has up to 4 players in every match. Teams have subs, which means ...
0
votes
1answer
24 views

while loop for bitwise conversion program

int counter(char c){ int count = 0; while (c!=0){ if((c & 1) !=0) count++; c = c >> 1; } } I am trying to understand a ...
1
vote
0answers
45 views

Determining number of $j$ such that $b_j \le c_i$ and $a_j \le b_i$ in time $O(\log n)$

I have an array $A$ of length $n$, containing triplets (think of it as a $3\times n$ matrix). Can I re-order the array (without reordering a triplet's inner values) in time $O(n\log n)$ so that it is ...
2
votes
2answers
45 views

Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

Given a self-balancing binary search tree of size $n$, I want to perform the following operations: InsertInOrderSequentialBatch an ordered sequence of $k$ values (...
1
vote
1answer
111 views

Reductions versus generalizations

I am reading Chapter 8 NP-complete problems in Algorithms by Dasgupta et al and looking at some questions at the end of the chapter. My own questions are below (after the image with the textbook ...
1
vote
1answer
56 views

Running time of heap sort, when all number are identical

Given n numbers that all are identical, then what would be the running time of heap sort? Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?
-1
votes
1answer
53 views

Minimal modification of sequence that removes all local minima

Consider a trail as a sequence of land heights representing the elevation along the trail. A pit is any position in the trail surrounded by higher terrain on both sides. For example, in the sequence [...
1
vote
1answer
52 views

Variant of assignment problem

This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
4
votes
1answer
157 views

Changing a matrix to become an ancestry matrix

An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
0
votes
0answers
38 views

O(nlogn) or O(n) alternative for Needleman-Wunsch algorithm

So I am a computer science student and I was recently looking at the subject of comparing DNA sequences. Probably the most widely used algorithm is the Needleman-Wunsch algoirithm and while it might ...
1
vote
2answers
46 views

What is the space complexity of quicksort?

What is the space complexity of quicksort? I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\...
-1
votes
1answer
15 views

Given the following state diagram, write out its formal definition as a 5-tuple

I got these for four of them, but I can't get the transition function. Q = {q1, q2, q3, q4} Σ = {a,b} q1 is the start state, and F = {q4}
1
vote
1answer
37 views

Shortest traverse path in a matrix given the start point $(i,j)$

Given a $m\times n$ matrix and a starting position $(i,j)$, how can we find the shortest path to go through all the elements at least once if we can only move by a single unit (i.e. up, right, left or ...
1
vote
0answers
5 views

Calculate coherence for non-gensim topic model [closed]

I've built a topic model, with: Input: list of tokenized lists Output: a m x t matrix (with each cell indicating the probability of word i appearing in topic k). Output: a k x n matrix (with each ...
1
vote
0answers
17 views

Understanding Suurballe's algorithm

I have been looking at the Suurballe node-disjoint algorithm, which is illustrated here: http://www.macfreek.nl/memory/Disjoint_Path_Finding What I am a bit unsure about here is "Step 4". So ...
0
votes
1answer
34 views

Sorting n weight disks with decision tree

I was refreshing some old tests about sorting algorithms, there was a question as follow: Question: we have n weight disks with different weights and we want to ...
2
votes
1answer
38 views

Smart most recently used algorithm

Background I need such an algorithm inside an android app (home launcher) to show the recently used apps. I want to avoid simple LRU / MRU logic by combining those logics (or use an alternative if ...
1
vote
0answers
38 views

Change a matrix into lower triangular matrix

I have a matrix over integer of size (50,50). I want to know whether it is possible to exchange rows and columns in such a way so that the transformed matrix is a lower triangular whose diagonal ...
0
votes
0answers
27 views

Search in array with blackbox

Given array $A[1..n]$, and black box, and a number $x$. we want to find out a $i$ such that $A[i]=x$. Our black box have three inputs, array $A$ and at most $k$ numbers from set $S=\{1,2,...,n\}$, and ...
1
vote
0answers
20 views

Is there an official name for this tree merging algorithm?

Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values ...
0
votes
1answer
19 views

Finding max flow in a undirected graph

According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents ...
1
vote
1answer
49 views

solve a rational equation as fast as possible

I would like to find the first positive solution(if there is one) to this equation: $$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$ The simplest way I fond would be to do the following: $$ax^2+bx+c = (dx^2+ex+...
1
vote
1answer
21 views

Unix glob() function and formal language equivalence

Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, ...
6
votes
1answer
155 views

Shared Elements Algorithm

I have a problem that I am working on an algorithm for: I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets) $S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\...
0
votes
0answers
27 views

Coordinate descent for Lasso, Question about algorithm

I'm not sure why the algorithm computes $c_k$ with $\sum_{j \neq k} w_j x_{i, j}$. Why does one need to ignore the $k^{th}$ feature here? I'm not sure how this is derived. Is this the result of taking ...
1
vote
0answers
10 views

How are randomized restarts in local search 4 times likely to give bad local minima?

I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
5
votes
0answers
40 views

2-Dimensional interval scheduling problem

I have a problem that is similar to the conventional interval scheduling algorithm but it is two dimensional, so I have another metric to take into account. My dataset format: Cars with the start and ...
2
votes
1answer
20 views

Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)

I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used ...
1
vote
2answers
74 views

How does size of list in merge-sort, quick-sort, insertion-sort, matter?

We have been taught that: Insertion-sort will best work if we have a small list. Quick-sort will best work if we have a long list. Merge-sort will best work if we have a huge list. It is not ...
1
vote
1answer
257 views

Solving two party problem

There are two parties A and B going on. Some people are going to party A, some are going to party B. We are given instructions of the form different 1 3, meaning ...
1
vote
1answer
204 views

Expected running time of an algorithm

This demonstrates the limitations of considering expected running time of an algorithm as a useful measure. For any $n>0$, describe a function $f:\{0,1\}^n \to \mathbb{N}$ such that $\mathbb{E}[f]...
1
vote
1answer
30 views

Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o

New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning. If you have a given an ...
2
votes
2answers
26 views

Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm

I am trying to solve the Budgeted Maximum Coverage Problem. I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller. Both are approximation algorithms. ...
0
votes
1answer
110 views

What are the advantages of using PRNG over TRNG?

True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will ...
1
vote
2answers
49 views

Which goes first stl or data structures and algorithms?

So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions. Is it possible to ...
0
votes
1answer
49 views

How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)

If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$. For example, if we have $A = [...