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

Is correctness implied by an optimality proof?

New to proofs (in the context of analysis of algorithms). I'm wondering, if I were to prove a greedy algorithm is the optimal solution, does this imply its correctness as well? (partial correctness + ...
0
votes
1answer
20 views

Best split with conditions

Given this sort of dataset: ID Score1 P1 Flag id1 0.01 0.2 False id2 0.99 0.9 True ... ... ... ... The limitations of each variable are: ID: identifier if each object, unique in the table Score1:...
2
votes
0answers
32 views

Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)

We have an algorithm problem in hand, can you please write your ideas about this, thank you! There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
0
votes
2answers
39 views

Is every problem with an output's size that grows polynomialy np?

I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$? My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic ...
0
votes
0answers
26 views

Proof of Correctness Request for Greedy Algorithm that solves “The Weight Job Scheduling” problem

Today, in my self-lead studies, I found out about greedy algorithms, more specifically, a greedy approach to solve The Weighted Job Scheduling Problem. I understand how the solution is implemented but,...
1
vote
1answer
32 views

Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$ $$ f(\mathbf{x},n) = \sum_{\sigma_1,...,\...
1
vote
2answers
69 views

Efficient way to find key points on spline to approximate it with line strip

Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the ...
0
votes
0answers
12 views

Research on Tree Automata/Tree Transducers for implementing Tree Generators

I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
2
votes
0answers
38 views

Median of given range of elements in a binary search tree

Given a range [l, r], we are supposed to find the median of all the nodes that are present in the binary search tree and whose values are within l and r. Let me take an example. Let the BST be the ...
4
votes
1answer
173 views

Randomly selecting element from data structure, probability based on weight

I have a list of elements, each with an id and a weight. A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as ...
2
votes
2answers
36 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

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$. Furthermore, ...
0
votes
1answer
28 views

Sort an array in specific bounds [duplicate]

Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$] I will need ...
1
vote
1answer
48 views

Meaning of “number of keys in the range $a$ to $b$” [closed]

Regarding this question: You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$. Suggest a data structure that allows to answer in $O(1)$ steps the number of ...
0
votes
1answer
23 views

Converting Binary Search Tree into Decreasing Ordered Linked List

Given a BST with n nodes, the algorithm should create a linked list that contains a decreasing order sorted array. The algorithm should have a worst case time complexity O(n). The signature of the ...
3
votes
0answers
49 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$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
1
vote
1answer
46 views

An algorithm that finds ord(a) in $O(\log n)$

Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^*_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$). I ...
0
votes
1answer
33 views

Solving a CSP using AC-3

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 ...
2
votes
2answers
95 views

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

Summary I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.) Normally, when attempting to add an edge to ...
1
vote
1answer
24 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 -&...
3
votes
1answer
37 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 ...
1
vote
2answers
230 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
20 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
44 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
1answer
16 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 ...
0
votes
1answer
37 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
23 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
23 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
19 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 ...
-1
votes
1answer
84 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
33 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
12 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
54 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 ...
2
votes
2answers
128 views

Edge exchange property of two Minimum Spanning Trees

Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T' Then I want to prove ...
1
vote
0answers
27 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 ...
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
vote
2answers
74 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
55 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? [duplicate]

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
28 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
53 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
36 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
22 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
1answer
59 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
21 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
31 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. ...