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
4 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
10 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
16 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. ...
1
vote
0answers
6 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: ...
0
votes
0answers
16 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
21 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
0answers
13 views

Recursive Language and its consistency

For a formal language $L(n)$ which mentions variable $n \in \mathbb{N}$, let define symbol blacksquare $\blacksquare$ : $\blacksquare L(n) \leftrightarrow$ $L(n$) is the recursive language. There ...
0
votes
1answer
17 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
17 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
31 views

Minimise the expected value [on hold]

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
24 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
5 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 ...
0
votes
0answers
213 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 ...
1
vote
0answers
16 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
37 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
31 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 [on hold]

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
13 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
87 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
14 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
25 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
20 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
10 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
35 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
34 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
35 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
41 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 ...
-3
votes
1answer
402 views
+50

Is it possible to take the square root of a number using only one operation?

The most ancient and also the best known algorithm 'Babylonian' to take the square root of a number requires 3 operations and Newton's 4 (3 different operations) $$ x_{n + 1} = \frac{1}{2} \left( x_n ...
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
14 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
24 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
32 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
19 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
45 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 ...
-2
votes
0answers
44 views

Maximize the parts in which a large number can be decomposed in a limited time

Moderator's note: this question comes from the September CodeChef challenge which ends on Sep 15, 2014. The question will be locked until then. Problem: We have an large number n of long. ...
3
votes
2answers
92 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
18 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
61 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
26 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$ ...
0
votes
0answers
14 views

Algorithms for Optimizing a Solution Set

Say that we have a function $f$ which relates the entries in the tuple $(x_1, x_2, \cdots , x_n)$ with $g(x_1, x_2, \cdots, x_n)$ constant for some function $g$. We are also aware that in the optimal ...
0
votes
0answers
38 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
-2
votes
0answers
61 views

Find Next good string [closed]

Given string s is considered good if each its character is one of the first p letters of the English alphabet and s doesn't contain any palindrome contiguous substring of length 2 or more. Now we ...
0
votes
2answers
51 views

An algorithm to obtain square of any number.

I have discovered a new way to obtain square of any number. I think its a new algorithm to find square of a number than just multiplying it with itself; if its not new then let me know. Algorithm is ...