Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

1
vote
1answer
5 views

Check whether an undirected graph contains a simple cycle of length four using the “Squares” method

The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani. Squares. Design and analyze an algorithm that takes as input an undirected graph ...
0
votes
0answers
5 views

Maximum cost path in integer matrix

In preparation for my design and algorithms exam, I encountered the following problem. Given a $2 \times N$ integer matrix $(a[i][j] \in [-1000, 1000])$ and an unsigned integer $k$, find the ...
3
votes
2answers
55 views

Number of winning combination in Nim

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are ...
3
votes
2answers
75 views

Searching the best trading route - algorithm

Imagine a village with people trading goods. Each person has his own offer in this format: Giving amount a of good b for amount ...
2
votes
0answers
26 views

Computational complexity of logistic map

My question is pretty simple and to the point. Is there a known way to efficiently compute logistic maps to within a specified precision? In other words, the input is a value $x$ and integers $d,n$; ...
0
votes
1answer
28 views

Shortest distance from a set of points

Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$. To ...
5
votes
0answers
60 views

Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which ...
1
vote
0answers
25 views

$N$-th term of a quadratic recurrence [on hold]

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $M$ ...
1
vote
1answer
34 views

Longest path in a cyclic, directed and weighted graph

I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights. In my research so far I have found out that you need to generate ...
1
vote
0answers
19 views

Vectorized Algorithm for finding the Shortest Path in a Graph

I know that you can calculate the shortest path in a vectorized fashion using Floyd-Warshall, e.g. like proposed by Han and Kang, however I want the matrix, they call "via", the actual route taken ...
-1
votes
1answer
16 views

ordered uniform distribution

We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ ...
-3
votes
0answers
44 views

Algorithm to solve a tangram [on hold]

I'm given a set of pieces and a shape, and I've to come up with one(any) solution. I'm totally stuck on where to begin. I'd like to get some suggestions to get me started. Particularly, I'd like to ...
2
votes
1answer
133 views

Maximum subset pairwise not divisible by $K$

I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$. I tried to solve this problem, but I have found the ...
-1
votes
0answers
53 views

Proof of correctness for the greedy solution of uva10249 The Grand Dinner [on hold]

This problem is at here. Given $M$ teams and $N$ tables, can we find a way to divide the teams over the tables such that no two members of the same team end up at the same table? The number of ...
1
vote
1answer
20 views

Travelling Salesman Problem with unknown shortest paths between nodes

I have a Travelling Salesman Problem, where I want to retrieve the "shortest" (approximate solution) circuit including the nodes n_1..n_n in a graph. The graph, however, includes a second set of ...
2
votes
0answers
42 views

Find internal surfaces in B-rep geometry

I have a solid with internal holes. My solid is in Boundary-representation (B-rep). More exactly my solid is a list of polygons that are list of points. I want to distinguish internal surfaces from ...
1
vote
0answers
18 views

Reconstructing a graph from set of sequences of edges

I have posted the same problem to Math Overflow, not sure where it fits better. I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, ...
2
votes
1answer
44 views

Shortest path from that passes through a set of edges once

Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big. Slow solution: Finding shortest ...
2
votes
1answer
43 views

Densely connected non overlapping subgraph

I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster. I'm currently trying to detect community using Louvain algorithm, but it ...
1
vote
2answers
32 views

What is the point of the “respect” requirement in cut property of minimum spanning tree?

The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows. Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight ...
1
vote
1answer
61 views

smallest circle that covers two points with its center in x axis

I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know ...
0
votes
0answers
70 views

How to determine if two extremely long lists of numbers (terabytes) are similar?

I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers. The main rule if if two ...
2
votes
0answers
43 views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
-4
votes
0answers
32 views

Program that computes product until it exceeds $7^{10}$ [closed]

Write a complete program using a while loop that computes the product $1×2×3×…×n$ until the product first exceeds $7^{10}$. The program should print to the last value of $n$ before the product ...
0
votes
1answer
38 views

Taking the modulus of 2 arrays [on hold]

I'm putting together a primality tester for large numbers. When the numbers were smaller things were more straightforwards. I got refined it to a point where I could quickly test any number within the ...
3
votes
0answers
26 views

Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m << D $ dimensional columns ...
3
votes
1answer
91 views

Convex hull algorithm in $O(\min(mn, n\log n))$

I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$. My first guess was ...
1
vote
0answers
42 views

Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

Given a weighted complete bipartite directed graph K_{m,n}, is it possible to find a simple cycle (every node is visited at most a single time) with minimal weight in polynomial time (in m*n) when ...
0
votes
1answer
30 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
4
votes
0answers
29 views

Computing the right tangent of two convex hulls

My question deals with the algorithm of computing the convex hull in 2D by Preparata. Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex ...
3
votes
1answer
43 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
3
votes
0answers
61 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. ...
0
votes
1answer
40 views

An efficient algorithm to find a shortest cycle including a speciic vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$. We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle. This ...
0
votes
1answer
25 views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
0
votes
1answer
19 views

choose minimum number of M professors in polynomial time in order to design all N course exams

Think that we have M professors and N courses every professor can wrote question for at least one course exam. we want to choose minimum number of professors in order to design question for all N ...
6
votes
1answer
126 views

Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

Karlheinz Brandenburg depicts a MP3 encoder like this: Source: MP3 and AAC Explained I marked the FFT as I'm not quite sure why it is actually necessary to perform one. Why can't the ...
1
vote
0answers
33 views

Create the shortest list that contains a set of subsets in block

I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list. The input is a set of set of ...
1
vote
2answers
60 views

IS Array of Positive Integers Always 'Equalizable' With This Strategy?

A little bit of history first. I have asked this question here some days ago. Quoting from there: An array $A$ is given that has only positive integers in it. The objective is to equalize the ...
-1
votes
0answers
26 views

What is an efficient gap sequence for shellsort

When implementing shellsort for 3x + 1 I found that some of examples use lenght/3 threshold for the sorting values. I mean if we ...
3
votes
1answer
50 views

Algorithm for listing all binary trees of a given height

I've been trying to find an algorithm to list all binary trees of a given height $h$. Note that I'm not trying to enumerate them: the number of such trees is given in the OEIS (A001699). All the ...
4
votes
1answer
69 views

KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
-6
votes
0answers
33 views

How to represent an Algorithm mathematically? [closed]

I read somewhere that the best proofs of an algorithm working can be seen mathematically, so Given that I have an Algorithm, how do I represent it mathematically.
4
votes
2answers
66 views

What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?

Let $A$ be an array (equipped with a total ordering $\leq$) of size $n = km$ with $k\in \mathbb{N}$, such such that $A[1],\dots,A[n]$ are all distinct. What is a fast way to find a partition ...
1
vote
1answer
29 views

Minimum Weight Directed Subgraph ensuring all pairs reachability?

After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an ...
0
votes
0answers
55 views

Misionnaries and cannibals problem (A* algorithm)

"In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if ...
0
votes
0answers
44 views

Is it possible to estimate Time Complexity from a formula? [on hold]

I am not very experienced with time complexity, networks, and algorithms, but here is a question for those who are. I will try to be as explicit and clear as possible. Imagine a regular network made ...
1
vote
2answers
72 views

Linear-time algorithm to find an odd-length cycle in a directed graph

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related ...
1
vote
1answer
51 views

Pseudocode algorithm to check encoding of Turing machine

My question goes like this: Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is ...
-1
votes
0answers
24 views

The problem of graph coloring

Is there an algorithm that solves the problem of graph coloring in 3 colors with complexity $O(2^n · m)$?
1
vote
1answer
58 views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...