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

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.

0
votes
0answers
27 views

Dijkstra’s shortest path algorithm

I'm learning about single source shortest path algorithms and need to clarify few doubts- Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers. Does ...
-1
votes
0answers
53 views

Destroy the graph in minimum number of steps [on hold]

$G$ is a directed acyclic graph with $N$ vertices and $M$ edges. The aim is to destroy the graph - by deleting all of its vertices in minimum number of steps. For each step following rules must be ...
0
votes
2answers
41 views

How to analyze the worst case of weighted quick-union method on union-find

Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne. Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial ...
0
votes
1answer
40 views

Minimum number of scenarios to run to fully test a page

I run a testing application that, using Selenium, runs testing "scenarios" each of which visits a bunch of pages on a website. Each page is modeled by a Java file that contains locators, each of which ...
-1
votes
0answers
21 views

Graph transformation

Problem: Given two undirected graphs (A and B) determine if graph B can be obtained from graph A by adding new nodes (possibly 0) and new edges between this new nodes or new edges between new nodes ...
-1
votes
0answers
11 views

Regarding Metaheuristic algorithm

I have a confusion regarding meta heuristic algorithms. I am currently looking at Sine Cosine Algorithm(SCA). I am trying to combine it with K means algorithm. Does metaheuristic algorithms calculate ...
1
vote
0answers
21 views

directed edges in an undirected graph [duplicate]

Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even. For example, consider a graph ...
2
votes
2answers
23 views

When are you supposed to eta-reduce?

Wikipedia lists the following algorithm for normalizing a lambda calculus term $t$: If $t$ is not in head normal form, beta reduce the beta redex in the head position to get $t'$. Then normalize $t'$ ...
-1
votes
0answers
19 views

Banerjee's Test

I have a few questions about Banerjee's test. what is Banerjee's Test, and is it related to the GCD algorithm if the answer is yes how? And what is the benefit of using it in dependency analysis, and ...
0
votes
0answers
13 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
-1
votes
0answers
18 views

Any code/algorithm/paper for video smoothing?

I've implemented on a third party software the NVidia Optix Denoiser but it has problems with animations yet since it introduces a small flickering so introducing a temporal smooth could be a nice ...
1
vote
1answer
39 views

Distinct Minimum Weight Spanning Trees

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider ...
0
votes
0answers
15 views

What's a good clustering algorithm to form a consensus definition of a word?

For example, if I had a list of different definitions for the same word, how can I use semantic clustering to form a consensus definition? What's the best algorithm?
1
vote
1answer
24 views

Running time in FPT

For a certain parameter $k$, is the algorithm with the running time of $O(k.n^{\log{n}})$ in class $FPT$? I would appreciate if you can kindly guide me through.
0
votes
0answers
12 views

Digitalize the endpoints (10, 18), (15,8) using Bresenham’s algorithm [on hold]

If there are any other example for Bresenham's regarding negative slopes ?
0
votes
0answers
21 views

“Spring” vs FFT spacial to frequency domain?

Before I found out about FFT https://m.youtube.com/watch?v=spUNpyF58BY but having seen and been impressed by spectrograms/sonograms, I developed my own algorithm for converting to the frequency domain ...
-1
votes
0answers
25 views
-1
votes
0answers
23 views

Writing a recurrence

I do not understand this problem. Please help me solve it, but also explain what is happening. I missed it completely on a HW assignment You are researching the size of the crowd at the US ...
2
votes
1answer
23 views

Variant of interval scheduling (multiple machines with given availability)

I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
0
votes
1answer
15 views

Parallel Algorithm for Data Averaging

I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
2
votes
1answer
64 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
0
votes
0answers
17 views

Fantasy sport points scoring

I have car racing game consisting of six teams of 2 cars making 12 cars per race, all twelve cars will compete in each race and score points based on their finishing position. The league will be six ...
1
vote
1answer
67 views

What is the optimal way to solve the following optimization problem

You are given a function $F$, which can take one or more positive integer operands. Let $L=\{a_1,a_2\ldots a_n\}$. We need to compute the function $F(L)$ using the least number of transformations/...
0
votes
1answer
14 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
0
votes
0answers
36 views

Fast Boolean minimization

Two level boolean logic minimization(AND, OR, NOT) for big number of variables,(say n) is time consuming. I want to minimize an n variable sum of Product form boolean expression efficiently where n ...
1
vote
1answer
48 views

What is the optimal way to perform GCD chain operation?

Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming. Similarly ...
2
votes
0answers
48 views

What is the relationship between “model of computation” and “algorithm”?

Traditionally, the usual definition you find for model of computation is "an abstract description of how an output is computed given an input" (Wikipedia and my TCS course are my sources, but the ...
0
votes
1answer
29 views

How can I find an object with a certain property value in a recursive branched nest of objects?

In my example, all objects represent layouts with arrays of components where components can have arrays of components themselves. A component does not always have an array of components and it also ...
1
vote
1answer
12 views

Approximation factor shorthand clarification

I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation ...
1
vote
0answers
20 views

Determining a value in an algorithm on its first run

I was given the following algorithm as a solution to one of my problems. However, I am baffled at understanding how c' is ever initialized. The first if statement can never be reached, as c' is never ...
3
votes
2answers
78 views

Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]

Title is self explanatory. I have searched here on this site and haven't found any discussion about this. Is it somehow related to Turing's Halting problem (which is undecidable)?
0
votes
0answers
13 views

Distribution of pointer keys in a Skip-list node

Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$. We construct a skip list over the keys. Now if I pick a key (e.g. 31 in the ...
0
votes
0answers
26 views

Joint Probabilistic Data Association Filter (JPDAF)

I am trying to learn about data association algorithms, and I came across the Joint Probabilistic Data Association Filter (JPDAF). I have read about the algorithm from multiple papers, and am looking ...
-3
votes
0answers
17 views

Need algorithm to determin whether A>B>C>D expressions are legal [closed]

I need to define function parameter priority, such as function Func(A, B, C, D, E) Others can write rules to define this priority, I need a algorithm to check ...
0
votes
0answers
11 views

Finding the intervals containing the query interval

Intervals are represented by two numbers, let's say integral numbers. At the beginning we have sequence of given intervals, for example [1, 5], [4, 8], [3, 5]. After that, we have sequence of queries, ...
2
votes
1answer
414 views

Direct edges of undirected graph so that all indegrees are even

Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even. For example, consider ...
1
vote
1answer
39 views

How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
-1
votes
0answers
15 views

Context free grammar to Turing Machine

I have the following problem: Draw the diagram of a TM for the language : of all binary strings of odd length with a 1 in the middle. My approach to this in CFG is as follows: ...
0
votes
0answers
25 views

Why it is important to understand when a particular problem is algorithmically “unsolvable.” How should I deal with this type of problems? [duplicate]

So I learned that there are some problems that cannot be solved in computer science but I want to know why is it important to understand the unsolvable algorithm and how should I deal with it.
1
vote
1answer
11 views

Reducing optimization problem to its decision version

There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C[a, b]$ is how compatible students $a$ and $b$ are. (1) Given an $n \times n$ compatibility matrix ...
0
votes
2answers
33 views

Sorting in a Priority Queue

Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key? I know than the priority in the queue is based on ...
3
votes
3answers
94 views

Undirected graph with exponential number of simple cycles

Hey I am new to graph theory and this question has me stuck for hours. What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n. I was looking at ...
0
votes
0answers
7 views

8 puzzle admissible heuristic where tiles are in correct position

For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once. But ...
1
vote
2answers
59 views

Smallest possible sorting network for given permutation

I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x_1, \dots, x_n$. The solution should not be a general sorting network that sorts every ...
0
votes
0answers
17 views

Feasible algorithm to find interpolating complex polynomial based on absolute value

Consider a complex degree-$(n-1)$ polynomial $p(z) = \sum\limits_{i=0}^{n-1} a_i z^i$. Given a number $0 > m > 2n$ of positions in the complex plane with absolute value requirements, i.e. $|p(...
0
votes
0answers
13 views

Find the direction of monotone polygon (if exists) in linear time

Implement a program that checks if there is a direction in which a simple polygon is monotone and,in that case, reports such a direction. Upper bounds: O(n) time, where n is the size of the ...
0
votes
2answers
36 views

Shortest distance from multiple points to one point

I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
0
votes
1answer
44 views

Counting the number of multiples of number A that perfectly divides the number B

What is the best way of counting the number of multiples of number A that perfectly divides the number B. This is the sub problem for one of the questions I am solving on codechef. This is the best I ...
0
votes
0answers
20 views

Aproximation of longest path in undirected graph from given point

I'm looking for a algorithm suitable to find possibly the longest path (by count of nodes) in given undirected graph and starting node in some time resime. Is there any know algorithm for that?
0
votes
0answers
13 views

Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times

A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s. for eg, n=3, m=3, ...