Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

2
votes
1answer
80 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
35 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
0answers
28 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
17 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
61 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
32 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
133 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
41 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
57 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 ...
5
votes
1answer
27 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
40 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
32 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
26 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
38 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 ...
3
votes
1answer
89 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
15 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
2answers
40 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
49 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
47 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
43 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
32 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
84 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
75 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, ...
0
votes
1answer
42 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
43 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
22 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
28 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
45 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
32 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
29 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
25 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
12 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
63 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
28 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
43 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 ...
0
votes
1answer
53 views

How to calculate running time of code?

I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one: ...
0
votes
2answers
26 views

Proving Algorithms

I'm trying to get down how to prove that something is $O(\cdots)$ or $\Theta(\cdots)$ but no matter what I look at, I don't get the reasoning as to how I can come to an answer. So here's a couple of ...
0
votes
1answer
51 views

How to prove the $\Theta$ notation?

I know that to prove that f(n) = $\Theta$(g(n)) we have to find c1, c2 > 0 and n0 such that $$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$$ I'm quite new with the proofs in general. Let assume that we ...
2
votes
1answer
49 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
1
vote
0answers
14 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
0
votes
0answers
24 views

Factoring a quadratic residue modulo

Do apologize, wasn't sure where to ask this, but I was wondering how an algorithm would factor and show the square roots in a quadratic residue modolo when you're given N and a, which is a quad. ...
2
votes
1answer
30 views

find all continuous path segments in an undirected graph

I have an undirected graph, like the following: . C . / \ . B F . / / \ . A D E The edges are: ...
1
vote
1answer
51 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
0
votes
1answer
38 views

Calculating running time for C code

The problem is this: How many array accesses does the following code fragment make as a function of $N$? ...