Tagged Questions

Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
10 views

Can O(ndlog(d)) + O(n^2d) + O(n^3) be simplified?

Can $O(nd \log(d)) + O(n^2 d) + O(n^3)$ be simplified without increasing the time complexity? Can $O(nd \log(d)) + O(n^2 d)$ become $O(n^2 d \log(d))$? Can it all become $O(n^3 d \log(d))$? Please ...
1
vote
1answer
10 views

Algorithm Running Time

Given an algorithm with a running time $$T(n)=5T(n/2)+n^2$$ So the number of nodes at a depth $i$ would be: $5^i$ The input size for each node at $i$ would be: $n/2^i$ Agreed. Then it states that ...
2
votes
0answers
21 views

How to find an expression for a number via a given set of math operators and constants?

Consider one gives you $n$ digits of a (possibly irrational) number and a finite set of math operators and constants, like $\{\sin(x), \ln(x),+,\times, \pi,e,7\}$. Then he asks you to build a ...
0
votes
0answers
12 views

Variation of Bin-packing with classes of bins and objects

I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows- We have objects of varying sizes, which can be ...
1
vote
2answers
33 views

An algorithm which takes long time to halt

I want to find an algorithm such that takes 10 inputs as natural number returns 1 output as natural number between 1 and 10. (including 1 and 10) It means it should be a function f($x_0$, $x_1$, ...
2
votes
1answer
38 views

Best score in this puzzle

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together. ...
0
votes
0answers
12 views

algorithm to generate some type of words in a finite group

In order to solve a problem (that is off topic to this subject) I would like to know if there is an algorithm that gives me the following: Given a finite group $G$ and some of its elements e.g. $a,b,c ...
0
votes
1answer
17 views

Calculating coefficients of interpolating polynomial using Neville's algorithm

First of all, sorry for my bad math terminology as it's not my native language and I may misuse some terms in English. I've been tasked with writing an application which calculates the general ...
0
votes
0answers
14 views

Interval in future

I have two intervals (times). For example, t1= 0:17, in this interval, we are now and interval t2=0:12, and the time, when was the time "time2". time2WasBefore = 0:04( which means that t2 was from now ...
4
votes
1answer
26 views
2
votes
2answers
66 views

Is it possible to express the idea of a number bigger than any other number ($\infty$) in programming languanges? [on hold]

I'm studying graphs and algorithms, most of the algorithms we're using (such as Prim's algorithm), have the need of a table with a symbol $\infty$. Which in some contexts mean that it is the biggest ...
0
votes
1answer
21 views

Help regarding solving the question

When a particular switch in the grid to toggle (if switch is ON you turn it OFF and vice versa),then the switch itself and its neighboring (up,down,left,right) switch will also get toggled. Given the ...
0
votes
1answer
38 views

Understanding Mathematical Symbols in Algorithms

Just a quick question here. I am working on an assignment for algorithms involving dynamic programming. Don't worry, this isn't a question about my assignment, just a question about understanding a ...
0
votes
1answer
30 views

How to find if an array has at least 10 unique integers in $O(\log n)$?

I am given a sorted array of integers. I want to find out if the array has at least 10 unique integers. I know this can easily be done with an algorithm that runs in $O(n)$ simply by going through ...
-1
votes
1answer
21 views

Spaced repetition algorithms

Can someone tell me how the Super Memo spaced repetition algorithms (http://www.supermemo.com/english/algsm11.htm) were calculated? How does someone go about designing algorithms like this? Is there ...
1
vote
0answers
23 views

Algorithm working with exact real numbers [on hold]

Can an algorithm working with exact real numbers outperform (say exponentially) a regular algorithm (working with finite natural numbers)? (just like quantum algorithms may outperform regular ...
0
votes
1answer
14 views

Need help using the neighborhood search heuristic

I need help using the following neighborhood search heuristic on the set S that is partitioned into A and B where A = {1, 2} and B = {3, 4}. This set partition is our initial solution x_0, and the ...
-1
votes
0answers
15 views

How to prove greedy algorithm optimality

Let S be a set of intervals (containing n number of intervals) of the natural numbers that might overlap and N be a list of numbers (containing n number of ...
0
votes
0answers
24 views

Algorithm of Equation reduction

I'm working on a programm wich have to reduce an equation. At this time, My programm can parse an equation as binary tree. I have searched for algorythm of reduction since tow days but i haven't ...
0
votes
0answers
17 views

Adding an edge to a MST generated from a distance matrix

Given an $N\times N $ distance matrix, but not an adjacency matrix for a connected, weighted, undirected graph $G$, I've managed to find a minimum spanning tree (with $N - 1$ edges) using Prim's ...
0
votes
0answers
30 views

How to draw a graph from edges [on hold]

If I have a set of edges and want to to plot the graph, what algorithm should I use? Each node has an id so it's kind of like projecting 1d points into 2d. I know that GNUplot can do this so I know ...
0
votes
1answer
17 views

Calculating a perpendicular distance to a line, when using coordinates (latitude & longitude)

I'm trying to implement the Douglas-Peucker algorithm for simplifying a recorded GPS track (a list of coordinates). All implementations I can find assume a simple X/Y grid of squares, however ideally ...
2
votes
0answers
35 views

Defining nth element of combinatorics

Let's say I have a set = {$1, 2, 3, 4, 5, 6, 7, 8, 9, 10$} and I'm interested in the $C^{10}_3 = \frac{10!}{3!(10-3)!} = \frac{10*9*8*7!}{3!7!} = 10*3*4 = 120$ Now, say $1^{st} element = 1, 2, 3$ ...
0
votes
0answers
10 views

help solve this recurrence realtion

1.T(n) = T(n^(1/3))+3 and 2.T(n) = 2T(n − 2) + 2 By using Master theorem. For the second one I guess the solution is θ$(2^n)$.
0
votes
2answers
71 views

cut cake problem

A circular cake has been cut with $n$ straight cuts, where each cut goes through the entire cake from one point on the circumference to another point on the circumference, no two cuts share a point on ...
1
vote
0answers
25 views

Finding maximum independent set in sparse graph

Let $G=(V,E)$ be a directed graph such that each node has out-degree exactly $1$. What is an algorithm to find a maximum independent set? Is it possible to do this in $O(|V|)$ time? (Note that ...
0
votes
1answer
21 views

What is the length of the longest decreasing sequence in integer matrix?

Given a finite $m \times n$ matrix $M$ with all distinct integers, we travel it following two simple rules: The travel can start from any cell, say, $M[i,j]$. At each cell $M[i,j]$, it computes the ...
0
votes
1answer
21 views

Finding the first intersection of a horizontal ray with many vertical line segments in $O(\log n)$ time

Design a data structure and a search algorithm to solve the following problem. It should be able to answer the query in O(log2 n) time. A high-level description of your data structure, the search ...
0
votes
0answers
9 views

similarity measure between sentences

I would like to know how the normalization factor was evaluated in the paper (http://dl.acm.org/citation.cfm?id=1220627). Also in the example "The church bells no longer rung on Sundays" I noticed ...
1
vote
0answers
37 views

Masters' thesis in algorithmic graph theory

I would like some ideas on topics in algorithmic graph theory which would be suitable for a masters' thesis. What sort of problems would be suitable for this level? Because it is at masters' level, no ...
1
vote
1answer
50 views

Can books be arranged into bags?

I'm trying to find an algorithm (sub exponential) to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags ...
0
votes
1answer
21 views

Why outer product isn't backward stable

Outter product isn't backward stable. This is because output matrix most likely has rank one and thus can't be represented in the form $(x + \delta x)(y + \delta y)^*.$ Also we know that if output ...
0
votes
1answer
43 views

$O(n\log^2(n))$ algorithm for finding closest pair of points between two sets.

For example, say that we are given a set of points where each point is labeled White or Black. How can we compute the pair of ...
0
votes
0answers
18 views

Maximum flow between three edges in a flow network

I am assuming that the following fact is true in a flow network N(G(V,E) ,s,t,c ) Let us say A,B,C belongs to E in a finite directed graph G. F(x,y) is maximum flow in the network N, then the ...
1
vote
1answer
28 views

Algorithm - iteration method

$$\begin{align} &T(n)=n+T(n-1)= \\ &= n + (n-1)+T(n-2)= \\ &= n + (n-1)+(n-2)+T(n-3)= \\ &= n + (n-1)+(n-2)+...+2+T(1)= \\ &= \frac{n(n+1)}{2}-1+T(1) \\ & \mathrm{Hence,} ...
0
votes
0answers
15 views

Increasing the speed of a depth first search.

I am looking for ways to increase the speed of a depth first on a graph when trying to find a path from a source node to a destination node. One thing I have tried is to perform a bidirectional ...
1
vote
2answers
33 views

Optimal Number of White Balls

There are C containers, B black balls and infinite number of white balls. Each container should have at least one ball. Each of the containers may contain any number of black and white balls. Action ...
1
vote
0answers
30 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
2
votes
1answer
44 views

Strategy to find out set with nice subset structure

Let $A=\{0,1\}^n=\{(a_1,a_2,\ldots,a_n)\mid a_i\in\{0,1\}\}$. Let $B\subseteq A$ be such that if $(b_1,b_2,\ldots,b_n)\in B$,$ (c_1,c_2,\ldots,c_n)\in A$, and $c_i\leq b_i$ for all $i$, then ...
0
votes
1answer
34 views

How to quickly determine running time of such recurrence relations?

$$T(n)=5T(\frac{n}{2})+n\log n$$ $$T(n)=9T(\frac{n}{3})+n^2$$ $$T(n)=2T(\frac{2n}{3})+n^{1.5}$$ What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
0
votes
2answers
35 views

Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$. I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern: $T(n/3) = 3T(n/9)+\log (n/3)$ $T(n) = 3[3T(n/9)+\log ...
1
vote
0answers
37 views

Algorithm to compute wether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
0
votes
0answers
24 views

Optimized way to compute L1 distance matrix

I'm computing distances between two groups of multi-dimensional points giving a matrix of distances pairwise between points. For the L2 (euclidean) distance I can use optimized matrix multiplication ...
0
votes
0answers
18 views

Breaking Ties Alphabetically Using Kruskal's Algorithm

Kruskal's Algorithm picks the next edge simply by picking the lightest edge. Doesn't that make breaking ties alphabetically impossible? If I had a graph where two edges ...
1
vote
1answer
38 views

Algorithms: Maximizing $\Pi \, a^{b}$ (NOTE: Homework)

First I would like to say that this is a homework assignment, so I'm not looking for someone to give me a solution. Just a little guidance if what I have is wrong or inefficient: Given two sets $A$ ...
1
vote
0answers
14 views

Minimal and maximal elements of a set consisting of sums of random variables

Consider a set of $n$ correlated random variables, $A =\{X_1, \ldots, X_n\}$. Suppose that I have another set, $B$, of all possible combinations of size $k$ of the random variables. Now, if for each ...
1
vote
1answer
44 views

Generate all permutations of a string containing repeated characters

I was writing a program to print all the permutations of a string. I came up with the following: ...
0
votes
0answers
27 views

Finding points on a curve - approximate

my issue is mathematical but comes from image processing. The image beneath is for a better understand of the problem. I've to detect three dots (black - marked with red arrows). The green points are ...
0
votes
1answer
33 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
1
vote
0answers
23 views

Is shunting-yard algorithm needed if there is no parenthesis?

I am trying to find a permutation (with replacement) of operators(such as addition and multiplication) that makes numbers 1 2 3 , ..., 9 result in to some numbers. My guess is to find all possible ...