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

learn more… | top users | synonyms (1)

1
vote
0answers
16 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 ...
1
vote
1answer
11 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
27 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
26 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
33 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
20 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
39 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
12 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
32 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
21 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
30 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
20 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
38 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
37 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
24 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
54 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
0answers
23 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
51 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 [on hold]

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 [on hold]

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
32 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$ ...
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
27 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
1answer
51 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
18 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
52 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
21 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
17 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
36 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 ...
0
votes
1answer
43 views

These symbols are referring to? BOOK: Introduction to Genetic Algorithms by S.N.Sivanandam · S.N.Deepa

I take this set of initialization (PAGE 120) from a genetic algorithm book with title: Introduction to Genetic Algorithms by S.N.Sivanandam & S.N.Deepa..here is the link ...
2
votes
0answers
39 views

Polynomial decomposition

I've just recently learned about the neat algorithm that, given a polynomial $f$ finds (non linear) polynomials $h,g$ such that $$f = g \circ h \quad (1),$$ or decides that there are no such ...
0
votes
0answers
20 views

Find cross product of two points A and B [closed]

Find cross product of two points A and B. Note, Point A and B are in latitude,longitude format. i.e A = {lat,long}
0
votes
0answers
26 views

Find a point C on line segment AB such that line segment DC is perpendicular to AB. D is a point outside the line segent

Find a point C on line segment AB such that line segment DC is perpendicular to AB. D is a point outside the line segment. Note, Point A,B and C are in latitude,longitude format, i.e A = {lat,long} ...
9
votes
1answer
96 views
+100

Simplifying polynomials

Suppose I have a (multivariate) polynomial with coefficients in $\mathbb Z$ or $\mathbb Q$, given in fully expanded form. How can I simplify this to reduce the number of elementary operations ...
2
votes
1answer
35 views

Are there algorithms for solving simple functional equations?

So somebody posted yesterday asking a question for continuous solutions $f$ satisfying $f(x+y) = f(x)f(y)f(xy)$. Continuity could be used for a simpler proof but then somebody posted a solution ...
1
vote
1answer
43 views

$O(1)$ algorithm for coin change w/out nickels

For the coin changing problem in the case without nickels (only quarters, dimes, and pennies available), assuming you use quarters until $x < 50$ since it's better to use quarters for $x \geq 50$; ...
1
vote
0answers
24 views

The number of subtraction step in binary GCD algorithm

Binary GCD algorithm is a algorithm which find a GCD of two positive integers. The algorithm proceeds recursively using the following reduction: $$(a,b)=\begin{cases} a&\text{if }a=b\\ ...
2
votes
1answer
41 views

Modify the closest-pair algorithm to use the $L_\infty$ distance.

I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to ...
0
votes
0answers
26 views

Algorithm complexity for roots of a polynomial [closed]

For a polynomial in one variable of degree $n$, what is the algorithm complexity for root finding of the best/typically used algorithm?
4
votes
1answer
70 views

Proof by counter example of optimal solution for Coin Changing problem (no nickels)

I'm a tutoring a student whose working on the classical coin changing problem. For those who are unfamiliar with problem or the greedy algorithm used for it. The goal is find the fewest number coins ...