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
23 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
48 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
13 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
21 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
70 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
0answers
43 views

Count edges that can be removed

Given are N nodes and M edges, each edge connects two nodes. The edges are bidirectional , i.e., substance can flow in either direction through the edge. We start from node 1 and end up at node N. ...
-1
votes
1answer
74 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
45 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
49 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
29 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
0answers
36 views

Distribute coins among N persons [duplicate]

Suppose we have infinite number of coins.Now we need to give some coins to $N$ persons in such a way that product of the number of coins any two adjacent persons have, is not greater than $M$. ...
-1
votes
2answers
89 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
78 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
38 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
141 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
87 views

Count distinct triplets with sum less or equal to M [closed]

Given an array A we need to find the number of unique triplets of integers from a given array A such that their sum is less than or equal to a given integer M. ...
0
votes
0answers
2 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
20 views

How do you determine the values of alpha, beta and rho in ant colony optimization? [closed]

I am implementing a software application that leverages the ant colony optimization algorithm and I'm having some trouble figuring out what the values of alpha (pheromone weight), beta (heuristic ...
0
votes
0answers
37 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
33 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
54 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
24 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
184 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
16 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
23 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
30 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
55 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
30 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 ...
0
votes
0answers
22 views

Sharing between 3 people

I have a problem on what im thinking since 2 weeks but i got no idea how to solve it. There are gifts with given values and we need to share these gifts between people fairly. Fair sharing in this ...
0
votes
0answers
13 views

Integer multiplication in 5T(n/3) [duplicate]

x and y has n bits x=x0*(10^2n/3)+x1*10^n/3+x2 y=y0*(10^2n/3)+y1*10^n/3+y2 x*y=x2y2+(x2y1+x1y2)10^n/3+(x2y0+x1y1+x0y2)10^2n/3+(x1y0+x0y1)10^n+x0y0*10^4n/3 now 9 multiplication of n/3 bit numbers ...
2
votes
3answers
60 views

Why does this loop yield $\pi/8$?

Was doing some benchmarks for the mpmath python library on my pc with randomly generated tests. I found that one of those tests was returning a multiple of $\pi$ consistently. I report it here: ...
2
votes
1answer
31 views

I understand what a division ring is, but cannot find any examples. Can anyone give me one? [duplicate]

From Wolfram Alpha I have that the definition of a division ring is; "a ring in which every nonzero element has a multiplicative inverse, but multiplication is not necessarily commutative". Can ...
3
votes
0answers
31 views

Decide if radical expression equals a given rational number

Given a radical expression an a rational number. Is there an algorithm to decide if the expression equals the number? Example: $(\sqrt{\sqrt[5]{74} - \sqrt[14]{78}})^{356}+\sqrt[6]{63} \overset{?}= ...
0
votes
1answer
21 views

A recurrence equation for the number of multiplications in an algorithm for computing powers

We were asked the to find the recurrence equation for the number of multiplications for the following algorithm as a function of N. For simiplicity, let $ N = 2^k $ and is a positive integer: I ...
0
votes
1answer
20 views

Permutation and Combination - Algorithm

Given Data in the problem For I= 1 to 10 print(x) means executing the immediate next line after for loop command 10 times. So here it prints "x" 10 times. Typical simple for loop construct in ...
0
votes
0answers
19 views

multiplication of two numbers in 6 of n/3 bits 6T(n/3)

multiplication of two numbers x*y ----> x =(x0*10^(n/3)+x1*10^(n/3)+x2) and y=(y0*10^(n/3)+y1*10^(n/3)+y2) x*y= x0*y0+x1*y1+x2*y2+x0*y1+x0*y2+x1*y0+x1*y3+x2*y0+x2*y1 it is 9 multiplication of ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
1
vote
0answers
16 views

Insertion and merge sort complexity - CLRS 1.2-2

My question is related to an already answered question: here (New here, could not comment on that answer). Is there a way to solve for $n$ in $2^n = n^k$ without resorting to trial and error or ...
-2
votes
1answer
50 views

Find minimum possible area of brush

A rectangular brush has been moved right and down on the painting. Consider the painting as a $n × m$ rectangular grid. At the beginning an $x × y$ rectangular brush is placed somewhere in the frame, ...
0
votes
1answer
47 views

Finding the inverse of Hadamard matrix [closed]

The $Hadamard\,\,matrices\,\,{H_0},\,\,{H_1},\,\,{H_2}, \ldots $ are defined as follows. Let ${H_0}$ be the $1 \times 1$ matrix $\left[ 1 \right]$. For $k = 1,2, \ldots ,$ let ${H_k}$ be the ${2^k} ...
0
votes
1answer
62 views

Graph diameter and average pairwise distance

How do I prove that for a graph G, I can always find a constant c>0 such that $$ \frac{diameter(G)}{average \ pairwise \ distance (G)} > c $$ where $$ average \ pairwise \ distance = ...
0
votes
1answer
52 views

How can I justify it formally?

Given the following algorithm: Function Fun(int n){ int j,k,t=1; for (j=0; j<=4n^2; j+=4){ for (k=j; k<=4*sqrt(n); k+=4){ t+=8; } } } I ...
0
votes
1answer
36 views

Algorithm - the longest chord whose supporting line contains a given point, in a convex polygon

"Let $P$ be a convex $n$-gon and $q$ a point in the plane. Find an algorithm to compute the longest chord whose supporting line contains q." When $q$ is external to $P$, I think I can prove the ...
1
vote
2answers
27 views

algorthm to find a farthest point in a convex polygon to an external point

Given a point $q$ external to a convex polygon $P$, propose an algorithm to compute a farthest point in $P$ to $q$. One can always have at least one vertex of $P$ in the set of farthest points of $P$ ...
3
votes
1answer
29 views

algorithm to find closest point in a convex polygon from an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$. A linear algorithm of course works, computing the ...
4
votes
1answer
164 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
1
vote
1answer
51 views

Make whole array as zero

Given an array of N elements some of which are positive and some are negative now some positive valued elements can give their value to negative valued elements.Now we need to make whole array as zero ...