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.

1
vote
1answer
39 views

Calculate Shortest Path (Shortest Time) Through a Store in a Graph

There is an undirected graph and some of the vertices are said to be stores. Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores ...
2
votes
0answers
42 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
0
votes
0answers
13 views

Forming an algorithm for assigning priority weights

I'm trying to develop/research an algorithm in which I can use to assign weighted values (priorities) to a list of jobs that need to be done. I've come up with some kind of arbitrary weights, but I'm ...
3
votes
2answers
78 views

Uniform sampling over non-standard simplex

Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex I want to sample one point from a non-standard simplex with vertices at: $s_{i}\vec{e_{i}}$...
0
votes
0answers
38 views

How to implement Dout = 0.607252935*Din using CORDIC algorithm

I can think of the implementation of Dout = 1.64676025815*Din using CORDIC algorithm by using 3 equations of X, Y and Z(angle). But how to implement the reverse i.e. Dout = 0.607252935*Din using ...
0
votes
1answer
56 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
6
votes
1answer
119 views

Does finding a cycle with $\log n$ length in $\text{P}$?

Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?
0
votes
1answer
74 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
0
votes
0answers
28 views

Define 'algorithm' [duplicate]

The dictionary definition of "algorithm" is so broad that it technically covers all computer programs: ...
0
votes
0answers
15 views

What is the complexity of the following program? [duplicate]

int max = int(pow(2,n)); int sum = 0; int i ; for(i = 1; i<=max; i++) { sum++; } How do I calculate the complexity of this program? Is it O(NlogN)?
1
vote
1answer
43 views

First problem to be considered np complete?

What is the first problem that was demonstrated to be NP-Complete?
2
votes
2answers
65 views

Finding a local peak in an array in O(log N)?

So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the ...
0
votes
0answers
12 views

What is the advantages of decision diagram over decision tree?

while reading few articles I come across few doubts. Could anyone please help me ? The below mentioned are the questions 1)What is the advantage of Decision Diagram over Decision Tree? 2)Is Decision ...
1
vote
0answers
16 views

Why Not To Take B8ZS with encoding 7 digit?

I have a simple question. In signal encoding we have B8ZS (Bipolar with 8 zeros substitutions) technique which encodes every 8 sequencial 0 bits with 000+-0-+ or 000-+0-+ depends on previous voltage ...
1
vote
1answer
43 views

Post numbers in DFS tree of an undirected graph

How could you prove: An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the ...
0
votes
0answers
23 views

Given bunch of 5-tuples like [7, 12, 1, 0, 5] how to detect patterns like AABDD where A,B,D are certain number ranges?

I have bunch of 5-tuples (representing some patterns in model) like [7, 12, 1, 0, 5], [7, 13, 10, 13, 9], etc. I also have rangeA=[1,2], rangeB=[2,3], rangeC=[4,5,6,7], rangeD=[8,9,10,11,12,13,14,15], ...
0
votes
0answers
13 views

Questions regarding Particle Swarm Optimization (for TSP) algorithm (paper)

I'm trying to re-implement an algorithm from a paper regarding the Particle Swarm Optimization metaheuristic for the Traveling Salesman Problem. The paper is the following: Goldbarg et al. (2006): ...
1
vote
0answers
15 views

Hungarian algorithm to search over all matching?

I am working on the following problem- "Finding the matching among all possible matching such that the sum of edge weight is minimum in the matching." Please note that I like to search over all ...
0
votes
2answers
39 views

Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
2
votes
1answer
55 views

Using Yao's principle to find a lower bound

This is a HW question, so I'm not expecting any answers, just a general guidance/help. Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\...
0
votes
0answers
46 views

Backtracking solution to Bin Packing problem

I have the following problem : Given an Array of integers such as : V = {9,4,1,2,4,3} and a number such as N = 12 divide into K parts, so each part adds N or less, taking the best solution. I ...
0
votes
0answers
41 views

Finding all subsets of a set

I have a set, and i want to find all its subsets. what is the best time complexity to find it? What is the most efficient algorithm to find all subsets of a set?
0
votes
0answers
31 views

How to select the best genetic algorithm for optimization?

I am trying to optimize parameters for a trading strategy, with many local/global maxima. I need to run a backtest for each new parameter set, which takes minutes to hours. I am wondering, if my own ...
0
votes
0answers
26 views

How to find all paths from a certain collection of nodes to another, without any common nodes in any of the paths?

For example i am given a undirected Graph G = (V, E). Within that graph i have a certain collection of nodes D and S. Now i need to find paths from D collection of nodes to S, without any two paths ...
0
votes
0answers
10 views

Algorithm for laying out grids (html-like tables) with row/column spans

This problem should have the same solution for the horizontal as well as for the vertical, so I'll only present the horizontal case. Consider the following layout with 3 columns, 3 rows and 2 column ...
1
vote
1answer
14 views

how is an arbitrary dimension “reshaper” turned into a function given a linear index?

i have an arbitrary "reshaping" function which, given a linear sequential array can "reshape" it to 2D or 3D. the order in which the X-dimension, Y-dimension and Z-dimension may all be changed, as ...
0
votes
0answers
15 views

angle constraint on convex hull

Given a set of points $P$ in $R^d$ it is straightforward to compute the convex hull (Graham-scan etc). However, the angle between the adjacent faces are unconstrained (apart from necessitating that ...
1
vote
0answers
35 views

Finding simple min-weight path between two vertices in graph with negative edge weights

Given a weighted graph (negative weights are allowed) and two vertices $u$ and $v$, can we find the simple min-weight path between $u$ and $v$? There can be a negative cycle on the path from $u$ to $v$...
0
votes
1answer
13 views

Distribute to pairs with efficient algorithms

The task is to find a efficient algorithm to the following problem. There are n boys and n girls who need to be divided to pairs. You get a list with all possible pairs that could be made. It means ...
1
vote
1answer
23 views

How would you identify the size of a circular turing tape?

Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that ...
2
votes
1answer
30 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
102 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
0
votes
0answers
24 views

Covering 1's in binary matrix using 1xK rectangles

Given a matrix of 0's and 1's cover all 1's using the smallest number of 1xK rectangles, where K is a number given by user. We can cover the 1's only horizontally or vertically. For example for K=3, ...
0
votes
1answer
29 views

interval scheduling algorithm

can any one explain why the greedy algorithm solution i.e sorting according to finishing time is optimal in the interval scheduling algorithm ?? I want proof in layman's language. I was watching this ...
2
votes
0answers
34 views

Theoretical performance measures other than worst case

Suppose that $P \neq NP$, and $P = BPP$. Assume one is given a decision language $L \in NPC$, and she has only polynomial time turing machines. Additionally, she can't use randomness (not sure that's ...
1
vote
1answer
63 views

Convert given string to Palindrome with given substring

Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other ...
3
votes
0answers
262 views

Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family

I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family Concretely: For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$ and $L'_j ...
1
vote
0answers
17 views

B/B+ trees without leftmost pointers

In both B-trees and B+trees, a node (a.k.a page) contains K keys and K+1 pointers: node = [ ptr_1, key_1, ... , ptr_K , key_K , ptr_(K+1) ] Now suppose that I ...
2
votes
1answer
40 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
0
votes
1answer
29 views

Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...
1
vote
1answer
28 views

How to find the number of Binary Search Trees with given number of nodes and leaves?

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that: Exactly $1$ leaf node(s) present? Exactly $2$ leaf nodes present? I was able to solve the first ...
-1
votes
1answer
26 views

Given a list of values, choose the greatest possible number of sorted values

Given an array of numbers, I want to select some entries, preserving their order, so that I end up with the longest possible sorted sub-array. It does not matter which entries I discard in the process....
1
vote
2answers
36 views

What algorithms are there for scheduling tasks

The scenario is something like this I have tasks that get requested, with a category and a priority For simplicity let's assume that rate of incoming tasks and completion is about the same, with some ...
0
votes
1answer
32 views

Finding duplicates in a stream of numbers

This is an interview question. Say you have a function foo() which returns some integer. You need to write an algorithm that does the following: (...
1
vote
3answers
88 views

Data structure for getting the k'th largest element

I'm given a set of $n$ numbers. Is there a data structure that builds in $O(n)$ (linear time) and gets the $k$'th largest element in $O(k)$ time? Also, is there anything better than $O(k)$?
2
votes
1answer
47 views

Is there an asymptotically optimal algorithm for unbounded search?

Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is ...
0
votes
1answer
27 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
0
votes
1answer
45 views

Egg dropping puzzle

My problem is a modification of the known problem. Suppose you have a building with n floors. (Where n can be any size). Furthermore you have an indestructible egg at your disposal. If the egg is ...
4
votes
2answers
130 views

A problem on constrained combinatorics

Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics). I'm looking for ...
2
votes
0answers
24 views

Find combination of array elements that exceed maximum array element

Say I have an array of integers like so: [2,2,3,5,5,5,5,6,6,7,7,7,7,9,10] I'd like to find all combinations of these values that when summed exceed the maximum (in ...