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
11 views

How do you typically prove recurrence relations?

The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to ...
0
votes
1answer
13 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
0
votes
0answers
18 views

# of ways to sort. Quick Sort Problem.

This is a question about the quick sort algorithm and the # of ways I can place the books on shelves. I have to place a book on n number of shelves with m number of books; m >= n >= 1. But I have to ...
0
votes
0answers
17 views

Help Representing Python Algorithm Mathematically

For a project I am doing (using rhythm comparisons as an alternative to password authentication), I created an algorithm called "MalKonform", which compares keystroke times between two instances. ...
0
votes
0answers
11 views

Upper and Lower Bound Function for Recurrence Function

Suppose the first number in a sequence is 2, the second number is 3, and every following number is two times the (i-1)th number plus three times the (i-2)th number plus 2. (e.g. the first five numbers ...
1
vote
1answer
20 views

Algorithm to find subset of integers with highest sum under specific conditions

I have a set of N>1 integers all greater than 1, not necessarily all different. I need the most effective algorithm to find a subset of these numbers whose sum is the greatest. Unfortunately, there ...
2
votes
3answers
41 views

How to check a polygon in $\mathbb{R}^2$ for convexity.

Given $n$ points in $\mathbb{R}^2$, $\{p_1,p_2,\ldots,p_n\}$, how do we test if the (interior of the) polygon formed by drawing the line segments $[{p_{i-1},p_i}]$ for $1\le i \le n$ and also ...
1
vote
2answers
15 views

Alternative hash table analysis

Let us say that we have to hash $n$ elements to $m$ hash slots. Now what could be the average length of a chain. We can assume that prob. that 2 elements will map to a particular location will be ...
1
vote
2answers
35 views

What algorithm solves this problem? Non-linear measuring tape

A measuring tape is marked at 0, 5, 15 and 40. The distances between each mark are marked on top. At what distances should I mark 1 through 4, as well as 6-14 and 16-39? My math knowledge does not ...
-1
votes
1answer
24 views

Need help with an algorithmic function [on hold]

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
2answers
33 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
20 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
122 views

Algorithms - Induction (packing cups into boxes)

I 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. Assume $k$ ...
0
votes
0answers
47 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
48 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
11 views

Is my proof correct : $\sum\limits_{i=0}^b a_in^i = \Theta(n^b)$

I want to prove : $$\sum\limits_{i=0}^b a_in^i= \Theta(n^b), a_o,a_1,...,a_b\in R, a_b \ne 0$$ So first, I prove that $\sum\limits_{i=0}^b a_in^i= O(n^b)$. First, Let's find $c$ $$ 0\le a_o + a_1n + ...
0
votes
0answers
15 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
30 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
19 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
13 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
28 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
123 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
21 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
19 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
34 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
39 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 ...
3
votes
1answer
37 views

Spacing of fence posts with minimal distance to other fence posts

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
64 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
92 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
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} ...