Questions related to design and analysis of algorithms
6
votes
0answers
48 views
Towers of Hanoi but with arbitrary initial and final configuration
Recently, I came across this problem, a variation of towers of hanoi.
Problem statement:
Consider the folowing variation of the well know problem Towers of
Hanoi:
We are given $n$ towers ...
4
votes
3answers
91 views
Find maximum element in sorted arrays in logarithmic time
Been stuck on this for a while, would really appreciate some help:
Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For ...
3
votes
2answers
56 views
Predicting energy consumption of households
I have the dataset which you can find here, containing many different characteristics of different houses, including their types of heating, or the number of adults and children living in the house. ...
-2
votes
0answers
48 views
Checking whether n vertices are reachable from v
I'm trying to find an algorithm that takes a graph, and checks if a given vertex $v$ can reach n other vertices in time $\mathcal{O}(\left| E \right| + \left| V \right|)$. Should work on directed and ...
6
votes
1answer
75 views
Finding the largest 3-clique-free induced subgraph
Consider this problem:
Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:
$G'$ is an induced subgraph of $G$
$G'$ has no 3-cliques
$|V'|$ is maximal
So the ...
1
vote
1answer
35 views
Backtracking for listing k elements
Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.
Describe a back tracking algorithm for efficiently ...
1
vote
1answer
63 views
Graph problem, shortest path with a K
From Skiena's book,
Let G = (V,E) be a directed weighted graph such that all the weights are positive. Let v and w be two vertices in G and k ≤ |V | be an integer. Design an algorithm to find the ...
0
votes
1answer
25 views
Identifying an object in an image based on color (AI ?)
First off, I am not sure if this is the correct stackexchange site to ask this question on, so moderators can feel free to move it.
I am working on an application that identifies an object in an ...
0
votes
1answer
38 views
Algorithm to determine if a number is perfect on a Turing Machine
I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
1
vote
0answers
43 views
LInear time algorithm to find the diameter of a tree [duplicate]
This is NOT HW, this is from Skienas book, and I just couldn't solve it at all.
Please give me a hand here, in understanding and solving it, thanks.
Let G = (V, E) be a binary tree. The distance ...
5
votes
1answer
62 views
Quicksort Partitioning: Hoare vs. Lomuto
There are two quicksort partition methods mentioned in Cormen:
...
2
votes
0answers
30 views
Pebbling Problem
Pebbling is a solitaire game played on an undirected graph $G$ , where
each vertex has zero or more pebbles. A single pebbling move consists
of removing two pebbles from a vertex $v$ and adding ...
-1
votes
1answer
41 views
Directed Acyclic graph question [closed]
first of all - great site!
Here is my problem, I am studying for an interview, and I ran into this problem,
http://i.stack.imgur.com/JmdER.png
I am asked, Suppose an arithmetic expression is given ...
0
votes
1answer
50 views
Why does DFS only yield tree and back edges on undirected, connected graphs?
Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.
Now, from intuition and in class lectures by Steven Skiena, I know ...
0
votes
1answer
46 views
Bellman-Ford parent pointer (?) negative cycle
First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof ...
5
votes
1answer
82 views
Route on a square grid with only (x,y) → (x,x+y) and (x,y) → (x+y,y) moves
This problem is about finding a route on a square grid.
The starting point is $(1,1)$ and the target point $(n,m)$.
I can move each step from my current point $(x,y)$ either to $(x+y,y)$ or $(x,y+x)$.
...
5
votes
0answers
42 views
FFT-less $O(n\log n)$ algorithm for pairwise sums
Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.
We are interested in finding the counts of all the ...
1
vote
0answers
61 views
What is Pointer Jumping ?
Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?
0
votes
1answer
15 views
Solving system of linear inequalities
I am trying to solve a system of inequalities in the following form:
$\ x_i - x_j \leq w $
I know these inequalities can be solved using Bellman-Ford algorithm. ...
3
votes
2answers
79 views
From Whence the Randomization in Randomized Quicksort
Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph):
Using a random number generator to choose the positions ...
2
votes
1answer
26 views
FFT implementation using Danielson-Lanczos Lemma
I am trying to understand FFT algorithm explained here
...
4
votes
3answers
92 views
Explaining why FFT is faster than DFT for the general public?
How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
5
votes
2answers
43 views
How hard is it to solve for $P$ in $A = PBP^{-1}$?
From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that
$A = P \times B \times P^{-1}$
So, to solve the problem, if two graphs are ...
1
vote
1answer
56 views
Size of maximum clique given a fixed amount of edges?
Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges.
I think this is doable after realizing that ...
9
votes
1answer
154 views
Transforming an arbitrary cover into a vertex cover
Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$.
I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
2
votes
1answer
24 views
Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?
Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
-1
votes
0answers
36 views
How does one calculate a competitive (ranking) index? [closed]
I have a game where one completes multiple rounds and is given a score between 1 (worst) and 100 (best). There are near 10,000 types of rounds. I'd like to give players some feedback on their skill ...
0
votes
1answer
26 views
Similarities mergesort and Cooley–Tukey FFT algorithm?
Could you describe the similarities between mergesort and the Cooley–Tukey FFT algorithm?
14
votes
2answers
212 views
What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits ...
4
votes
2answers
80 views
Finding shortest and longest paths between two vertices in a DAG
Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
2
votes
0answers
41 views
Space filling between random 2D lines
Note that I had asked this question in GIS forum, although it
has gotten many up-votes, still has not received any answer. Hope you can
break the silence, some collaboration :)
Consider a ...
4
votes
1answer
56 views
How to find the minimum number of vertices whose removal make the graph disjoint
Given a graph $G = (V,E)$.
Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, i.e., every vertex is ...
4
votes
1answer
39 views
Extracting the set of chains from a partial order
Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)?
Note: I am asking here ...
1
vote
1answer
36 views
Finding the element that occurs more often than the other
I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.
Example : $aaaaaabbb$
Here ...
7
votes
1answer
97 views
Longest path in an undirected tree with only one traversal
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:
Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
3
votes
2answers
51 views
Finding no. of leaf nodes for each node in a BST
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is
$\qquad ...
2
votes
1answer
27 views
Correctness of Strongly Connected Components algorithm for a directed graph
I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph ...
1
vote
0answers
57 views
Bridge determination in undirected graphs
A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components.
I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. ...
0
votes
0answers
27 views
Bridge determination in undirected graphs [duplicate]
I need to determine all critical edges (bridges) in an undirected graph, in $O(|V|+|E|)$ time. From what I found out, I need to use a modified Depth-First search, but all pseudo-code algorithms I ...
1
vote
1answer
55 views
What is a computer year?
In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?
3
votes
4answers
140 views
The physical implementation of quantum annealing algorithm
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum ...
5
votes
2answers
46 views
Given a tree, find a vertex which maximizes the minimum distance to any leaf
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.
I am sure this problem has been studied before.
Does anybody know the ...
4
votes
1answer
20 views
Parallel merge sort using hypercube connection template
I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear.
What I ...
0
votes
1answer
39 views
How to check whether a graph is connected in polynomial time?
I have to solve the following problem:
Consider the problem Connected:
Input: An unweighted, undirected graph $G$.
Output: True if and only if $G$ is connected.
Show that Connected ...
5
votes
4answers
77 views
Space complexity for finding the minimum number outside the list of numbers
We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.
We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.
What is the ...
5
votes
1answer
53 views
Circles covering a rectangular, how to verify it?
This may be basic to some of you, but excuse my inexperience with comp. geometry:
Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a ...
5
votes
0answers
45 views
numerical integral vs counting roots
I have a problem that can be viewed in two different ways:
Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
Count (just ...
2
votes
1answer
76 views
Tarjan's Strongly Connected Component algorithm
I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):
On line 33 why is ...
8
votes
1answer
65 views
Average length of s-t (simple) paths in a directed graph
Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
4
votes
0answers
29 views
Relaxed Bin Packing Problem
The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin.
Is there an ...
