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
0answers
6 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer n and a finite list of distinct positive integers ds, ...
0
votes
0answers
7 views

An algorithm that finds ord(a) in log(n)

Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p*2^k$ and $a∈Z^*n$, I should suggest an algorithm that will find the $order(a)$ in polynomial time of $O(logn)$. I showed that if $n$ is the above so $φ(n)...
-1
votes
0answers
12 views

Dry run AC-3 on a CSP problem

Peter (P), Mary (M), Otto (O) and Dicky (D) would like to rent an apartment house. The house has three floors: G/F, 1/F, 2/F. Every floor has only one apartment. P, M, O and D must be assigned to ...
0
votes
0answers
25 views

Quicksort: upper bound on comparisons for single element

Assume we want to use quicksort on some array $S$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)}, S_{(2)}, \dots, S_{(n)}$ be the sorted order of the elements in $S$. ...
1
vote
0answers
36 views

DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Summary Normally, when attempting to add an edge to a DAG that would cause a cycle, you instead detect the situation and abort. I'm seeking an algorithm that will instead add the edge and modify the ...
0
votes
1answer
19 views

Measuring the length of a “loop” in a linked list in $O(n)$ Time?

I have been given a linked list in Python. At some point, one of the nodes is linked to a previous node creating a "tail" and a "loop": Node1 -> Node2 -> Node3 -> Node4 -&...
2
votes
1answer
25 views

What's the runtime complexity of this algorithm for breaking up string into words?

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to ...
0
votes
2answers
204 views

Why is there no “traditional”-mathy way to describe the general algorithm and give a more math-friendly definition of algorithm?

Why is there no algebraic definition of algorithm besides recursive functions? If I'm wrong, what is the matheist definition of algorithm that you've ever seen in a paper and can you provide a link? ...
0
votes
0answers
18 views

K Disjoint Triangles [closed]

Given an undirected graph G and a parameter k, the task is to decide if there exists a collection C of k vertex-disjoint triangles. We need to create a randomized algorithm in O*(n^(3k))-time. The ...
0
votes
0answers
16 views

How to find the LCP of string pairs in a set

I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, ...
1
vote
1answer
34 views

Minimize sum of $w_i(y_i-y)$ given $|y_i-y| \leq 4w_i$

Given numbers $y_1,\ldots,y_n$ and $w_1,\ldots,w_n > 0$, find $y_c$ which minimizes $$ L = \sum_{i=1}^n w_i (y_i - y) $$ under the constraint $|y_i - y| \leq 4w_i$. How to proceed?
0
votes
0answers
8 views

How to sample Bivariate Normal Distribution with Accept reject method

I have to write python code in jupyter due to sampling bivariate normal distribution with 3 sampling methods: Prior Sampling Gibbs Sampling Rejection Sampling I have done the first two samplings and ...
-2
votes
1answer
30 views

Maximum weight matching with cardinality constraint

Suppose that $G$ is an edge-weighted graph and $k$ is a positive integer. Give a polynomial-time algorithm for computing a maximum weighted matching $M$ in $G$ subject to $|M| < k$.
-3
votes
0answers
24 views

Two weight functions but different MSA

Give an example of a digraph D = (V; A), a root r, and two weight functions w1 and w2, such that w1(e1) < w1(e2) if and only if w2(e1) < w2(e2), for every e1, e2 in E, yet the minimum-weighted ...
0
votes
1answer
29 views

Multiplying two bivariate polynomials using FFT

Consider two bivariate polynomials of degree at most $n − 1$ in each variable: $$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^iy^j \quad\text{and}\quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^iy^j $$ Show how ...
0
votes
0answers
22 views

Calculate math function depend on N value

I have method with the following prototype : R[] = method(k,n) which : ...
0
votes
0answers
20 views

Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
0
votes
0answers
12 views

Algorithm for dividing works into threads by priority

TL;DR Is there an existing algorithm for dividing W works each with priority P using T ...
0
votes
0answers
11 views

Alter Sankoff's Algorithm to give all optimal solutions

I'm trying to find a way to alter the Sankoff's Algorithm so it will trace back all the optimal solutions and not only one. Is it possible?
1
vote
1answer
63 views

Minimizing sum of $w_i(y_i - y_c)$ over $y_c$

A person wants to connect $n$ circuit points to the clock signal. Now, the clock signal is going to pass parallel to the x-axis and all those circuit points are going to be connected by vertical to ...
0
votes
1answer
40 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
0
votes
1answer
31 views

What's the name of this packing problem?

I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping. For example if I have these intervals: ...
0
votes
0answers
11 views

Algorithm to calculate the period where cumulative days within a rolling period exceeds a threshold

I'm struggling to think of the algorithm to transform one data set to another. The problem I'm looking at is creating a dataset of periods of time where cumulative days absent within a period (eg 30 ...
0
votes
1answer
43 views

Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here. As highlighted by the lack of a 7*2^64/8 term it is not ...
1
vote
2answers
52 views

Minimum Spanning Tree (MST) in graph?

Note: the provided answer doesn't really answer my questions, I am still looking for help. Given an Undirected graph G with with weight on its edges and 2 ...
1
vote
0answers
25 views

Sparse tables as prefix sum data structure

I am trying to understand how a sparse table can be used as a prefix sum data structure for a bit vector. In the screendump below 1 the article [2] very vaguely describes how to use a sparse table ...
-3
votes
0answers
12 views

Rod Trip Problem [closed]

You are going to Europe by road! Wow. And its one single road (wow!). You start on the road at distance 0. There are many stopovers on this roads and these are located at distances . You are driving ...
0
votes
0answers
32 views

Algorithm for associating track ids

Hello Computer Science stackexchange, I am trying to make an object tracking system. I have a module for object detections which feeds into a object tracking module. However, due to objects sometimes ...
-1
votes
1answer
28 views

Placing k Queens in a board, recursive problem

This is my first post here, Im a math student and I just took my first computer science course (introduction), so I apologize in advance if I'm asking something in a way that is not acceptable here. I ...
1
vote
2answers
66 views

Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A. Are there ...
2
votes
1answer
43 views

How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time?

Without the unknown $\lfloor \sqrt n \rfloor$ elements this question wouldn't be hard. After a long time trying to solve the question, the best partial idea I have is to use Radix sort for the $n-\...
1
vote
0answers
26 views

Combining insertion/deletion operations in Levenshtein distance

Considering the definition below (with $d$ as distance, $w$ as operation weight/cost and $m$, $n$ being the string lengths), the operations $del$ and $ins$ seem to represent pretty much same thing ...
0
votes
1answer
20 views

Finding values in a space that matches a relational query

Assume we have 26 vectors ${A,B,C,....,Z}$ all have 1 million integers. given a query: $$ \vec{query} = (r_a, r_b, r_c, ..., r_c) $$ I want to find a match vector $\vec{m_{1 \times 26}} = (a, b, c, ......
0
votes
1answer
27 views

What is the right data structure for MST in a stream

In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm: ...
3
votes
1answer
44 views

Algorithm to check two binary expression trees for equivalence

Is there any known algorithm to check for equivalence of two binary expression trees over a field $\mathbb{F}$? For example for the expression $a+b = b+a$ it should return true (since $\mathbb{F}$ is ...
0
votes
1answer
23 views

Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?

The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS. Problem 7-1.b Hoare's partition algorithm from the book. Part b: Assuming the subarray $A[p,...
0
votes
0answers
15 views

mark sweep algorithm

Given the codes below for Mark-Sweep Algorithm, what are the state of the live objects prior to mark and sweep phase? Reference: True - has a marked bit False - has no marked bit for each root ...
0
votes
1answer
18 views

maximal independent set on grid graph proof

I'm trying to figure out proof of maximum independent set from: this link. (1b part). And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$. Shouldn't it be other way ...
-1
votes
0answers
8 views

I have just created a program to create a heap out of the input array, but my output does not match, please point the error [closed]

#include using namespace std; int swap(int dumb ,int i, int temp) { int jigle=(dumb+temp); (dumb+temp)=(dumb+i); *(dumb+i)=jigle; return 0; } int main() { int a[6]={32,40,15,50,5,44}; int n=6; ...
-1
votes
1answer
39 views

recursive algorithm to sort children and parents based on value

Edit: I dont have CS background and I'm still studying Algorithms, so any help will count! I met this algorithm while I was in interview, I didn't know what category it falls in, and hence I was ...
0
votes
1answer
20 views

Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta

So far I've understood that because of the definition of $\Theta$, we have $c_1n^2 \le f(n) \le c_2n^2$. I'm not sure how to proceed from there.
1
vote
1answer
27 views

How to solve this max contiguous subarray sum with a twist?

How to solve the max contiguous subarray problem, where we have an addition parameter $M$, and the contiguous subarray must include both $A[M]$ and $A[M-1]$? For example, for the zero-indexed array $1,...
0
votes
0answers
28 views

Apply Quicksort Algorithm to [23,12,11,0,5,2,7,8,15,14]

I have an array, [23,12,11,0,5,2,7,8,15,14]. I choose the rightmost element (14) as the pivot and set lo = 23 and hi = 15. Then since lo = 23 > pivot = 14, I don't change the position of lo. ...
2
votes
1answer
76 views

color adjustment algorithm

Got a problem I'm not sure how to approach. I'm being given a string of text with indeterminate length, around typical "body text" size. The text is a solid color, and the background can be ...
2
votes
0answers
18 views

What is an algorithm to do this binary image segmantation task?

What I need to do is go from a binary image like this: to a segmented structure like this: because I have a program that operates on those separated line contours after. As you see, those contours ...
1
vote
2answers
117 views

Sorting by repeated reversal

Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let $\mathrm{Reverse}(A, i, j)$ be a ...
1
vote
1answer
46 views

Is there a theorem that says when an array of numbers can be searched faster than linearly?

I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, ...
1
vote
1answer
29 views

Checking the existence of a pattern in a given prefix

I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before ...
0
votes
1answer
42 views

Constructing a crown graph given an independent set

A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold: (a) The set of neighbors of vertices in $C$ is ...
0
votes
0answers
21 views

Allocating workers to jobs

A company has some workers who need to perfrom some jobs. Each job requires workers of a combination of departments and seniority. Departments : HR, Legal, Product, Development Seniority : Junior, Mid ...

1
2 3 4 5
192