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
18 views

Winnow2 Algorithm

In the Winnow2 Algorithm, how is the alpha value obtained? I have found a handful of papers and sources (included below), but none explicitly call out how to decide on the alpha value... http://www....
1
vote
0answers
45 views

Finding the best state for chain graph with cycles

I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
2
votes
1answer
40 views

2-opt vs 3-opt comparison

I have a question regarding performance of 2-opt and 3-opt algorithms. I tried implementing the 3-opt and 2-opt algorithms and most of the time 3-opt outperforms the 2-opt algorithm around 5%. ...
0
votes
0answers
28 views

topology representation through graph [on hold]

Is there any way to represent indoor topology of a house through graphs or trees and calculate similarity or dissimilarity between them?
3
votes
2answers
104 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
39 views

List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
0
votes
1answer
36 views

How fast can all nth roots of an integer be computed?

I mean that for every $i$ from 2 to $\lceil \log_2n\rceil$ I want to know $\lfloor \sqrt[i]{n}\rfloor$. Could this be done faster than computing the roots one by one?
1
vote
1answer
37 views

Solve the recurrence relation T(n)=3T(√n)+lg(n) [duplicate]

Master's Theorem is known to me, but I can't understand how to apply this theorem to this problem. So, how I will find Θ of T(n)?
2
votes
0answers
18 views

Inverse kinematics step

I am working on an implementation of inverse kinematics using the jacobian transpose method. The implementation seems to be working as it does find the "theta" vector, although sometimes it might take ...
0
votes
0answers
48 views

Successive shortest path without reduced costs

The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows : Successive shortest path (for minimum-cost flow) : while all flow is not ...
1
vote
2answers
46 views

Pseudo Code optimization

Summary: I am struggling with the Pseudo code for an that algorithm assigns "least filled slot first" to a tasks on multi-core chip. Detail So far I have written following: What I do not like ...
4
votes
2answers
73 views

Add lines to star with fixed coordinates maximizing smallest angle

I have the following problem: There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
1
vote
0answers
69 views

Choose subsets to minimize a set function

Given two sets $S_1$ and $S_2$ of $n$ elements each and a capacity $C$. Each element in $S_i$ ($i=1,2$) has a weight $w_{ij}$ for $j=1,2,\ldots,n$. From each set $S_i$ ($i=1,2$), choose a subset $O_i\...
1
vote
1answer
24 views

Enumerating all ways of pairing odd nodes

Can someone provide a brute force pseudocode for finding best connections between odd-degree nodes in the Chinese postman problem mentioned here? For example, if the odd nodes are $B,C,D,E$, the ...
1
vote
0answers
25 views

How do distributed algorithms for shortest path finding handle negative cycles?

I am searching the web for an answer to this question, but I have only found answers for non-distributed algorithms. I am interested in this for its application to Distance Vector routing.
0
votes
0answers
35 views

How minimal perfect hash functions are discovered / created

I have been looking at How to create minimal perfect hash functions, and come across resources such as these: Finding Succinct Ordered Minimal Perfect Hash Functions $$h(x) = \Bigg[\sum_{j=0}^{m-1}g(...
0
votes
0answers
14 views

Trie or no Trie for 1,000 page document or searchable BigInt dataset

Tries seem to be good at storing and querying small strings, like keys to a dictionary. What I would like to know is if there is anything better for storing large strings such as a 1,000 page ...
0
votes
0answers
41 views

Resource allocation / optimization

At work I stumbled across this problem of allocating resources: We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...
1
vote
0answers
26 views

Algorithm for DFA accepting any string with ending with a particular substring

Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly ...
0
votes
1answer
22 views

Hash table open addressing without dummy

If a hash table is using open addressing as the collision resolution strategy, then during deletion, we mark that slot as dummy. I understand the reason behind ...
1
vote
1answer
55 views

Maximum product of contiguous subsequence over $\mathbb{R}$

For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here). Let us first show how to solve the ...
1
vote
0answers
31 views

How to generate a random number in a given range with uniform probability [closed]

I have used programming languages which generate a random number in a given range. Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
0
votes
1answer
34 views

Why is O notation the worst case? [duplicate]

I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f(n) <= cg(n), we can see that in any case f will be smaller that the original ...
1
vote
0answers
20 views

How to find all numbers that there distance from given point are less or equall to integer n? [closed]

Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$? Example: suppose we ...
2
votes
0answers
60 views

What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle). It ...
0
votes
0answers
36 views

How MAC-3(maintaining arc consistency-3) algorithm works?

I am studying CSP problems in artificial intelligence. I don't understand the MAC-3 algorithm especially line number 10. Could you tell me with step by step? ...
0
votes
1answer
60 views

What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

There is D-dimensional array A. The number D and the size Sd of every dimension d=1..D is input from keyboard. There is also 1-dimensional array E of size N. It consists of unique integer numbers 0..N-...
-1
votes
0answers
22 views

How to solve(prove) this? [duplicate]

I'm having difficulties prooving this problem. Actually, I have a lot of hws but If you help me I would solve other ones by myself. I just want to understand how to prove this kind of problem. (Big-O ...
1
vote
0answers
51 views

Sum of long geometric progression [on hold]

Finding sum of a geometric progression is simple when we just need to report the sum, but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me. I have a ...
-1
votes
1answer
76 views

Find the Most Frequent Ordered Word Pair In a Document

This is a problem from Skiena's excellent book The Algorithm Design Manual: Give an algorithm for finding an ordered word pair(e.g."New York") occurring with the greatest frequency in a given ...
0
votes
0answers
19 views

Deriving cost function of algorithms with constant input size

When an algorithm uses conditional loops that depend on constant input (i.e. O(c) ). How to calculate the cost function? See this example of pseudocode that takes two int and returns true if one is a ...
2
votes
1answer
45 views

Greedy Solution for Selecting Prefix Sum

Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to ...
1
vote
1answer
83 views

Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
0
votes
0answers
22 views

3-partition reduction [duplicate]

Let's say we have a set A of positive integers.The weight of this set(weight sum of elements) is multible of 3.Is there a partion of A in 3 subsets A1,A2,A3 so that:weight(A1)=weight(A2)=weight(A3)? I ...
1
vote
1answer
29 views

Approach to find minimum set in one table consisting of all items in second table

wondering if you can help me with the following problem. I have one table consisting of items in each person's bag: ...
-1
votes
0answers
28 views

Real estate maximum matching algorithm

I’m working in real estate company and when we launch a new project we receive thousands of customers everyone with a list of several choices of units ordered by priority 1st and 2nd and 3rd. Clients ...
-1
votes
1answer
33 views

Genetic algorithm problem

This is a problem I found in an old exam in my school. I have to solve this Genetic Algorithm problem: N students $x_{1},..,x_{N}$ have answered a quiz of 10 questions (True or False questions) and ...
2
votes
1answer
56 views

Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
2
votes
2answers
63 views

Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?

Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments. I think I can ...
1
vote
0answers
17 views

Maximizing cache utilization when scheduling a computation graph

So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done ...
1
vote
0answers
30 views

Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
2
votes
1answer
66 views

Checking the validity of a pyramid of dominoes

I came across this question in a coding interview and couldn't figure out a good solution. You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level ...
1
vote
0answers
25 views

Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
1
vote
0answers
31 views

Text Segmentation Problem give Word Frequencies in a Universe

Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I ...
0
votes
0answers
28 views

findining the smallest sum of squared lengths of the intervals I_{k}

Given a set S = { $x_{1}$, $x_{2}$, . . . , $x_{n}$} where $x_{i} \in Z$ . and a K and it is $Z^{+}$ . The goal is to find k intervals $I_{1}, I_{2}, . . . , I_{k}$ so that each $x_{i}$ is in one ...
1
vote
0answers
10 views

State of the art of parser handling of offset errors

Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the ...
0
votes
1answer
18 views

minimum cardinality maximal matching of graph

How to find minimum cardinality maximal matching? I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
3
votes
0answers
21 views

How does negation as failure work with variables?

Let's say we have the following rule: p -: X ≠ Y, X = Y Stating that $\forall x.y. x \neq y \land x = y \implies p$. Now let us suppose that we are searching for ...
1
vote
1answer
50 views

Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each ...
0
votes
1answer
21 views

Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...