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
37 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
28 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
22 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
41 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
39 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
607 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
59 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
28 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
11 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
66 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
115 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
36 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
18 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
58 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
52 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
26 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
37 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
20 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
37 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
46 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
53 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
29 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 ...
0
votes
0answers
23 views

Modifying U=mxn SVD Algorithm to U=mxm Algorithm

I have painstakingly ported this Python source "svd.py" to C++. I confirm it works for the example it comes with. While testing another example (this one, from Wikipedia), the assert statement trips ...
2
votes
1answer
26 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
2
votes
0answers
33 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
8
votes
1answer
85 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
2
votes
0answers
50 views

Minimise total cost and count ways [closed]

A country has a + b cities located in a row, which are uniformly placed. There are two large telecommunication operators in this country. The first operator will ...
0
votes
1answer
15 views

algorithm to see if some sign(s) of terms will sum to zero

I was trying to develop an algorithm so see if a given set of terms $a,b,c,d$ can sum to zero given any possible combination of signs $+/-$ on those terms. How does one compute how many distinct ...
0
votes
0answers
23 views

Algorithm of matching points between two point sets

I have two point sets $A=\{a_1,a_2,...,a_m\}$ and $B=\{b_1,b_2,...,b_n\}$ $(m\ge n)$, and want to find a injection map $\phi$ from $B$ to $A$ such that it minimizes $\sum{||b_i-\phi(b_i)||}$. There ...
4
votes
3answers
93 views

2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
0
votes
0answers
11 views

Perlin noise seems to be distributed like on a bell curve

I coded a perlin noise function, (gradient noise, not value noise). Weirdly, (or maybe it's normal?) my values seem to be distributed pretty much like on a bell curve. I guess I should fix my ...
1
vote
1answer
23 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
0
votes
0answers
7 views

Estimate time it takes the minimum mean cycle cancelling algorithm to converge

This particular algorithm solves the circulation problem, equivalent to the minimum-capacitated flow. My question rather than only from this particular algorithm, but for combinatorial solutions in ...
0
votes
1answer
22 views

Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
0
votes
2answers
25 views

Fastest way to find the top points in a rectangle

Given a rectangle X1,Y1 and X2,Y2 such that X1,Y1----------------- | | | | ----------------------X2, Y2 And given a ...
3
votes
2answers
39 views

Smallest value taken by a quadratic polynomial in two variables.

Let $p$ be a degree $2$ polynomial with integer coefficients, say $$p(x,y) = Ax^2 + By^2 + Cxy + Dx + Ey + F.$$ I would like to find an algorithm which solves the following: Problem 1: Given ...
1
vote
1answer
35 views

How to generate a point cloud with known symmetry?

So I would like to know if there are any published algorithms to generate point clouds with known symmetry groups, such as $D_{3h}$ or $O_h$ and stuff like that. I know lots and lots of point clouds ...