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
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
37 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 ...
1
vote
2answers
44 views

Members of the sequence greater than 1 less than N

Suppose N is a positive integer. How many decreasing integer sequences are there such that members of the sequence are greater than 1 but less than N… I have tried to come up with an expression for ...
1
vote
1answer
22 views

Modelling problem

i have this problem and i have to model it in a boolean formula. Assuming that variables can have value 0 or 1 and V is OR and ∧ is AND. I have n boolean variables x1,x2......xn. i want a formula ...
-1
votes
0answers
55 views

Maximum pairs of men and women

There are shoes of n different colors. We will enumerate the colors from 1 to n. For each i, there are M[i] pairs of men's shoes, W[i] pairs of women's shoes and S[i] pairs of shoelaces of color i. ...
2
votes
1answer
51 views

Make a one sequence

A sequence of integers is a one- sequence if the difference between any two consecutive numbers in this sequence is -1 or 1 and its first element is 0. More precisely: a1, a2, ..., an is a ...
1
vote
1answer
21 views

Generating sets with exactly one mutual element

I have a quite interesting task. I need to generate all $n$-element sets, such that every two of them have exactly one mutual element. There are $m$ elements to choose from and can be assumed, that ...
0
votes
2answers
72 views

Arrange the following growth rates in increasing order: $O (n (\log n)^2), O (35^n), O(35n^2 + 11), O(1), O(n \log n)$

I want to Arrange the following growth rates in increasing order This order are following : $O (n (\log n)^2), O ((35)^n), O(35n^2 + 11), O(1), O(n \log n)$ Please give me idea how to arrange growth ...
4
votes
2answers
31 views

Can we find an $x, y : x < y$ and $x, y > 0$ and $\lfloor \frac{n}{x}\rfloor$ < $\lfloor \frac{n}{y}\rfloor$ for some integer $n > 0$?

I know there are no solutions when we have just the fraction without the floor, but how do we consider solutions when the floor is there?
0
votes
0answers
25 views

3D extension of Euclidean algorithm jigsaw method - help!

Recently I've been learning about how the Euclidean algorithm = jigsaw method (filling a rectangle with squares) = forming continued fractions. And today I'm wondering how a 3D version of the jigsaw ...
0
votes
0answers
20 views

How to solve $T(n)=T(n/3+5)+T(2n/3+7)+c$

How can I solve $T(n)$ in terms of big O notation? Please let me know. I've written a following code that might help. ...
0
votes
1answer
20 views

What would the Big oh be of (1/2)^n

Is it just (1/2)^n? The function itself gets closer and closer to 0 as x > infinity but I don't know what its classification would be in terms of big oh. O(1)?
0
votes
1answer
19 views

Converting $f_{2}$ to $O(f_{2})$ that isn't $f_{1}$

So the actual problem I'm trying to figure out is Find functions $f_{1}$ and $f_{2}$ such that both $f_{1}(n)$ and $f_{2}(n)$ are $O(g(n))$, but $f_{1}(n)$ is not $O(f_{2})$ I know that if I had ...
5
votes
2answers
63 views

Recurrence Relation from Old Exam

I see this challenging recurrence relation that has a solution of $T^2(n)=\theta (n^2)$. anyone could solve it for me? how get it? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 ...
0
votes
1answer
33 views

Proving $\sum\limits_{i=1}^n i^2$ is $O(n^3)$

Just starting my Data Structures class, and this is one of several questions for my HW in one question. (I.e. this is 1a, but there's b-f too). I have no clue where to even start, the book doesn't ...
0
votes
1answer
15 views

Show running time of algorithm on input of size n is $\Omega$ (f(n))

Basically I'm given this algorithm where I have an array A of integers which outputs an n-by-n array B where B[i,j] contains the sum of the array entries A and asked to give a bound of the form ...
0
votes
2answers
25 views

How can you tell if you a piece of code has running time of logn?

I'm new to Data Structures and Algorithms and I would like an example of code (preferably java or any pseudocode) that shows logn running time. I know what n and n^k running time looks like (simple ...
0
votes
1answer
29 views

Combinatorics counts outcomes, what mathematics lists outcomes?

Since I've been learning combinatorics the past few days I've constantly found myself wanting to implement the combinatorics I've learned in various ways(mostly by writing software that analizes each ...
1
vote
0answers
21 views

Number theory formula needed

Problem: $10$ numbers modulo $77$ are given. Denote them by $a_1, a_2, ... , a_{10}$. I want to find a surjective function $f(a_1, ... ,a_{10})$ with following condition: $f(a_1, ... ,a_{10}) \neq a_i ...
1
vote
0answers
28 views

Need help checking my recurrence for a simple algorithm

All I'm writing to get a second opinion on the algorithm shown in this link. I'm pretty sure its supposed to be $T(n)=2T(n/2)+n$ but I can't see where I'm supposed to get the +n from. So far I'm ...
0
votes
0answers
27 views

Count ways to paint the grid

Given a rectangular grid of dimension N x M. We need to paint the grid with black or white color such that there is no rectangle of size X x Y having same color in each cell. Find the number of ways ...
1
vote
1answer
74 views

A Turing machine algorithm which determines other algorithms

Let $X$ be a Turing machine algorithm, which run as following: For a Turing machine algorithm A, X(A)=0 if A(A)=0 X(A)$\neq$0 if A(A)$\neq$0 We can code X easily. However, what's the ...
0
votes
2answers
18 views

How fast can you split a set of numbers into 2 sets, where the difference of each sum is maximized

How fast can you perform this task? More specifically, if there is a set of 2n elements, how fast could you split those elements into two groups of n elements where the sum of each group is of ...
0
votes
2answers
37 views

Multiplication and addition, but in a weird way.

'calculate the product of x and y by accumulating the sum of x copies of y' I'm stumped, what is it this exercise actually wants me to do? Express $x$ * $y$ as something else? I'm allowed to use an ...
0
votes
1answer
33 views

Distribute n balls across m bags when bags are not empty to get the same sizes

Thinking about the best solution of the next problem. Suppose we have m bags where $n_1, n_2, ..., n_m$ balls are already laid. We need to distribute new n balls across these bags to get almost the ...
1
vote
1answer
34 views

Expanding a recurrence relation with a summation involved

Question: $(10)$ Solve the recurrence in asymptotically tight big Oh function; $$t(n)=n+\sum_{i=1}^kt(a_in),$$ for the two cases (a) where $\sum_{i=1}^k a_i < 1$, and (b) where ...
0
votes
0answers
25 views

Help with understand the growth order of functions

I am taking an Algorithms class and I understand everything that relates to the asymptotic growth and Order of growth for a given function (Theta, Omega, etc). However, I am having trouble in ...
4
votes
2answers
85 views

Algorithm to answer questions on dominated input

Consider a setting where we see inputs one-by-one, with each input being an $n$-tuple $(a_1,a_2,...,a_n)$, where each $a_i\in\{0,1\}$. For each new input we see, we have to answer two questions: 1) ...
1
vote
0answers
17 views

How to find all maximal chains and antichains in a finite bounded lattice

Is there a (possibly efficient) algorithm to find all maximal chains and antichains in a finite bounded lattice?
0
votes
0answers
24 views

Divide-and-Conquer algorithm for sorting ascending lists

Divide-and-conquer involves dividing the problems into as small sub-problems as possible and then recursively solving the sub-problems before combining the solutions to get an overall solution. The ...
0
votes
1answer
46 views

How to deal with summation with log bounds like: $\sum \limits_{i=1}^{\lg (n)}$ [closed]

I came across this summation in my algorithms textbook. I've googled everywhere and can't seem to find anything on how to deal with these types of bounds. (Apparently it equals 2n as n approaches ...
2
votes
0answers
60 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
0
votes
3answers
67 views

Prove that $1^{k} + 2^{k} + \cdots + n^{k}$ is $O (n^{k+1})$

I have the following to prove: $1^{k} + 2^{k} + \cdots + n^{k} \text{ is }O (n^{k+1})$ I have done the following: $$\frac {1^{k} + 2^{k} + \cdots + n^{k}}{n^k} \leq n$$ Am I on the right track? I ...
2
votes
4answers
61 views

Prove that $3^n$ is not $O(2^n)$.

I am working on some Big oh questions and I can't seem to get how disprove them. In this case we have: Prove that $3^n$ is not $O(2^n)$ I can see that its obvious just by looking at the two ...
0
votes
1answer
11 views

Help on understanding tax bracket computation

Warning: some codes Tax Bracket: 1 up to 5,070 ---- 10% ...
1
vote
1answer
50 views

Onion-peeling in O(n^2) time

I am working on the Onion-peeling problem, which is: given a number of points, return the amount of onion peels. For example, the one below has 5 onion peels. At a high level pseudo-code, it is ...
0
votes
0answers
41 views

counting the good numbers

We need to calculate Good Numbers in range from $A$ to $B$ (Both inclusive). A number $N$ is said to be a good Number if it satisfy following conditions : If we extract every $2$-digit number of $N$ ...
0
votes
0answers
18 views

Separate a list of spheres into several lists, each contained in a sphere with a radius no larger than specified.

I have a list of arbitrary spheres, what I want to end up with is that list separated into a number of groups, where spheres in each group all fit into thier specific larger sphere. The limitation is, ...
1
vote
1answer
31 views

How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same. Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
1answer
27 views

Multiply two polynomial in O(nlog n) time

In order to multiply two polynomial , we need O(n^2) complexity. Is it possible to perform the multiplication in O(nlog n) time??
3
votes
1answer
82 views

Computing convex hull of a bunch of circles

I am stuck on the following question ...
0
votes
2answers
63 views

Integrate $\int_{0}^{\pi} \frac{1}{a-b\cdot cos(x)}$ [closed]

Evaluate$$\int_{0}^{\pi} \frac{1}{a-b\cdot cos(x)}$$ Solution through either contour integral method or indefinite integral method please!
0
votes
1answer
17 views

Comparing algorithmic complexities

If an algorithm has a running time $ T(n) = O(n$ log $n)$, would it be possible to show that $T(n) = o(n^2)$?
1
vote
0answers
45 views

Finding a minimum stops along a route with a car that has unlimited tank

Suppose you want to go to a place that is D miles away, and you have a car that has unlimited fuel tank and has I unit of fuel initially. Along the route, there are N number of fuel stations, and the ...