# Tagged Questions

Questions related to design and analysis of algorithms

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 ...
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"...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
19 views

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 ...
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 ...
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. ...
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 ...
21 views

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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
77 views

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 ...
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 ...
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 ...
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 ...