Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

2
votes
1answer
8 views

Finding the interior of a connected graph

I'm designing software that produces images such as the following: Regions of interest are circumscribed by red pixels. I am interested in extracting the fully-enclosed pixel regions. Ultimately, I ...
1
vote
0answers
18 views

Distance Largest Weight Edge in MST

Given a set $P$ of $k$ points in a plane. The Distance Variant problem: partition set $P$ into two subsets $P_{1}, P_{2}$ so you can maximize, $d(P_{1}, P_{2})$ = min $p \in P_{1}$ min $ q \in ...
1
vote
1answer
29 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
1
vote
0answers
17 views

What does ∇log mean in the Robbins-Montro algorithm?

The Robbins/Monro Algorithm is a type of stochastic optimization algorithm of the following form: (as mentioned in wikipedia) $$x_{n+1} - x_n = a_n(\alpha - N(x_n))$$ where $M(x) = \alpha$ is a ...
1
vote
1answer
33 views

Enumerating all n-tuples over a finite domain

I would like to create an algorithm which takes in an integer n and returns an array whose entries give all n-tuples of nonnegative integers each of which is at most n, so like ...
3
votes
1answer
46 views

Algorithm to extract the subgraph of all nodes with degree at least four

I have an undirected graph represented by a list of nodes and a list of edges. What I need to produce from this is a list of nodes and edges representing a new graph containing only the nodes which ...
-2
votes
0answers
14 views

Online studying [on hold]

From where should I start learning Computer science as there are many resources available online. I need advice which course to start with and which course to follow next.
0
votes
1answer
43 views

How do you search a graph? [on hold]

An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one. Got the first one but not the second. What is the modern standard way to search ...
0
votes
0answers
27 views

Utility Maximizing Challenging Assignment Problem

There is a grid of size MxN. M~20000 and N~10. So M is very huge. So one way is to look at this is N grid blocks of size M placed side by side. Next assume that there are K number of users who each ...
1
vote
1answer
163 views

Algorithm - Wine Bottle Filling

You have two friends, call them A and B. They each are given two wine bottles: one bottle holds k_1 litres and the other k_2 ...
-1
votes
2answers
43 views

Is there any other way of getting a function from this piece of code?

I have this code The problem ask for the expression that returns this function using N or in terms of N The best I have done is $\sum\limits_{i=0}^n i \bmod 3$ Is there any better way to express ...
-3
votes
0answers
29 views

Very basic Brute-force algorithm [on hold]

Yes, this is homework. I'm taking a starter statistics class where we're going over brute-force algorithms. It's basic enough that I could do this by hand, but I'm more interested in doing this with a ...
-2
votes
0answers
9 views

Which algorithm should I choose for constraint satisfaction in 3d space?

I've got this problem: He peered at Richard seriously. ‘Do you have a good sofa?’ he enquired. ‘Well, yes.’ Richard laughed. He was cheered by the silliness of the question. ... ...
3
votes
1answer
55 views

Bellman-Ford Termination when there is no change on vertex weights?

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the ...
0
votes
1answer
35 views

What's the difference between physically based rendering and global illumination?

I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual ...
-2
votes
0answers
81 views

An algorithm for graph isomorphism [on hold]

I have an idea for a Graph Isomorphism algorithm with complexity $$(n^{k}/2^{\sum k})^{s}$$ where $k \cdot s = n$ is the number of vertices of the input graphs, $k<\log{(n)}$. I am not sure, it is ...
0
votes
1answer
51 views

Algorithm to compute a recursive function on a given set

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
0
votes
0answers
42 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
5
votes
1answer
71 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
2
votes
1answer
40 views

Understanding terms related to 2SAT algorithm

Recently I am learning about solution of the 2-satiability problem using strongly connected components. There is a theorem related to this problem given below: Let $F = Q_lx_1 Q_2x_2\ldots Q_nx_n C$ ...
-1
votes
1answer
23 views

Edges of minimum spanning trees.

Is as edge of a minimum spanning tree in a graph $G$ the shortest path between its incident vertices? I think this might be true due to the cut property of but I am unable to prove it.
0
votes
1answer
38 views

Recursive algorithm to compute a sum of product like function

I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ ...
-1
votes
0answers
19 views

How do I prove that 1 function is an upper bound of the other? [duplicate]

If for every $n > 0$ and some $b > 1$, $T(n) \le h(n)$ and $h(n) = O(h(n/b))$ then how can I prove that $T(n) = O(h(n))$, I understand that $T$ is bounded by $h$, so $h$ must be its upper bound, ...
2
votes
1answer
40 views

Going deeper with pseudo-polynomial time algorithm for set partitioning

If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next? To illustrate this ...
0
votes
0answers
19 views

How to measure a probability that two data objects represent the same entity [closed]

What algorithmic ways exist to assign a probability for two data objects to represent the same entity? For instance, identifying misspelled person names, using ambiguous initials, when we may also ...
3
votes
1answer
43 views

Greedy algorithm for Set Cover problem - need help with approximation

I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above. ...
2
votes
1answer
23 views

Explanation of implementation of an algorithm for Dominating Set [closed]

I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices... So, I have found a well ...
3
votes
0answers
21 views

Pi Calculus: Restriction necessary for molecular (atomic) action?

In "A Calculus of Mobile Processes, Part 1" [1], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes ...
-2
votes
1answer
60 views

What is the algorithm to add 2 binary numbers with boolean operations?

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
3
votes
0answers
33 views

Can someone help me make this branch and bound algorithm more efficient for a large input?

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the coursera discrete optimisation course) I tried implementing dynamic programming first, and that worked ...
0
votes
0answers
10 views

Any good algorithms for 3d volume alignment by feature extraction, especially ones involve machine learning?

I am trying to align 3d mri brain images of different rat individuals. I have dozens of examples that have been aligned manually, which are good resources for machine learning. I am considering ...
5
votes
1answer
37 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
0
votes
1answer
46 views

Optimization in multivalued logic. Optimal strings with given patterns

This question comes from an application in multivalued logic. Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the ...
2
votes
1answer
63 views

Finding the values for a particular bucket in a list

I have a list of n items. I need to find the items that will be present in a given range, if the list were to be sorted. Sorting the entire list is not required and ...
1
vote
1answer
26 views

Finding the best combinations between items of 2 arrays in a sequential manner

I'm reposting this because people found the last description to be too hard to follow. The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. ...
2
votes
0answers
25 views

Looking for some lossless compression theory [duplicate]

I'll apologize in advance if anything in here is ineloquent. Suppose we have a pair of lossless compression (C) and decompression (...
-1
votes
1answer
31 views

Problem on Dynamic Programming

A company is planning a party for its employees. A fun rating is assigned to every employee. The employees are organized into a strict hierarchy, i.e. a tree rooted the president. There is one ...
-2
votes
0answers
15 views

Negative Cost Cycle in a Directed Network [duplicate]

Does anyone have a code for finding the negative cost cycles in a directed network? Or can help how to find one? The problem is to generate an arbitrary network with random arc costs, and then find a ...
1
vote
1answer
21 views

Splitting permutations into transpositions

Suppose we are given an array $\texttt{a[]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a[]}$. Otherwise we interpret ...
0
votes
0answers
25 views

Finding the N'th viable combination between arrays A and B [duplicate]

To dumb it down to basics, lets say I have a struct called item that looks like this: struct item { int power, cost; }; then I have 2 arrays of these items, ...
9
votes
2answers
605 views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
1
vote
1answer
48 views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
0
votes
0answers
60 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
2
votes
1answer
28 views

Efficient computation of traces of all primitive elements in field extensions of GF(2)

Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from ...
1
vote
1answer
56 views

Skienna's recursive algorithm for edit distance

I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic ...
2
votes
1answer
80 views

Correctness of splitting an undirected tree into a forest of trees with even number of children

Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is to remove as many edges from the tree as possible to obtain a forest of trees, where each such ...
-3
votes
0answers
35 views

Diameter and some Formula on Graph Theory

in an undirected graph G, we define: Diameter is maximum of minimum paths between two vertex of a graph. L(s) is maximum length of minimum paths from s to ...
2
votes
1answer
33 views

Finding the best N length combination between M items

Lets say I have a few million random items. Each item has 6 attributes: Type, Cost, Strength, Stamina, Agility and Intelligence. Type is one of 4 different possibilities, the other 5 are various ...
1
vote
1answer
24 views

Absolute orientation alignment with vectors

I have two trajectories of a moving object. Each trajectory is composed of poses at discrete time. Each pose is a translation vector and a rotation matrix. Each trajectory defines the same path (with ...
0
votes
0answers
3 views

Algorithm for arranging operands and operators to get desired result [migrated]

I am trying to write an algo and code in Excel VBA or Java to arrange different values and operators to arrive at given result provided starting value. Input Table 1: Values Label | Value ...