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
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 ...
0
votes
1answer
42 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
22 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
45 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 ...
0
votes
1answer
37 views

How many n-digit numbers can be formed using x single digit numbers? [closed]

For instance, I have to form 4 digit numbers with the any 3 digits, say 1, 2 and 3. There are several possible numbers that can be formed by arranging these digits in various orders, but I am unable ...
2
votes
1answer
47 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
20 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
24 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
41 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
32 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$? ...
0
votes
1answer
20 views

Turing machine algorithm and Natural number

Let T be a deterministic Turing machine and let A be a set of all algorithms which is running on T. I know that there is an algorithm F which can transform an Algorithm $X$ into a Natural number ...
0
votes
1answer
19 views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
-2
votes
0answers
35 views

Minimise the expected value [closed]

Given an array A that contains n integers, namely $A[1], A[2], ..., A[n]$. A single action consists of performing one of two following operations: ...
1
vote
0answers
27 views

Definition of decidable sentence

Let $P(n)$ is a sentence which mentions natural number $n \in \mathbb{n}$ For example, "$n > 5$" or "There is no $n$ such that $3^n+4^n=5^n$ " can be $P(n)$. I want to define a set A as a set ...
0
votes
0answers
6 views

Pseudo-algorithm for most equals group size

Let's say I don't know how many (let's says person) will be present. I know I want to divise all those persons in group of 15. What king of algorithm could I use to create groups of person (the most ...
-1
votes
1answer
244 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
2
votes
1answer
31 views

Algorithm to determine if integer matrix is similar to symmetric integer matrix with nonnegative entries

Let $A\in M_n(\mathbb{C})$ be a matrix with integer entries (treated as a matrix over the complex numbers). Is there an efficient way to check if $A$ is similar to a symmetric matrix with nonnegative ...
0
votes
1answer
39 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
3
votes
2answers
32 views

How to check if a sequence is random?

When I was thinking about various types of pseudo-randomness, the following question struck me: Suppose that a sequence $a_n \in \{0,1\}$ is given. Is there a way to check if it is genuinely ...
0
votes
1answer
46 views

Count ways to make K joules of energy [closed]

A scientist of NASA has discovered a secret formula, according to which if a bottle of chemical A occurs to the immediate left of a bottle of chemical B in a straight line arrangement, they produce 1 ...
0
votes
0answers
15 views

random relax based algorithm complexity

consider the follow relax based algorithm than find all the shortest paths from s: input: directed graph G = (V , E) , weight function W:E->R(real numbers), source vertex (s in V). G don't ...
4
votes
0answers
105 views

Will this algorithm stop before time?

For every $n \in \mathbb N$, let's define $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& ...
0
votes
0answers
21 views

Iterative algorithm for finding approximation functions for N-dimensional space

Say, I have billions of integral-valued vectors of the form $(0, 1, 3, 0, 0, 0, 3)$. My goal is to efficiently compute approximate distribution of values of each component of these vectors for each ...
0
votes
1answer
13 views

Linear-time algorithm for deciding triconnectivity?

The german site of wikipedia (Look at wikipedia k-zusammenhang) states that there are linear-time algorithms to decide whether a given undirected graph is triconnected (Deleting any two vertices ...
0
votes
1answer
29 views

Quicksort probabilistic analysis

Let us say that we randomly pick up a pivot element and partition the array around it. What is the probability that we always pick the pivots in subsequent recursive calls such that it partitions the ...
2
votes
0answers
28 views

Fast algorithm/formula for serial range of modulo of co-prime numbers [migrated]

In my project, one part of problem is there. But to simplify, here the problem is being formulated. There are two positive co-prime integers: $a$ and $b$, where $a < b$. Multiples of $a$ from 1 ...
0
votes
1answer
21 views

Growth Rate Algorithms

Which Function is growing faster as I take the Limit as $x$ approaches infinity? In this case I think $g(x)$ is growing faster $f(x) = (\ln(2x))^3$ $g(x) = (\ln(3x))^2$ I have to use L'Hospitals ...
0
votes
0answers
11 views

Smallest survey size algorithm

I was inspired to think of this problem when I saw a commercial saying "97.1% of audiences loved this movie!". After fiddling around with some numbers, I realised that at least 34 people must have ...
1
vote
0answers
11 views

Algorithm conjecture

This is an algorithm analysis question for computer science. Let f(n) be positive functions. (Dis)prove the following conjecture? $$f(n)+o(f(n))\in\Theta(f(n))$$ o above is the Little O, defined as ...
0
votes
1answer
18 views

Logarithm Base Question

Suppose you have a integer n. Log2(n) is supposed to be ~ the number of times you have to divide n by 2 until you reach one. Now let's say you want to know ~ the number of times you have multiply n by ...
0
votes
0answers
36 views

Calculate digits of pi without needing to reuse them

I am looking for some algorithms that can calculate digits of pi. without needing to reuse previous digits. I would like to find the most simple and fast algorithms possible. Thanks!
-1
votes
0answers
39 views

Find ways to make sum N from K type of coins

Given K type of coins with each denominations between 1 to 15. Also K <=15 and now we need to make sum N with help of these coins provided each of given denomination coins are infinite in number. ...
1
vote
2answers
36 views

When is a point in the plane inside a simple closed path?

Suppose I have a simple closed curve $\gamma(t)$ in the plane. In general, how do I tell if some point $p$ is inside or outside this curve? For example say $\gamma(t) = (2 \cos(t), \sin(t) + ...
0
votes
1answer
14 views

Proof of the optimality

I have the following problem. I have constructed an algorithm for evaluating some expression, e.g., $L := a_1 \& a_2 \& \ldots \& a_n$ Now the overall costs for some plan P, evaluating L ...
2
votes
2answers
43 views

Rewriting nested summations that sometimes sum to zero

Is there a way of re-writing the following formula in terms of just $n$: $$r = \sum_{i=1}^{n}\sum_{j=i+1}^n\sum_{k=i+j-1}^n 1 $$ From what I understand, when $i+j-1 \gt n$ the inner-most sum is ...
-17
votes
1answer
961 views

Taking the square root of a number using only one operation [on hold]

The most ancient and best-known algorithm 'Babylonian' to take the square root of a number requires 4 operations (like Newton's) and 3 different operations $$x^2 = \alpha \rightarrow x_{n + 1} = ...
0
votes
0answers
26 views

Native algorithm for lottery

Consider a simple lottery game that you are required to pick 6 numbers out of 50 numbers (1 to 50), and you have the history of the most recent n games' result, by ...
0
votes
0answers
15 views

Degree characterization

I have been asked in a programming contest if it is possible to construct a graph just with the degree numbers. For example, given $1,2$ the answer would be no by the handshake lemma, but that's a ...
0
votes
2answers
28 views

comparing two algorithms and their respective Big O notations

So we learned in classes that some algorithms perform better at certain times. On the homework assignment, We are asked to compare algorithm 1 which takes 4n4 days to run with one that takes 3n ...
1
vote
2answers
28 views

How can I find The Big Oh bounds for a summation with multiple variables?

I have this as a homework problem so I won't post the same thing. I'll just post what I need to know to move forward. $$ \sum_{i=0}^n 10^i i^2 $$ I'd just like to know how to split this ...
1
vote
0answers
33 views

Divisible 4 for every different number?

My formula is for ABC 3 digits number; 100A + x*B + y*C. What should coefficient of B and C be for everytime different result for different number? (Result number ) mod 4 has to be zero. For ...
1
vote
0answers
20 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
0
votes
0answers
47 views

How can we find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits?

If $n$ and $m$ extremely large (1000 digits) and $1 <\frac{2^m}{e^n} < e$, how can we create an effective algorithm to find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits (10 digits ...
3
votes
2answers
96 views

Determining whether a number is a 'factorial number'

Let's define $\mathbb{F}=\{x \in \mathbb{Z^+}: x=n!, n=\mathbb{N}\}$ to be the set of all 'factorial numbers' (i.e. all positive integers which are the factorial of some natural number). Is there ...
1
vote
2answers
19 views

Add integers to a set number of lists, so that the sum of each completed list is as closely matching to the other lists as possible?

I am trying to figure out how to solve this problem in computer science. I won't go into the programming side of things, but basically what I need is this: I have a list of integers ranging from ...
4
votes
2answers
66 views

The determination of the Galois group of a polynomial

The GAP package has a function $\mathtt {GaloisType}$ that takes a polynomial as an argument and returns a number, the index of the transitive group of order the degree of the polynomial. I read ...
0
votes
0answers
27 views

Simple enumeration of discrete simplex

I'm looking for a computationally nice enumeration of the $n$-dimensional discrete simplex $$\Delta^n_N = \{ x \in Z^{n} | 0 \leq x_i \leq N \, \text{and} \, x_1 + \cdots x_n = N \}$$ I have an easy ...
1
vote
1answer
50 views

Complexity of computing $N!$

Question: Complexity of computing $N!$, considering that each multiplication cost about $O(\log^2{n})$. Attempt: There's $n-1$ multiplication. Each multiplication leads to a bigger number, thus $n-1$ ...