Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
-1
votes
1answer
14 views
Need help with an algorithmic function
Consider the following claim: for any positive constant c, f(cn) ∈ Θ(f(n))? Either
show the claim is true or give a counterexample.
-1
votes
1answer
15 views
Need help ordering a list of functions
List the functions below from lowest order to highest order. If any two or more are of
the same order, indicate which.
$n$, $n^3$, $2^n$, $\ln n$, $n^2$, $\ln^2 n$, $\sqrt n$, $2^{n−1}$, $\ln n$, ...
0
votes
1answer
14 views
Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$, where $0 < a < b$.
Let $a$ and $b$ be real numbers such that $0 < a < b$. Show that $n^a$ is in $O(n^b)$ but $n^b$ is not in $O(n^a)$.
0
votes
1answer
75 views
Algorithms - Induction (packing cups into boxes)
Hey I really need some assistance on this question. I honestly just have no idea where to go with this one.
Question: We have $n\cdot k$ cups. Each of these cups has one of the $k$ different colors. ...
0
votes
0answers
38 views
Door game between alice and bob
Alice and Bob are taking a walk in the Land Of Doors which is a magical place having a series of N adjacent doors that are either open or close.
After a while they get bored and decide to do ...
1
vote
0answers
46 views
Count ways to reach Nth row
Given a N*M grid I need to reach last row with following operations :
...
0
votes
1answer
25 views
Sequence of polynomials with rational coefficients
Clearly, the set of all univariate polynomials with rational coefficients is countable. That is, we can enumerate the members, say, as $x_1,x_2, \dots ,x_n, \dots $
How can we find $x_n$ for a given ...
0
votes
0answers
13 views
{0,1}-solutions for integer equations via lattice base reduction?
I would like to find $\{0,1\}$-solutions of a system of equations of the form $$\left\{\begin{array}{c}\sum_{i\in I_1}x_i=1\\\sum_{i\in I_2}x_i=1\\\vdots\\\sum_{i\in I_k}x_i=1\end{array}\right.$$
...
1
vote
0answers
28 views
Count balls to put in triangle
Given balls of radius $R$ we need to find how many balls can be put into a triangular container with sides $a,b$ and $c$.
Example : Let $R=1$ and $a=3,b=4$ and $c=5$ then answer is $1$, as only one ...
0
votes
1answer
18 views
Division Algorithm With Negative and Absolute Value
(a) Prove that $d \, |\, a$ implies that $d \,| (−a)$.
(b) Prove that $d\, |\, a$ if and only if $d \,| (−a)$.
(c) Prove that $d \,|\, a$ if and only if $d\, \Big|\, |a|$.
I can see why these ...
0
votes
0answers
12 views
Pina's algorithm
I have difficulty to understand the Pina's algorithm for enumerating all cycle bases of the undirected graphs.
-Could you please explain to me using a detailed example ?
0
votes
2answers
55 views
Making 24 with given number N
Initially we have a sequence of n integers: 1, 2, ..., n. In a single step, we can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, ...
0
votes
0answers
27 views
Divide N elements in 3 sets
Given N elements in an array where ith element has A[i] value.Now we need to divide these N elements in 3 sets in such a way that difference between sum of all elements in set1 and set3 is minimised.
...
3
votes
2answers
118 views
Sums $\sum_{n=1}^{N}\sqrt{4n+1}$
I need to find sum of the first N terms of the sequence whose nth term is as follow :
T(n)= $\sqrt{4*n+1}$
So the sequence is : $\sqrt{5}$,$\sqrt{9}$,$\sqrt{13}$,$\sqrt{17}$,$\sqrt{21}$......
...
0
votes
2answers
37 views
Find expected value of F(N)
If we are given that a variable X is defined as
X=rand() % N
Here rand() returns an integer between 0 and $10^{100}$ (inclusive) uniformly at random.
Now we ...
1
vote
1answer
54 views
Battle Ship Winning Algorithm - Optimal Strategy
I have an $8 \times 8$ grid. I have three ships that are $4$ long, $3$ long, and $2$ long. Is there an algorithm that can ensure a win every time? Oh! Most importantly, you must know the number of ...
4
votes
1answer
20 views
Question about Growth Rates
I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
0
votes
0answers
18 views
Most efficient algorithm to determine whether a given finite sequence is mutually distinct
Let $a_1, \dots a_n$ be a finite sequence of elements of a set $X$.
I'm wondering what is the most efficient algorithm to determine
whether the number of elements of the set $\{a_1,\dots, a_n\}$ is ...
1
vote
0answers
36 views
Count the strings with n0 K zeroes together
Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1.
Now , the problem is we need to count the number of ways to fill these ...
0
votes
1answer
33 views
searching a number in 2D matrix
I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise.
Finally i came across, this link ...
0
votes
2answers
23 views
Greedy Algorithm, Fewest overlaps
Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
2
votes
2answers
25 views
algorithm to find the order of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$ where $n$ is not prime.
algorithm to find the order of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$ where $n$ is not prime.
Now I know a naive algorithm where you just keep multiplying $a$ by itself until you find it equals $1 \mod ...
2
votes
0answers
37 views
Does a generalization of the Teichmuller-character for non-prime arguments exist?
Rereading an older article on Fermat-quotients in which I'd applied some p-adic-rationale I find now, that my method for the representation of bases $b$ which allow high fermat-quotients ...
2
votes
0answers
33 views
Algorithm to lay out orthogonal connector lines without overlap
I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
0
votes
1answer
12 views
Linearly independent rows in a binay matrix
I need the algorithm to finding only the linearly independent rows in a binary matrix using XOR function.
Example 1:
The result:
Example 2:
The result:
R4 is not included because:
0
votes
0answers
24 views
Identify regions in 3D space and assign a point to a region [on hold]
Sorry if the question is duplicated, I don't even know what to search for solve this problem.
I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane ...
0
votes
2answers
37 views
Is my method of computing the running time correct?
Okay, so this is the code for which I need to compute the running time:
...
2
votes
0answers
46 views
Algorithm to find the “optimal” path in a given graph
Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
2
votes
0answers
26 views
Find spacing of fence posts with minimal distance to fence posts of two other fences
Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$.
A fence is described by three values ...
0
votes
1answer
13 views
Max no. of piece in k cut
Suppose I have large piece of rectangular sheet. Cutting is allowed only vertically and horizontally.
My approach is
if no. of cut is even then max. no of piece is (n/2)*(n/2)
if no of cut is odd ...
0
votes
0answers
36 views
Find Good string in mimimum Moves
A string is called to be good if and only if "All the characters in String are repeated the same number of times"
Now, Given a string of length n, what is the minimum number of changes we have to ...
1
vote
1answer
31 views
How to get the ratio from a function of N?
The exercise gave us a chart which showed the running time as a $N$ increases:
\begin{array}{c|c}
N & \text{seconds}\\\hline
256 & 0.000\\
512 & 0.000\\
1024 ...
5
votes
0answers
60 views
Traveling salesman problem: can a terrible strategy beat a good one?
Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
3
votes
0answers
24 views
Looking for an algo to “sorta” diagonalize a similarity matrix.
I've got a big fat similarity matrix. The rows and columns represent people, and the values represent some positive measure of their closeness (0 meaning no connection at all). The n-th row and n-th ...
6
votes
1answer
63 views
Traveling salesman problem: a worst case scenario
For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
-1
votes
1answer
89 views
0
votes
1answer
35 views
Big-Oh of exponent of exponent
How does one whether an exponent of an exponent is the big-Oh of the other?
For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking ...
0
votes
0answers
7 views
sufficient and necessary condition for specific dfs property
Let $G$ be a directed graph. I want to find a sufficient and necessary condition for the next property regarding dfs run-
For each dfs run on $G$ the vertex with the latest finish time is a vertex ...
1
vote
0answers
37 views
Bride Groom Problem
Let's consider a system of $n$ men and women. Each woman is paired with one man (there are only pairings between a woman and a man in this system). There are $n!$ possible distinct pairings. I refer ...
0
votes
0answers
21 views
Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$
I want to algorithmically solve the (large integer) modular root equation
$$x^n \equiv a \pmod {p^k},$$
assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
1answer
15 views
In the loop average computation
I want to compute the average of a set of number, which is constantly increasing. I guess it's simple, but I'm struggling here:
Let's say:
1st iteration:
m(i)=a+b/2
2nd iteration:
m(i+1)=a+b+c/3
...
0
votes
0answers
26 views
Sum of products of numbers in a list
For N numbers in a list, is there a formula to get the sum of products of the numbers in the list? Example:
{3, 3, 2} = (3 * 3) + (3 * 2) + (3 * 2)
Right now I'm ...
1
vote
1answer
40 views
“Job-scheduling” problem that minimizes the number of machines
In a graph, there are points that need to be visited. For each of these points, there
is a certain time interval given by its start and ...
0
votes
0answers
31 views
Find two element $x_k$ and $x_l$
Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...
0
votes
0answers
22 views
To minimize surface area of integer cuboid of the known volume
There is a cuboid (a * b * c), (a, b, c ∈ N).
S (Surface area of a cuboid) = 2 * (ab + bc + ca).
V (Volume of a cuboid) = a * b * c = n.
I need to minimize S, provided that I specified the volume ...
0
votes
0answers
22 views
Adjust previous optimal solution to new assignment problem
Suppose I have an assignment problem with $n$ workers and $n$ jobs and its optimal solution.
Now another worker and another job comes along and we are given all new costs. Is there an efficient ...
1
vote
0answers
9 views
Finding groups with minimum mean deviation
Is there any algorithm that groups consecutive elements in an array that gives the minimum mean deviation.
For example we are given an array a=[1,2,3,4,8,2,3,5]
There can be many "consecutive" ...
0
votes
0answers
52 views
Real roots of a quintic polynomial with constraints
This is a question on the edge of math and programming.
I pondered about the best way to state the problem: should I provide context, or get straight to the point of the question? Given various ...
0
votes
1answer
27 views
Minimal disjoint chains covering graph vertex set
I'm looking for references on the following problem:
Given a graph $G=(V,E)$,
what is the minimum number of simple, disjoint paths that span all the vertices in $V$?
i.e., let $P$ be the answer to ...
1
vote
0answers
30 views
Efficient algorithm to find a minimum spanning set for a given vector.
A few days ago a colleague proposed the following problem.
Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
