Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

2
votes
1answer
33 views

Processing weighted points of interest. Is there a name for this task/algorithm?

Is there a name for the following problem? Is there a measure of quality of a given solution? How can we even define what a proper solution is? Context: I want to detect long lines (most lines over ...
0
votes
0answers
32 views

How can I find the “thinner” path from a cloud of coordinates? [migrated]

Following up with this, I have a bunch of coordinates and I draw them on a bitmap image as a coordinate system. Now, I would like to get rid of all the noise, and filter coordinates to give a "clearer"...
0
votes
0answers
12 views

Linear equation in n variables with non negative solution [migrated]

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
6
votes
1answer
44 views

Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?

Yesterday StackOverflow was down for half an hour. Later, they wrote a blog post about it, detailing that the problem stemmed from unexpectedly high complexity of regular expression matching. In ...
1
vote
2answers
71 views

Finding a match in two collections

Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at ...
0
votes
0answers
11 views

Getting speed difference between signal comparison using Dynamic Time Warping

I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed But is there a possible way to find the speed difference between the two ...
0
votes
0answers
14 views

TicTacToe Solver [on hold]

I want to find the most efficient algorithm for determining whether there is a winner on a board of tictactoe at the end of the game. Normal tictactow board dimensions are 3x3 but I need the most ...
5
votes
0answers
31 views

Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how many permutations would get rejected ...
2
votes
1answer
31 views

Working Optimization Algorithm

This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each ...
-1
votes
1answer
44 views

Stack depth for QuickSort

CLRS Problem : 7.4 How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ? Original quicksort Tail recursive quicksort ...
-1
votes
0answers
19 views

Graphical password [on hold]

I am doing a project about graphical authentication,but I can't approach to do that project because I don't get any clue how can i proceed to the next step.Hera a screen short,how can I display this ...
0
votes
2answers
46 views

Interval Scheduling Problem with Three Resources

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem. Say there ...
0
votes
0answers
36 views

How does the induction proof work in this example?

Refer to answer 1.1 of this file: http://www.dei.unipd.it/~geppo/AA/DOCS/NPC.pdf From my understanding and this thread, http://math.stackexchange.com/a/928412, we need 3 steps for that proof. ...
2
votes
0answers
43 views

Finding an optimal topological ordering

I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological ...
-3
votes
0answers
21 views

Is the sum of admissible heuristic functions, admissible?

If $h_1, h_2$ and $h_3$ are given as admissible functions, is $h_4$ admissible given that, $h_4 = h_1+h_2+h_3$ ? All I know is that if $h$ is admissible, $h(n) \leq h^*(n)$ where $h^*(n)$ is the ...
1
vote
0answers
22 views

Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs. The nodes each side are both at the level of 10^3. The graph is globally sparse while locally dense. (I don't know whether this will give ...
-5
votes
0answers
51 views

How do i proceed with writing the algorithm? What will be the run time of the algorithm?

Given an n x n matrix which is to be multiplied with a vector of size 1 x n, write a algorithm for the purpose with 1-D partitioning of the input matrix along with one element of the vector per ...
1
vote
2answers
33 views

Why do source and sink have to be distinct in Ford-Fulkerson?

Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard,...
0
votes
0answers
15 views

FInding number of ancestors at given depth

I have a rooted tree with $n$ vertices. I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$. The query is ...
2
votes
1answer
29 views

Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the ...
0
votes
1answer
35 views

Why does using unary in subset sum problem result polynomial time complexity?

From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input). The number of bits in binary notation is obviously less ...
-3
votes
1answer
31 views

classifier accuracy

I’m developing a mutual information based classifier, the output of the classifier is {{0,4,5,6},{1,2,3},{7},{8},{9}} and the correct decision output is {{0,1,2,4,5,6,9},{3},{7,8}}. How to compute the ...
2
votes
2answers
54 views

Gramatical evolution doesn't result on creating good constants

I'm using Grammatical Evolution for symbolic regression tasks (i.e. searching the space of mathematical expressions to find the model that best fits a given dataset). I'm evolving solutions according ...
2
votes
1answer
46 views

Need explanation of Heap's Algorithm

Okay I am trying to understand the Heap's Algorithm from the original research paper published by B.R Heap. The most confusing aspect I found that while Heap says that the example described on the ...
-3
votes
0answers
14 views

Why DFS that is processed by stack is showing wrong sequence [closed]

See DFS image Here I am using stack to print sequence of dfs. According to input and that image of graph, sequence is 1 2 4 8 5 6 3 7 . But My code is giving output as 1 2 4 8 7 6 5 3 . Can anyone ...
1
vote
0answers
38 views

PageRank algorithm analysis

I was reading a paper about the PageRank algorithm and it mentions $ 2 $ ways to compute the weighted score for each vertex: If $ M_{n \times n} $ is a positive column stochastic matrix that ...
3
votes
1answer
77 views

Algorithm to find the first person in front of $A$ that is shorter than $A$

We have an array of $n$ positive integers $a_0,a_1\dots a_{n-1}$ and let $a_n=0$. I need to build an array $b_0,b_1\dots b_{n-1}$ such that $b_i$ is the first integer larger than $i$ with $a_{b_i}\...
2
votes
1answer
40 views

why & how are BFS nodes goal tested when they are generated?

In BFS, nodes are goal tested when they are generated.In other searches, nodes are goal tested before expanding them.what is the difference between this two statements? What is the advantage from this?...
0
votes
1answer
42 views

O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

Question: Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice. The second buy has to come after first sell. Solution: ...
0
votes
0answers
11 views

what is the Time complexity of matrix multiplication? and how can it be determined? [closed]

I tried to obtain it from a program. It gave me a graph whose equation is in exponential form.
0
votes
1answer
38 views

Find Divisible Sum Pairs in an array in O(n) time

You are given an array of n integers a0, a1, .. an and a positive integer k. Find and print the number of pairs ...
-1
votes
1answer
40 views

DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk. My question is that, say we have a DAG (...
-1
votes
1answer
97 views

Are basic CS algorithms used in machine learning?

I have read some articles which state that basic algorithms such as dynamic programming , graph algorithms etc are not required int machine learning fields such as deep learning , reinforcement ...
0
votes
1answer
32 views

Sifting algorithm for group generated by a set

On page 38 of "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2). I have some confusions. Why it is written that an entry $M_{i,j}, j < i$, ...
4
votes
1answer
24 views

Is the inverse of MST cycle property always true? Why?

I am trying to find an algorithm which would check for each edge in a given weighted undirected graph whether it belongs to any of the graph's Minimum Spanning Trees. I have found many potential ...
3
votes
0answers
52 views

Early termination of A* with weak heuristic if solution is known

I have a large graph G and a pair of nodes s,t. I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent. Suppose I already know of a path ...
0
votes
0answers
35 views

How to schedule different elements in a 24h range?

Given the following conditions: An element has: A time range, for example: 9:00 to 18:00. A repeat time, for example: every 5 minutes. Then a device recieves some elements and has to schedule ...
3
votes
2answers
79 views

Generate random point inside a polyhedron

I would like to know if there are known algorithms for generating a random point(say following a probability distribution P) inside an arbitrary polyhedron(possibly non-convex and may contain holes)? ...
0
votes
1answer
83 views

Algorithm for length of longest common subsequence

The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code: ...
4
votes
0answers
45 views

Is this solution to the dining philosopher's problem entirely valid?

In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem: A possible approach for avoiding deadlock without incurring ...
2
votes
0answers
13 views

Orderly graph generation and graph canonization confusion

In Orderly algorithms for generating restricted classes of graphs, Colbourn and Read expand on the earlier introduction of the orderly generation of graphs. Briefly, orderly generation allows you to ...
4
votes
0answers
28 views

Parallel bubble sorting on arbitrary graphs

Are there bubblesort-esque algorithms for sorting on arbitrary graphs? I'm working on a problem in which $k$ robots are placed randomly on a graph and have to reach their respective goals as quickly ...
3
votes
1answer
39 views

Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?

Given a graph G=(V,E) with positive edges weights, Is it possible to produce different shortest path trees for the Bellman-Ford algorithm and Dijkstra's algorithm?
1
vote
1answer
40 views

Vertex cover of a graph by removing leaf-vertices from a DFS tree

Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997. A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at ...
1
vote
1answer
42 views

Optimizing method for counting length of elements between blocks

I'm currently trying to do a count of the number of elements between obstacles, for example: 000100001000 Would yield 3,4,3 and 01001110 would yield 1,2,1. More precisely i'm trying to find the sum ...
0
votes
1answer
34 views

Spanning tree display conventions

On page two of this discussion of spanning trees there are two different tree structures shown, one labeled DFS tree starting from a as the root and the other labeled Spanning tree created by DFS. If ...
0
votes
1answer
70 views

Maximizing the rank of a binary matrix by zeroing matrix entries

Given a Square Binary Matrix. The entries of the Matrix are the integers modulo 2 (i.e., GF(2)). The Rank of the Given Matrix is an Integer value R0. What is the fastest known Algorithm to ...
2
votes
1answer
26 views

Big Theta for finding combinations of arbitrarily sized subsets from n total elements

Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset? Assume the elements ...
2
votes
2answers
42 views

Is It possible to change the side of 0 and 1 in Huffman tree?

When we are constructing the Huffman tree to get the Huffman codes, Is it possible to give "1" to left side and "0" to right side rather than giving "0" to left side and "1" to right side of the tree?
2
votes
1answer
34 views

Generating all directed acyclic graphs with constraints

I am interested in listing all the unlabeled1 acyclic digraphs with n vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for ...