Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
1answer
31 views

Proof approach: A 7x7 matrix with 15 ones can allow at least three marriages

This is quite difficult to prove imho with regards to Hall's Marriage Algorithm I can visualize a number of scenarios that work (i.e. put ones from the first entry to the fifteenth, or across ...
3
votes
1answer
45 views

Counting the number of integers $i$ such that $\sigma(i)$ is even.

Define $\sigma(i)$ to be the sum of all the divisors of $i$. For example, $σ(24) = 1+2+3+4+6+8+12+24 = 60$. Given an integer $n$, how can we count the number of integers $i$, less than or equal to ...
0
votes
0answers
48 views

The problem of making change for $n$ using the fewest number of coins

Consider the problem of making change for $n$ cents using the fewest number of coins. Assume that each coin’s value is an integer. Describe a greedy algorithm to make change consisting of quarters ...
-2
votes
1answer
75 views

Application of the Knapsack Algorithm

I want to apply the Knapsack algorithm at the following: n = 4 (# of elements) W = 5 (max weight) Elements (weight, benefit): (2,3), (3,4), (4,5), (5,6) The ...
1
vote
0answers
35 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
-1
votes
1answer
41 views

Knapsack Problem [closed]

There are two versions of the Knapsack problem, the integer and the fractional one. Could you describe them to me?? Which are the differences?? With what type of programming do we solve them?? ...
2
votes
1answer
35 views

How to remove fields from sudoku puzzle in such way to assure there's still only 1 solution?

I'm trying to create a Sudoku puzzle (programatically, if that matters). Here's how I do it. STEP 1: Creating an initial set, with unique solution: 123456789 456789123 789123456 ...etc... STEP 2: ...
0
votes
1answer
47 views

Algorithm to distribute numbers so that average of sets is closest to total average

Given a collection of N non-unique decimal numbers d1, d2, d3 ... dN whose average is μT. Assume we distribute d1, d2, d3 ... dN across K sets with sizes s1, s2 ... sK and therefore: $$\sum_{i=1}^K ...
0
votes
1answer
11 views

Trigonometry to radially spread points around a center

I'm having a basic Math problem. I have number of point collections, each with a different amount of points. Let's say one collection has five points and I want them to spread radially around a ...
0
votes
0answers
20 views

Minimization according to a function

I am working on a simulation project on Matlab/Simulink and I would like to minimize the following function : $min_f \int_{t=0}^{t_1} m(A(t) + \int_{y=0}^{t} B(y) f(y) dy) dt $ With $m : \Bbb{R}^6 ...
0
votes
0answers
19 views

Minimax in the context of Knuth's algorithm for mastermind

I have several questions about using minimax to find a next best guess for knuth's 5 guess algorithm for mastermind: For each possible guess, that is, any unused code of the 1296 not just those in ...
0
votes
1answer
27 views

3 rotation values to work out rotation in degrees

I am currently working with the Oculus headset and dealing with the Z axis. With the software I have, the values I can retrieve are limited and I was hoping someone could help me find a solution to ...
0
votes
0answers
9 views

Clarification on a rasterizing curve drawing algorithm

The algorithm in question is described in this paper. The author describes the general approach to plotting a curve (page 10): ...
-2
votes
2answers
82 views

What is the algorithm to add 2 binary with boolean operations? [closed]

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
0answers
16 views

How to solve constrained ode problem

Currently I'm facing question in which let's say I have 3 coupled eqn. \begin{align} x = f(x', z', y', t) \\ y = f(x', y', z', t) \\ z = f(x', y', z', t) \\ \end{align} There is initial ...
0
votes
2answers
41 views

what is the complexity of this type of algorithms (loop bounded)?

I have an algorithm which contains only the instructions of type: $X_i=X_j$ $X_i=X_i+1$ $\text{while }(X_i\le N)\text{ do }\{C\}$ where $C$ is another instruction $N$ is a global constant and ...
0
votes
0answers
7 views

Function to increase entropy for a specific number and seed and reduce it for the rest

Hello I think I am wording the title correctly. I am looking for a function / algorithm that can increase the variability or entropy of a specific number and reducing it for the rest. The function can ...
0
votes
1answer
17 views

Weighted Random Selection

I read a blog post about a simple algorithm to select a random item from a list, certain items in the list were weighted to increase the chance of it being selected. Add up all the weights. Pick a ...
1
vote
1answer
40 views

Minimize the squared dot product of two specific vectors

Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with ...
0
votes
0answers
31 views

On Tree- Doubling Algorithm

Use the Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically. Need help to this question. Thanking you.
-1
votes
0answers
32 views

The minimum number of machines to install the software on to clean the entire network

A Worm has affected all computers in a companies LAN network. The worm removal software is licensed in such a way that only adjacent machines (connected directly by a cable) can share a copy of the ...
0
votes
1answer
15 views

What is the lower bound for an algorithm that reconstructs a permutation?

In this challenge on codegolf.SE, one has to reconstruct a permutation $p$ of a vector of length $n$ given only a function $P\colon\{0,1\}^n\mapsto\{0,1\}^n$ which applies $p$ to a vector of booleans, ...
0
votes
1answer
40 views

Finding minimum paths in Graph theory

A Canadian postman, rather than returning to the post office $(p)$ after delivering mail along every street in town, wishes to return straight home $(h)$. Let $G$ be a connected graph and $p , h $ ...
0
votes
1answer
28 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
0
votes
1answer
39 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
0
votes
1answer
32 views

How to “layer” two scale adjustments in a formula?

First: I apologize for the title, I truly don't know what the correct terms to describe my problem are. If I receive suggestions for a more appropriate title or learn some new terms I will revise it. ...
1
vote
1answer
36 views

Why is the time complexity of factorization $2^n$?

Can somebody explain to me why, given the factor value N, the time complexity of a factorization algorithm (N / 2, N / 3, N / 4, ...) is $2^n$ rather than n?
3
votes
0answers
25 views

Check if a point is inside a rotated 2D NACA 0012 airfoil

I've already checked the rotated rectangle problem but this is (I think!) a little more complicated. I have a CFD calculation of a 2D NACA 0012 airfoil and I need to test if a point is inside the ...
3
votes
1answer
58 views

Infine Sequence ${1, 3, 2, 3, 1}$

I have an infine sequence where at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends a and b (inside which the numbers are absent) we ...
-6
votes
1answer
211 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
3
votes
1answer
62 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
1
vote
1answer
28 views

Function (algorithm) for obtaining random number(s) from dice

I'm afraid I don't speak maths very well. I hope this question is sufficiently comprehensible and mathematical. Suppose I have a perfect D$x$ (i.e. $x$-sided) die, and a pen and paper, and with these ...
0
votes
0answers
15 views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
2
votes
0answers
30 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
1answer
54 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
0
votes
1answer
23 views

Does it make sense to use optimization algorithms(Like ACO) in weighing average to find weighs

I am going to use a DEM fusion method using simple weighing average,I am going to use 2 inputs to create my fusion function W1X1+W2X2/(w1+W2)=result this is a ...
0
votes
0answers
18 views

Checking the correctness of my triple-nested loop analysis

I am trying to analyze the complexity of a triple-nested loop. Using previous posts here as a guidance, I believe I have arrived at the correct solution. However I would appreciate if somebody could ...
0
votes
3answers
52 views

Point inside the area of two overlapped triangles

The question is as simple as that, but I have been trying to figure out an answer (and searching for it) with 0 results. I mean, given two triangles (in 2D) I want to find just a single point which ...
1
vote
0answers
54 views

Best lotto algorithms 7 from 42

I have been looking for some algorithms to solve some problems with lottery 7 from 42. My question is , what is the best algorithm to guess at least 2 numbers from selected 7: example , I am able ...
2
votes
3answers
94 views

Expected value of number of sorted elements in a permutation

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is out of ...
0
votes
1answer
22 views

Algorithm design: θ(f(n)) - help explaining my answer

I am studying algorithm design and need some help explaining my (correct) answer to the following question: Assume that $T(n) = \Theta(n^2)$. Can we say that for every input size $n$, our ...
1
vote
1answer
28 views

Mathematics and Algorithms for Interpolation

I am doing some programming, where I am interpolating point a to point b, against a timer that is constantly incrementing by ...
2
votes
0answers
30 views

Explanation of the algorithmic form

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.The core of the algorithm is the replacement of a string of $1's$ ...
4
votes
3answers
401 views

Proving big oh by notation with full expression power

I am trying to prove that: $(n^2 + 1)^{10}$ is $O(n^{20})$ but I am not able to figure out how can I prove it with full expression having a power. Any suggestions?
2
votes
1answer
29 views

“The three shooters algorithm”

As requested at http://stackoverflow.com/questions/29111313/the-three-shooters-algorithm?noredirect=1#comment46504341_29111313 I have moved that topic into here: Like the title says, you've got 3 ...
3
votes
1answer
41 views

Understanding the QR eigenvalue finding algorithm

I'm trying to code up a matrix library (purely as a learning exercise). This question is about the math I'm trying to understand in order to implement it. I just want to make sure I have a firm grasp ...
5
votes
1answer
120 views

Power towers of $2$ and $3$ - looking for a proof

Let $\uparrow$ denote the right-associative exponentiation operator: $a\uparrow b\uparrow c=a\uparrow(b\uparrow c)=a^{b^c}$ There is a sequence $A248907$ recently submitted to OEIS (see also ...
0
votes
2answers
15 views

$T(2N)/T(N)$ ~ $2^b$ (Please help me step out this simplification)

Algorithms textbook says if $T(N)$ ~ $aN^blgN$ then $T(2N)/T(N)$ ~ $2^b$ $$T(2N)/T(N) = a(2N)^blg2N/aN^blgN$$ $$= 2^b(1+lg2/lgN)$$ $$ = 2^b$$
1
vote
0answers
28 views

Algorithm to divide a set of symbols with constraints into minimum number of subsets

I have a set $$ S=\{a,c,d,e,f,j,m,q,s,t\} $$ with a constraint $$ C=\{am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js\} $$ where $xy$ in $C$ means that $x$ and $y$ cannot be in the same subset. ...
1
vote
1answer
25 views

Min/Max number of inequalities needed to determine the order of $n$ numbers

We are given an ordered $n$-tuple of positive real numbers $R=(r_1,..r_n)$. A $k$-inequality is an inequality of the form $x_1<x_2<...<x_k$ where $x_1,..,x_k$ are in $R$. For example, for ...