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

Need help to write the algorithm

I want to write an algorithm, that sorts the following list, using the Insertion Sort: 50, 200, 1, 102, 8, 52, 69 Could you explain me how I could do this?
0
votes
0answers
7 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
31 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
41 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
14 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
0answers
19 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
17 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
11 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
32 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
40 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
33 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
28 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
36 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
21 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
17 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
votes
0answers
60 views

MERGE(L1,L2) two sorted list [on hold]

Merge(L1, L2), below, is a function which merges two sorted linked lists L1 and L2, and outputs a single sorted linked list. By "sorted", we mean increasing order. ...
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
40 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
32 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
22 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 ...
1
vote
2answers
39 views

O(n) algorithm for minimizing Manhattan distance between points

Given two sets points with each point either "Black" or "White", design an algorithm to find the pair of points, one that is black and another that is white, such that the Manhattan distance between ...
1
vote
1answer
39 views

What type of series is this: $k^n + k^{n-1} + k^{n-2} + k^{n-3}+\dots$

I am wondering what type of series this this, where you have some constant (let's say 4) to the power of n, summed up where each new exponent keeps going $n-1, n-2, n-3, n-4, ...$ and so on. So, ...
1
vote
1answer
27 views

Using recursion tree to solve recurence T(n) = 3(n/2)+n

I am trying to solve the recurrance of the function, T(n) = 3(n/2)+n where T(1) = 1 and show it's time complexity. n can be ...
1
vote
3answers
56 views

n! v.s. $a^{n}$ How can we know which one is faster without graphing?

n! v.s. $a^{n}$ If we are given an arbitrary number a (a>1). How can we know which one is faster as n->INFINITY without graphing?
1
vote
0answers
31 views

Big O-notation proof: show that $x^{2}+5x+11$ is $O(x^{3})$

Show that $x^{2}+5x+11$ is $O(x^{3})$ by providing the smallest value of the witness $C$ such that $|f(x)|≤C|g(x)|$ whenever $x>11$. What's the value of $C$?
0
votes
1answer
26 views

What is a Lattice?

To be up front, I was helping my friend with his programming assignment and I stumbled upon the following sentence List all the lattices (subsets of S) on S with size K it later says that the ...
2
votes
1answer
63 views

Step by step LMS for learning a linear function

Disclaimer Since this is an exercise assignment I'm not looking for a complete solution but for help that enables me to solve it on my own The task Given the error function ...
0
votes
0answers
16 views

Binary Search when no “fixed” answer…? (Font Sizing)

So I'm trying to figure out how best to implement a binary search algorithm to find the "optimal" font size for a piece of text to fit into a given space, to the nearest 0.5pt. My understanding is ...
-1
votes
0answers
35 views

Proof of big theta using induction [closed]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove that ...
-2
votes
0answers
22 views

count minimum spanning tree [closed]

if there is no three edges have the same length in a graph (but two edges can have the same length). How many di efferent MSTs can you have in the worst case? Give an example to show that How fast ...
0
votes
0answers
41 views

Prove probing to be permutation

So I have been taught that probe sequences (h(k, 0), h(k, 1), ... , h(k,m - 1)) are meant to be a permutation (0, 1, ... ,m - 1), but how does one prove that? I was asked this question in an ...
0
votes
0answers
36 views

Method for finding bridges and articulation points using DFS

How can we find all bridges and articulation points using DFS? Suppose we have the following DFS psuedocode (from Wikipedia): ...
0
votes
0answers
30 views

Find the minimum capacity edge that is maximized among all paths from $s$ to $t$

Consider some weighted, directed graph $G=(V,E)$. How can we find the edge that is the maximum of all minimum values along paths from $s$ to $t$? For example, if there are two paths from $s$ to $t$ ...
1
vote
1answer
18 views

Prove that there always exists a fair driving schedule

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
0
votes
1answer
14 views

Determine whether or not a binary number is divisible by $3$

Let $K$ be a natural number with $n$ binary digits. Is there an $O(n)$ method for deciding whether or not $K$ is divisible by $3$? $3|K \iff d_1-d_2+d_3-d_4\dots\pm d_n=0$ works correctly up to ...
0
votes
0answers
28 views

Number of strings of length n generated using m different characters.

We need to find the number of sequences that can be made from m different characters (X0, X1, ...., X(m-1)). An array arr[m] of size m is given, ith element tells that character Xi should be used ...
0
votes
0answers
24 views

Determining whether there is a valid rounding in a table of numbers

Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|& 27\\ 1.019 & 2.045 & 0.936 &|& 4\\ ...
1
vote
2answers
57 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
0
votes
0answers
19 views

An algorithm to find if two sentences are at edit distance $1$

Definition: Two sentences $S_{1}$ and $S_{2}$ they are at edit distance $1$ if $S_{1}$ can be transformed to $S_{2}$ by: adding, removing or substituting a single word. Examples: Consider each ...
2
votes
0answers
54 views

area estimation with tiling

For any given shape drawn on a graph paper, a kid can calculate the area of any shape by counting the tiles with a simple formula: any edge covering 50% or more, mark the tile; total area = sum all ...
0
votes
0answers
22 views

Modulo and power calculation [closed]

Let $A{^-}{^n}$ mod X = ($A{^-}{^1}$ mod X )${^n}$ mod X for $n>0$ Now we want to compute $A^B$ mod X fro given A,B and X provided A and B are coprime. Note : $A{^−}{^1}$ mod X refers to the ...
0
votes
0answers
19 views

Calculate sum of distinct pairs [closed]

Given an array A we need to find the sum of all distinct pairs of indexes from the array and adds the value ⌊$A[i]+A[j]\over A[i]×A[j]$⌋ to the sum Note: ⌊$A\over B$⌋ is the integer division ...
0
votes
0answers
18 views

Understanding the difference in (double) diagonally traversing trough a square matrix

I have been struggling with an algorithm to solve the PE Problem #149. I was able to find a solution (algorithm) for this problem on the internet, which can be found here. I do understand this ...
1
vote
1answer
31 views

Using Extended Euclidean Algorithm

Apply the Extended Euclidean Algorithm of back-substitution to find the value of $\gcd(85, 45)$ and to express $\gcd(85, 45)$ in the form $85x + 45y$ for a pair of integers $x$ and $y$. I have ...
0
votes
2answers
35 views

How to design a function $f$ such that $f(x) \not\equiv f(y)\,(\text{mod } n)$? [closed]

$x$, $y$, and $n$ are known, $x \neq y$, and $x\equiv y\,(\text{mod } n)$. I try to design a function $f$ that $f(x) \not\equiv f(y)\,(\text{mod } n)$. Thanks
0
votes
1answer
46 views
+150

Defining ellipse using points and normal vectors from them

There is an article on how to detect circles in images using pairs of gradient vectors (assuming the circle is dark and background is bright). The thing is that gradient of image intensity at each ...