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
49 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
99 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
21 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
67 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
29 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
42 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 ...
0
votes
2answers
53 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 ...
-2
votes
2answers
138 views

How to find sum of 4th power of n numbers mod m [closed]

How can i calculate $1^{4} + 2^{4} + 3^{4} + 4^{4} .....+n^{4} \pmod m$ where $1 \le m \le 10^5$ and $1\le n \le 10^{20}$. I can't use the formula here because it will Overflow the limit of long long ...
0
votes
0answers
20 views

Find the running time of the following program fragment

The exercise in my book is asking me to calculate the running time of the following for loop: for (int i = 0; i < n; ++i) ++k; This instantly reminds me ...
2
votes
1answer
40 views

Quadratic Equation Algorithm

I need help for developing an algorithm. I'm drawing a given amount of line segments and I want them to decrese in length the more they get close to amount/2 and then to grow again until they reach ...
0
votes
1answer
15 views

Labeling of cells from 2D plane division by lines

My question is about a labeling scheme for the cells (convex polygon regions) resulting from the division of a 2D plane by a set of lines. I am seeking answer for the Euclidean (flat) 2D plane, ...
0
votes
0answers
38 views

Statement about limits from Algorithm Desgin

There is a statement in Algorithm Design by Kleinberg and Tardos: "It follows from the definition of a limit that there is some n0 beyond which the ratio is always between 1/2 c and 2c" I'm a Computer ...
0
votes
1answer
54 views

sudoku number of solutions with no recusion

am asking you if you know if it's possible that sudoku, which is able to be solved with no recusion (with intersection of sets only) has more than one solution ? Thank you for answering me!
0
votes
0answers
38 views

Question about Horners rule algorithm

I am studying Horner's rule I have a question about an algorithm I found here . I understand that the rule allows you to break down polynomials in to monomials to solve them more easily, so that for ...
1
vote
0answers
29 views

How to use a computer to give guesses for a counting formula, given the first few terms?

Are there any systematic approaches developed on how to derive some "succinct" combinatorial formulas e.g. using factorials/hypergeometric terms and polynomials with integer coefficients that fit the ...
1
vote
0answers
24 views

operator vs operation vs function vs procedure vs algorithm

I have a vague understanding of what operator, operation, function, procedure, algorithm mean in general. I am heavily biased towards computer science. Do you agree with them? What are the generally ...
0
votes
1answer
45 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
0
votes
0answers
15 views

AVL, keys where rotations are not required

Suppose the keys {1,2,3.....,n} are inserted into n empty AVL tree in sequence 1,2,3.....,n. Find the key values(1,2...n these are the keys) where rotation(rotations to balance the tree structure) is ...
0
votes
1answer
41 views

Verify that T is a binary tree

Given a tree, how efficiently can you verify whether T is a binary search tree or not? I really do not know how to proceed with this. I think an algorithm is required, but I cannot figure out any... ...
-1
votes
0answers
11 views

How to calculate Kappa for segmented images using two judges images

I have two reference images representing the two judges, and i have my segmented image. Now i want to calculate the Kappa of my segmented image. As i understood from this paper that i should have the ...
0
votes
0answers
613 views

Make beautiful Arithmetic progression [closed]

Moderator Note: This is a current contest question on codechef.com. Given an array that consists of $n$ integers, we have to change at most $k$ elements so that the resulting array will be a most ...
0
votes
0answers
6 views

Is f(n) = O(g(n)), Ө(g(n)), or (g(n))?

So I have a homework assignment, and I have no clue how to work out its problems. Here is one example: n - 100 vs. n - 200 If the first is f(n), and the second is g(n), is f(n) = O(g(n)), Ө(g(n)), ...
2
votes
1answer
33 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
0
votes
1answer
29 views

Selecting a random orthogonal polygon

For a certain demo application, I want to create at random a rectilinear polygon with a given number of corners. Selecting random $x$ and $y$ coordinates of each corner is not a good method, since ...
2
votes
1answer
21 views

An inequality and random number and algorithm problem

I've been run into a problem which is absolutely not as simple as is looking, I just don't know how to describe it.I think it is a math problem eventually? Suppose a target number A and a mistake C ...
0
votes
1answer
61 views

The number of ways people standing in a line can be holding hands

I'm writing a program to analyze the maximum unique sequences of data in a string, given certain sets of two can be interpreted in two ways. There's a bit of math that I can't figure out, I've ...
3
votes
0answers
32 views

The Basic Example and Output of Algorithms [closed]

if exg(x,y) swap the x,y, and array A contains integer numbers, the following algorithm how modify the $A[1]$ and what is the operation of the following algorithm? i confused to trace this code. any ...
2
votes
1answer
30 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
0
votes
0answers
14 views

Mex and Grundy Numbers explanation

I've been reading this small tutorial on Nimbers and game theory. Could someone explain why the mex rule governs the nimber of a game position? See: http://en.wikipedia.org/wiki/Mex_(mathematics) ...
2
votes
0answers
85 views

Computing generators of the positive component of a graded ring

Let $R$ be a sub-algebra of $\mathbb{Q}[X_1^{\pm 1}, \dots, X_n^{\pm 1}]$ given by finitely many generators, and let $\lambda$ be a linear form $\lambda : \mathbb{Z}^n \to \mathbb{Z}$. This defines a ...
4
votes
0answers
41 views

One Simple Code and Problem on Running [closed]

My Stackexchange friends, would you please show the following code how manipulate the n-elements array A?
3
votes
0answers
51 views

Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
2
votes
2answers
116 views

How to find the optimal mapping between two sets?

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
2
votes
0answers
38 views

Add two a,b bits number Algorithm

Suppose we want add two numbers that has a and b bits. we do such operation in O(max{a,b}). we want to add n, 1 bit numbers (0 or 1). what is the best and worst case of this algorithm? i ran into ...
1
vote
1answer
19 views

Creating a scoring algorithm for voting app

I have just created what I thought to be a good scoring algorithm until I looked at some demo results. It now looks pretty floored though I have a table with a number of images I have another table ...
0
votes
0answers
62 views

Proof of Majority Value Algorithm for inductive step when c = 0

Call a majority value for the list L if > 50% of the elements of l have the value v. Prove that if L has a majority value, then the following algorithm will output it. (If L does not have a majority ...
4
votes
0answers
57 views

local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
0
votes
1answer
27 views

Tarjan's algorithm to determine wheter a directed graph has a cycle

I want to know if a directed graph has a cycle; something like 1->2->3->2 ... 1->2->3->4->3... 1->1->1->1... So, I'm considering ...
1
vote
1answer
38 views

Question about efficiency of an algorithm (Big-O)

The efficiency of the algorithm dolt can be expressed as O(n)=n^3.Calculate the efficiency of the following program segment exactly and by using the big-O notation. ...
0
votes
0answers
21 views

Inclusion-wise minimal feedback arc set

How is the term inclusion-wise defined? More precisely, I am trying to get a hold of what an inclusion-wise minimal feedback arc set is. Let $G = (V,E)$ be a (directed) graph. A feedback arc set $F ...
2
votes
1answer
38 views

Numerical evaluation of Hurwitz zeta function

Is there a way to evaluate numerically the Hurwitz zeta function $$\zeta(s,a) = \sum_{n=0}^\infty \frac{1}{(n+a)^{s}}$$ that is more efficient (i.e., quick and precise) than simply explicitly adding ...
1
vote
0answers
29 views

How to find the center of of rotational symmetry in a Penrose tiling?

The center of Helsinki sports a gorgeous Penrose tiled pavement: Could anybody give me an algorithm that will permit me to find its 'center' - that is, the point around which the five-fold ...
1
vote
0answers
26 views

Details of the Goldberg-Radzik algorithm for computing shortest paths

I'm trying to implement the Goldberg-Radzik algorithm, which is described in the 1993 paper "A heuristic improvement of the Bellman-Ford algorithm" by Andrew Goldberg and Tomasz Radzik (link: ...
4
votes
1answer
47 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
2
votes
1answer
112 views

Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...
2
votes
1answer
57 views

Count ways to make total coin value [closed]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
2
votes
1answer
55 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
1
vote
0answers
30 views

How to Prove an Algorithm is $O(n \log n)$ Using Substitution Method and a Change of Variable?

Consider the following: Show that $T(n) = 2T(\left \lfloor n/2 \right \rfloor + 17) + n$ is $O(n\log n)$. Here is what I have come up with: Restrict the domain of $n$ to $n \geq 1$ and define ...