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
1answer
49 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 ...
1
vote
1answer
64 views

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
44 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
38 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} ...
10
votes
1answer
139 views

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 ...
3
votes
1answer
39 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
2answers
49 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
25 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
61 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 ...
4
votes
1answer
105 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 ...
2
votes
1answer
70 views

Challenging Algorithms Question: Proving that upper bound for computing 'silhouette' points is nlog(n)

Given a set of points (on the left). The silhouette set of these points is shown to the right. In this problem, all rectangles are defined by two points, $(0, 0)$ and $(x_i, x_j)$. Formally, for a ...
0
votes
1answer
34 views

Karatsuba multiplication algorithm of two 6 digit decimal numbers.

What are the min and max number of single digit multiplications, involved in recursive karatsubha multiplication of two 6 digit decimal numbers? I found different results on different numbers. But I ...
0
votes
1answer
46 views

Help with using Master Theorem on Floor/Ceiling Functions [closed]

I have to use the master theorem to find the asymptotic growth of this function in Big-theta notation. T(x) = T(⌈x/4⌉) + T(⌊x/4⌋) + √x How should I approach this ...
1
vote
1answer
62 views

Help with using Master Theorem on $T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$

I want to use the Master theorem to solve the following recurrence. $$T(n)=9T(n/3) + \Theta(n^2/\operatorname{lg}(n))$$ We can easily see that $a=9$ and $b=3$ and $f(n) = n^2/\operatorname{lg}(n)$. ...
0
votes
1answer
31 views

A Question Regarding Asymptotic Notations

Well, here I am again, stuck with my algorithm's class HW question again... . $g(n) = \Theta(n^2)$, $f(n) = g(n) + g(n-1) + ... + g(2) + f(1)$ Given the conditions above, is it suitable for me to ...
1
vote
3answers
184 views

Number of binary palindromes in a range

I want to find the number of binary palindromes from $1$ to $N$. $0 \lt N \lt 2^{32}-1$. I observed a pattern that if we have an odd-length binary palindrome, it can generate only $1$ even-length ...
0
votes
1answer
28 views

How to scale this set of points?

I have a set of 8 points: [x1, y1, x2, y2, x3, y3, x4, y4] they are x y pairs. We see below that easeIn_right has start point of ...
0
votes
2answers
30 views

Are there algorithms that traverse from two sides of a graph to find an s-t path.

Say I have a directed graph with a source and destination node s and t and I want to see if there's a path that exists between those two nodes. Intuitively I would think that the fastest way to do ...
6
votes
2answers
93 views

Eating chocolate game on grid

Given is a chocolate of size $m\times n$. Anne and Birgitte plays a game, with Anne starting. In each turn, the player has to divide the chocolate into two rectangular parts along the lines, and eat ...
0
votes
0answers
14 views

Randomize algorithm three times for modified values

Let $F:\{0,\ldots,n-1\}\rightarrow\{0,\ldots,m-1\}$ be a function such that $$F((x+y)\bmod n)=(F(x)+F(y))\bmod m$$ for $0\leq x,y\leq n-1$. Now, $1/5$ of the values of $F(x)$ that we store have been ...
1
vote
1answer
25 views

Strictly convex sequence

A sequence of numbers $A=(a_1, a_2, \dots, a_n)$ is called strictly convex, if there is a $k$, with $1 \leq k \leq n$ so that for all $1 \leq i \leq k-1$ we have $a_i>a_{i+1}$ and for all $k \leq i ...
0
votes
1answer
14 views

Asymptotic $T(n)=T(\sqrt{n})+1$

I would like to find the complexity of $T(n)=T(\sqrt{n})+1$ I did : $$T(n)=T(\sqrt{n})+1$$ $$T(n)=T(n^{1/2})+1$$ $$T(n)=(T(n^{1/4})+1)+1=T(n^{1/4})+2$$ And after $k$ steps : ...
1
vote
2answers
39 views

Efficiently calculating the 'prime-power sum' of a number.

Let $n$ be a positive integer with prime factorization $p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$. Is there an 'efficient' way to calculate the sum $e_1+e_2+\cdots +e_m$? I could always run a brute ...
1
vote
2answers
52 views

Contradiction Involving Division Algorithm.

Given the smallest positive integer $d$ such that $d = ax + by$, prove that $d\mid a$. To do this, you must use a proof of contradiction. Assume $d$ doesn't divide $a$, and apply the division ...
0
votes
0answers
14 views

Information based complexity — existence of algorithms

Is there a situation in IBC literature, where a constructive algorithm that is significantly better than the best known algorithm is shown to exist?
1
vote
1answer
23 views

Height of the tree : $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$

Let the tree described by $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$ Can someone explains why the height is $\log_{8/5}{n}$ I don't know how to proceed
0
votes
1answer
75 views

Improving the Edit Distance Algorithm

I applied an Edit Distance Algorithm for similarity between two strings over the lowercase latin alphabet, where the first string has length $m$ and the second length $n$. However I want to improve ...
-1
votes
1answer
77 views

Check if $N$ is of form $6A + 8B$

Given a number $N$ we need to check if its of form $6A + 8B$ .If its of this form then we need to check if $B$ can be greater than equal to $1$ or not. Like $24$ is of form $6A + 8B$. Also $B$ can ...
0
votes
0answers
13 views

Topic for attribute exploration

I'm writing my bachelor theses about the interactive algorithm 'attribute exploration'. For this I want to add an example. In the literature I found many such examples, like exploration of finite ...
1
vote
0answers
52 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
1
vote
2answers
51 views

Efficient software implementation of $x^2+3y^2=N$

I would like to implement a solver (in C) for the Diophantine equation $x^2+3y^2=N$ for non-negative integers $\{x,y\}$ and positive integer $N$. I have read online that one has to prime factorize N ...
0
votes
0answers
33 views

game theory subgame perfect equilibria

Let s be a strategy pro le in an extensive game with perfect information 􀀀; let h be the current history, i.e. the sequence of actions taken by the players. let P(h) be the player to play next after ...
-1
votes
2answers
113 views

Check if we can turn a string into a palindrome by reversing a substring

Given a string consisting of lower-case characters from English alphabets, we want to reverse a substring from the string such that the string becomes a palindrome. Note : A Palindrome is a string ...
2
votes
1answer
81 views

Find different sequences of game to find winner

Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
0
votes
1answer
18 views

Assigning integers to a list of items?

I have an ordered list of items. Some items already have integer weights. It is desirable that the difference between two adjacent items is as uniform as possible. What would be a good algorithm to ...
1
vote
1answer
42 views

Proving n(log(n)) is O(log(n!))

I want to prove $n(\log(n)) \in O(\log(n!))$. I don't really understand how to prove this statement. From the definition, we would have that: $\exists c > 0, \exists N$, so that $\forall n \geq N, ...
1
vote
1answer
151 views

Count ways to distribute candies

N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students ...
0
votes
0answers
3 views

BSS Statistic Independent Sources

When reading about the Blind Source Seperation algorithm, I read that one of the conditions was that sources must be statistical independent of each other. Can someone provide me an example when two ...
0
votes
0answers
38 views

Algorithm to iterate so that the product of the two numbers iterated is always smaller than the previous iteration

I'm looking for some kind of algorithm that iterates through two numbers, say $x$ and $y$, so that $x*y$ is always smaller than $x*y$ in the previous iteration. All numbers need to be integers, and ...
1
vote
2answers
38 views

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$?

If $f(n) = O(g(n))$ and $f(n) \not\in o(g(n))$, does $f(n) = \Theta(g(n))$? Well, this is just another algorithm's class HW question, but I don't seem to be able to figure out how to prove or ...
0
votes
0answers
81 views

Prove the correctness of Tarjan's off-line least-common-ancestors algorithm

Tarjan's off-line least-common-ancestors algorithm is given as follows: LCA($u$) Make-Set($u$) Find-Set($u$).$ancestor$ = $u$ for each child $v$ of $u$ in $T$ $\quad$ LCA($v$) ...
1
vote
2answers
27 views

Find the minimum possible order at a restaurant for a party of n people

I want to find an efficient algorithm for determining the minimum possible order total for a party of n people at a restaurant, assuming that the items in the order are unique, and they will each ...
-4
votes
1answer
201 views

Count good numbers in between L and R

Let length(A) denote the count of digits of a number A in its decimal representation. All non-negative numbers of length 1 are Good. Further, a number X with length(X) $≥ 1$ can also be considered ...
0
votes
1answer
17 views

Enumerating the elements of $\mathbb{Z}^n$

The elements of $\mathbb{Z}$ can be enumerated as $0, 1, -1, 2, -2, 3, -3, \ldots$. Similarly, the points of the lattice $\mathbb{Z}^2$ can be enumerated $$(0,0), (1,0), (0,1), (-1,0), (0,-1), ...
0
votes
1answer
24 views

Given N points with integers coordinates find the number of parallel lines

nC2 will give the number of lines we can form in O(n^2) complexity. Finding the slope of these lines in O(n^2) complexity and store them in an array, say x. Sort x in O(n^2 logn) complexity. Search ...
0
votes
0answers
34 views

Directed DFS graph - one vertex

I am having trouble trying to figure out the following problem: Give an example of DFS(depth-first-search) on a directed graph where vertex v is the only vertex in some DFS tree despite the fact that ...
1
vote
2answers
62 views

Sort sequences of the form ABCABCABC, ABABAB, ABCDABCD, etc.

You are given a sequence of distinct elements $P$ and a positive integer $R$. Consider the sequence obtained by repeating $P$ $R$ times and concatenating together. For example, if $P = \langle A, ...
0
votes
0answers
9 views

Algorithm to compare set of objects given a metric

Assume I have Objects $x\in X$ with an associated metric $d:X\times X\to\mathbb N_0$. I want to find a metric $d^*: \mathcal P(X) \times \mathcal P(X) \to\mathbb N_0$ wich compares sets of these ...
-2
votes
1answer
34 views

Cover nodes at distance X from given node

Given a tree with $N$ nodes and $N-1$ edges where each edge has weight equal to $1$. Now we are given a query which provides $Y$ pairs of type $(A,B)$ It means cover all those vertices that are at ...