Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

1
vote
1answer
29 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
1
vote
1answer
31 views

Computing binomial coefficients and factorials modulo a composite number

Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular? I know that for primes and factorials we can apply ...
-1
votes
1answer
20 views

difference between multilayer perceptron and linear regression

What is the difference between multilayer perceptron and linear regression classifier. I am trying to learn a model with numerical attributes, and predict a numerical value. Thanks
1
vote
1answer
33 views
-3
votes
1answer
17 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
2answers
64 views

Which textbook can I use after a high school CS course?

I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through ...
-4
votes
0answers
25 views

Question regarding post: http://cs.stackexchange.com/questions/16467/how-to-reverse-a-subarray-of-an-array [on hold]

I have a question regarding the algorithm you proposed for efficiently computing multiple sub-array reversals. I just took a simple example ant tried to apply your method - and it did not work for me ...
0
votes
0answers
10 views

What is co-factor multiplication with respect to ECHD [on hold]

I am new to ECDH and wanted to generate the a secret key in Java. I wanted to use Elliptic curve Diffie-Hellman with cofactor key derivation. I'm using the P-256 curve for the elliptic curve ...
0
votes
1answer
22 views

Stable marriage problem preferential to asking side

Watching this youtube video: https://www.youtube.com/watch?v=w1leqkpDaRw it described the problem with the stable marriage problem, that the asking side get a better deal then the asked site. Meaning ...
6
votes
2answers
44 views
+50

Detecting coplanarity by given pairwise distances

Given a 3D point set $P$, where $|P| \gg 4$ is there a way other than using Cayley-Menger determinant to detect if a group of points are coplanar or not? In other words, what are the methods to ...
1
vote
0answers
28 views

Palstar algorithm Dynamic Programming getting the result

I recently started to read abour dynamic programming, and I am doing an exercise on it. The problem to solve: Given a String, find the least amount of palindromes it can be split into, and print out ...
0
votes
1answer
25 views

Algorithm for distributing members over activites (with individual preferences)

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils ...
0
votes
1answer
31 views

efficient algorithms for factoring polynomials [on hold]

Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within ...
0
votes
0answers
13 views

Clustering geo location coordinates (lat,long pairs) [on hold]

What is the right approach and clustering algorithm for geo location clustering? Is it right to use Kmeans for location clustering, as it uses Euclidean distance and not Haversine formula as a ...
-3
votes
0answers
31 views

Idea of Manacher & Jeuring algorithm for finding the longest palindromic substring [closed]

I read the Manacher's algorithm and honestly I couldn't grasp the high level idea at all. I am trying to get it and thus Before spending more time my question is first: what type of algorithm would ...
3
votes
1answer
57 views

Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts. Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in ...
0
votes
1answer
42 views

Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm?

I created a program that simulates the fcfs scheduling algorithm. First I implemented it for a single core, then modified it for four homogenoues cpus. I compared the results with several datasets, ...
0
votes
1answer
49 views

Use Dijkstra to find negative cycles in a graph [closed]

I will state the problem: Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph. So, I saw the runtime, and I immediately said we need ...
2
votes
1answer
44 views

Finding Kernel in DAG

Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a ...
-2
votes
0answers
13 views

How to test the efficiency of Dijkstra's Algorithm in getting the shortest path? [closed]

My Professor ask me to show him how Dijkstra Algorithm will be efficient to get the shortest path. He said that it needs to be apply in an application to prove that this algorithm will work. But i ...
1
vote
1answer
33 views

How “coplanar” is a set of points?

Assume that we have 10 points. If all those points are on the same plane, they all are coplanar. But some of them might be at a different place. That disrupts the structure of the plane if we were to ...
1
vote
1answer
56 views

Set cover problem with constant size subset

Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?
0
votes
0answers
20 views

How to achieve ANFIS algorithm or Pseudo Code? [closed]

As you know for using anfis in Matlab we use anfisedit command which calls anfis command and this code calls anfismex which is in a .DLL file and invisible. So we can't edit and develop it. I have to ...
3
votes
2answers
69 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
0
votes
0answers
33 views

Longest Path A*, Admissible Heuristics, and Optimalness

Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path. I have some ...
0
votes
1answer
27 views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
6
votes
1answer
636 views

Why doesn't Knuth's linear-time multiplication algorithm “count”?

The wikipedia page on multiplication algorithms mentions an interesting one by Donald Knuth. Basically, it involves combining fourier-transform multiplication with a precomputed table of ...
1
vote
1answer
51 views

Efficient algorithm for iterated find/replace

I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow. Specifically: I have a function, ...
3
votes
3answers
125 views

Efficient algorithm to find subgraph

I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance. My problem I have a set of elements (that ...
0
votes
1answer
40 views

what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

in TAOCP vol3 2nd Edtion's 5.4.1R Replacement Selection, there is a paragraph describing a data structure and example for Replacement Selection as follows: the algorithm below uses a data structure ...
0
votes
1answer
48 views

Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
0
votes
0answers
50 views

how to understand some steps of TAOCP's 5.4.1R Replacement Selection Algorithm? [on hold]

these days, I am studying The Art of Computer Programming vol3 2nd Edtion's 5.4.1R about Replacement Selection Algorithms, the following is the original algorithm: $\texttt{Algorithm R (Replacement ...
-2
votes
2answers
58 views

Sum of all binary numbers matching a pattern [closed]

Given $a_1, a_2, a_3, \dots,a_7$ where $a_i \in \{0,1\}$. How to calculate sum of all binary number of the form $$\over {1a_1a_2*a_3**a_4***a_5a_6a_7}$$ where $*$ represent the position of running ...
3
votes
1answer
59 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...
10
votes
1answer
132 views

Quantum Computing - Relationship between Hamiltonian and Unitary model

When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, ...
-1
votes
1answer
54 views

Learning, understanding and using algorithms [closed]

I am a 2nd year computer science student. We all have subjects about Data Structures, Theories, more more theories we all know that i have a subject this semester Design Analysis of Algorithms. So ...
2
votes
1answer
77 views

Can not understand idea of the KMP algorithm

I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say: The ...
3
votes
1answer
27 views

Find missing value in period of LCG

It's well known that linear congruential generators have a full period only if a few properties are fulfilled. Now I need a LCG that does not generate a full period in 2^32 (easy to find, just ...
4
votes
0answers
51 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
1
vote
0answers
30 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
-2
votes
2answers
46 views

Efficient algorithm for extreme spread of points in a plane

Given a set $X$ of $n$ points in the real plane, designated by their Cartesian coordinates, find the extreme spread of the points, which is defined by $\qquad\displaystyle \mathrm{ES} = \max_{1 \leq ...
-2
votes
1answer
35 views

How do you return the k smallest elements of an array using Mergesort?

I'd like to create a modified mergesort algorithm to return the k smallest elements of an array. The mergesort algorithm below sorts an unordered array of size n. How do I modify the algorithm so that ...
-2
votes
1answer
63 views

Suffix automaton algorithm to find occurrences of substrings

Here is an attached link to a problem, the Substring query problem that I am trying to solve. It requires the use of suffix automaton,but I could not understand what is a suffix automaton. Can ...
7
votes
2answers
53 views

Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements: S = s1 ... sm T = t1 ... tm Semantically both sets are equal, but due to noise ...
3
votes
2answers
295 views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
3
votes
0answers
117 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
1
vote
2answers
115 views

Finding shortest path from a node to any node of a particular type [on hold]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
3
votes
1answer
57 views

Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas?

Definition: A renamable Horn formula is a Boolean formula that can be transformed into a Horn formula by flipping the polarity of every instance of one of more of its variables. Example: $\qquad ...
4
votes
1answer
46 views

Efficiently finding the maximum pairwise GCD of a set of natural numbers

Consider the following problem: Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers. Let $G = \{$ $gcd(s_i, s_j)$ | $s_i, s_j \in S,$ $ s_i \neq s_j \}$ where $gcd(x,y)$ is ...
0
votes
0answers
10 views

Is there any staticstics for the effect of noisy range measurements to the localization percentage in 3-D Range-based localization?

I'm implementing a simulation for 3D range-based wireless sensor network localization. In order to simulate the real-world cases, I need to impose some distance measurement errors. When I run my ...