Stack Exchange Network

Stack Exchange network consists of 174 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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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.

0
votes
0answers
10 views

Is it possible to solve maximum weight independent set in linear time for a cycle?

Given a cycle of $n$ vertices and each vertices of the input graph $G$ assigned a weight. We want to find an independent set of cycle such that weight of the vertices taken in the independent set is ...
2
votes
2answers
24 views

Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you ...
-3
votes
0answers
21 views

knapsack problem

i have a question for the knapsack problem that i am totally not able to comprehend properly. I know how to knapsack works with the 0-1 approach and fractional. kindly can i be helped with this ...
1
vote
1answer
29 views

Proof of correctness of reversal algorithm for array rotation?

We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}. ...
-1
votes
0answers
45 views

Shell sort vs quick sort, which is better?

Referring to this website : Toptal This website is confusing me, on clicking on play all, website starts to play animations of all available algorithms sorting the given arrays, which shows shell ...
0
votes
0answers
7 views

How to determine R-Tree MBR Nodes?

I understand the concept of an R-Tree and how it is used to spatially index and store geometric objects such as polygons and points, but I am not sure how to construct it by choosing MBRs that group ...
1
vote
0answers
25 views

Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
1
vote
1answer
49 views

Split graph in two parts, such that most nodes have even number of edges

We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between ...
17
votes
5answers
4k views

What does a faster algorithm mean in theoretical computer science?

If there is an algorithm running in time $O(f(n))$ for some problem A, and somebody comes up with an algorithm running in time, $O(f(n)/g(n))$, where $g(n) = o(f(n))$, is it considered an improvement ...
1
vote
1answer
41 views

Dijkstra Partitioning Algorithm : Special Case

I have been exploring Dikstra partitioning Algorithm. Below are my given: R = Red W = White B = Blue I have this unpartitioned array. ...
-1
votes
2answers
44 views

what is the expected number of comparisons made before the algorithm terminates?

How to approach this question ? I have no idea regarding the method to be applied for solving such kinds of problems .
3
votes
1answer
43 views

Merge sort worst case running time for lexicographical sorting?

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
0
votes
0answers
30 views

$k$ -center with outliers - but the points are on a line

The classic $k$-center with outliers problem is NP-hard and there exist approximation algorithms to solve it. However, what if we assume that the input point are on a line, rather than in an ...
-1
votes
1answer
41 views

How to construct a branching program for this function?

Suppose we have a formula $F(x_1,x_2,x_3) = x_1 \vee (x_2 \land x_3)$. $F$ outputs 1 when it has a satisfying assignment and 0 otherwise. How can I convert the above formula(or any formula like this ...
1
vote
0answers
29 views

Counting subarrays where each number either doesn't occur or occurs odd number of times

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times. ...
1
vote
1answer
34 views

Candy Problem for k size window

I was solving this problem and end up learning two ways to solve this problem. One is two pass method and the other is considering peak and valleys (candies - interviewstreet). Both of these are O(n) ...
2
votes
1answer
62 views

Is my interpretation correct?

I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for recommendation systems. This is the algorithm: These are the necessary definitions for ...
1
vote
2answers
31 views

Time complexity of set intersection

This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below). Problem 1: The input is a positive ...
1
vote
1answer
22 views

Recurrence Substitution Method with multiple givens

Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$ Given $T(0)=3$ and $T(1)=5$ I kind of understand it with only one given and one recurrence call by expanding the call using what is ...
3
votes
1answer
44 views

FPTAS definition

I read that a fully polynomial time approximation scheme (FPTAS) has time complexity polynomial in the input size and also polynomial in $1/\epsilon$. However, this leaves some ambiguity. For example,...
3
votes
2answers
51 views

“Which complexity represents a majority of algorithms?”

Student asked me this question. During lectures on algorithm complexity I've shown similar picture (source): After I've explained and gave examples for each category, a student asked: "Which of these ...
1
vote
1answer
38 views

Book recommendation for algorithms

I'm a software engineer having a master degree in software engineering. I've been coding for 8 years (2 years full time job). But I feel like I have forgotten the fundamentals of algorithm and theory ...
1
vote
2answers
38 views

Does this constraint satisfaction problem have a name

I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution. The problem is: I am making a card-...
1
vote
1answer
27 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
3
votes
2answers
104 views

Is there a name and efficient algorithm for this Tree Traversal method?

Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks. I want to traverse this type of ...
2
votes
1answer
229 views

Why is this n^2 growth?

I am attempting to understand the growth of the following algorithm, which is described as $n^2$ growth in the book I am reading: "... performs of the order of $n^2$ steps on a sequence of length $n$....
2
votes
1answer
23 views

Edit distance for huge strings with bounds

My question is simple but I don't know if the answer is. If you have two strings of length 10 million each, is there an algorithm that would allow you in practice to compute their edit distance (...
4
votes
1answer
51 views

Applying a permutation on a sequence with multiplication

We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if ...
1
vote
1answer
10 views

Matching two lists of different sizes with exceptions?

Suppose that I have two lists of numbers (which represent IDs for rows in a database): list1 = [1, 4, 7, 8] list2 = [2, 3, 5, 6, 7] I would like to write an ...
5
votes
1answer
34 views

Hindley-Milner type inference for language with implicit type casting

I've only implemented the HM algorithm on a small academic language with a few primitive types and functions. In that case, the unification algorithm would return a type error if two different ...
0
votes
0answers
18 views

Implementation of the PageRank algorithm

I have a question concerning the implementation of the PageRank algorithm In this video Victor Lavrenko explain that the value of the page rank should be pulled from the source to the target ...
6
votes
1answer
97 views

Does there exist a travelling salesmen generating algorithm?

I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling ...
4
votes
1answer
430 views

Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

Motivation: Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any ...
4
votes
2answers
28 views

Determining the existence of a forced win vs determining the best outcome

A large body of work looks at the computational complexity of games. In particular, identifying a forced win from a given position. Is this problem equivalent under polynomial-time reduction to ...
1
vote
0answers
22 views

Order list of dependent calculations

I'm working on an application where the user can add 'calculation' fields to a page. Every calculation field is dependent on x amount of 'number' fields and 'calculation' fields. If calculation field <...
2
votes
1answer
20 views

Best algorithm for splitting up departments such that the least unique ones are assigned per day

I have a collection of people who need to be assigned to one of 10 dates. Each person is in a specific department. The departments have vastly varying amounts of people (from ten to thousands). Each ...
1
vote
0answers
29 views

distinguishing two biased coins

I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
0
votes
0answers
22 views

Extended stars and bars approach using dynamic programming

If we have an equation with N variables of the form x1 + x2 + x3 +...+ xN with sum S, and upper and lower bounds for each of the N variables, is it possible to find the number of integer solutions (...
6
votes
0answers
116 views

Testing algorithm for a modified sieve of Eratosthenes

Context: I am looking at a modified version of the sieve of Eratosthenes. I started by generalising Eratosthenes' sieve, like so: Choose some starting "root", $n_0\in\mathbb{N}$, a sieve limit (the ...
3
votes
2answers
121 views

Skip List estimate number of elements less than (or greater than) a value

I am looking for a thread safe data structure where an element can be searched in $O(\log n)$, for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,...
1
vote
3answers
58 views

Algorithm to compute maximum of blocks

We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total). One algorithm is to compute the ...
-1
votes
1answer
28 views

Book example Profit maximization understanding [closed]

This may not be the right place to ask this kind of question and it also sound a bit stupid, but please help me understand better. I am not able to to see why on page 192 "which imposes another ...
3
votes
1answer
22 views

Best algorithm to make a smooth route through a raw set of GPS-points with some errors?

We're developing a mobile application where one of it's functions is tracking user driving route. The app simply pushes GPS-coordinates to the server, which stores them into a route. Then we need to ...
3
votes
2answers
294 views

Time Complexity to find height of a BST

Below is a question I was asked in an Interview What is the best case time complexity to find the height of a Binary Search Tree? I answered it explaining using the below algorithm $\mathrm{...
1
vote
1answer
26 views

what is the significance of the word “Sub-problems” in Greedy Method?

With respect to Dynamic Programming we make a statement that : Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then ...
0
votes
1answer
45 views

A question about a variant of a knapsack problem

I have the following problem: Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
2
votes
1answer
30 views

How to find the optimum solution of Weighted set cover in O(2^n)

A weighted set cover problem is: Given a universe $U=\{1,2,...,n\}$ and a collection of subsets of $U$, $\mathcal S=\{S_1,S_2,...,S_m\}$, and a cost function $c:\mathcal S\to Q^+$ , find a minimum ...
0
votes
1answer
29 views

Comparing variable image to static image

What are Levenshtein distance algorithms, but for images? I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created) For example, ...
1
vote
1answer
18 views

Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching. However, I am using python-graph-tool, which only has max-cardinality ...
1
vote
1answer
26 views

Median of two sorted arrays of different size in logarithmic time?

The solution given in Cormen is as follows: Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary ...