Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
0
votes
0answers
26 views
Temporal collision between rectangles
I have the following specifications, which describe the limit collision between two rectangles moving without rotation:
...
0
votes
1answer
37 views
PageRank algorithm. Iterative approach.
Given we have 4 nodes: A, B, C, D. A -> B and A <- B, B -> C, C -> D, C -> A and C <- A, D->A. We know only the starting probability of C which is 1. If we start from node C, what are the ...
0
votes
1answer
35 views
Mathematics for algorithms
What are the best books for a programmer to improve his mathematical skills ? I am actually good at programming,but when it comes to mathematical problems,i fail sometimes !! any tips to improve my ...
0
votes
0answers
60 views
Arithmetic Coding Example
I have a question for static arithmetic coding which I have done in class but I can't seem to figure out where I got the answers. It's a bit hard to get in touch with my lecturer at the moment so I'm ...
1
vote
1answer
55 views
How quickly can we detect if a digit is in a number?
If we suppose that we have a number $n$ in base $b$, represented as a power series:
$$n = d_0 b^0 + d_1 b^1 + d_2 b^2 + \dots$$
...where the $d_k$'s are the digits, how quickly can we determine if ...
0
votes
1answer
31 views
“Location to location” algorithm?
Lets say I have two locations, each one with X, Y, Z, and a int. Each location represents one cube in a 1000 x 1000 world. Lets say I had one location at 500, 343, 284, with an int 1. Another one at ...
6
votes
1answer
41 views
Enumerating all antichains in a finite poset
I have some reasonably small finite posets (on less than 20 points) and would like to iterate over all "downsets" in the poset, where a downset is a set closed under ≤ (so if x in X, and y ≤ x, then y ...
1
vote
2answers
36 views
How to check if a number has reached given precision?
So right now I'm working on an algorithm which has to know when to terminate its calculations - namely, it should do it when the number he's acquired in the last step is at least as precise as the ...
2
votes
1answer
271 views
Largest prime below a given number N
This came up as a part of algorithm puzzles:
Given a number $N$, how to find the prime $P$ such that $P<N$ and the difference $N-P$ is minimum.
For small $N$, simple sieves do work, but I'm unable ...
2
votes
1answer
93 views
Computing RSA Algorithm
Modulus $N=247$; encryption exponent $r=7$
Encrypt $100$; Decrypt $120$.
$Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$.
For a discrete math ...
1
vote
1answer
43 views
Binary heap deletion algorithm
In a binary heap ,in order to delete an element:
We delete the node at the root - this is the node with highest priority.
After deleting there is a hole at the root, which has to be filled, and to ...
5
votes
2answers
75 views
Algorithmic approach to enumerating ideals in $\Bbb Z[x]/(m, f(x))$
I'm studying for my algebra quals this fall and keep encountering problems like the following:
List all the ideals of $\mathbb{Z}[x]/(16, x^3)$.
or
List all the primes of ...
1
vote
1answer
28 views
Computing the running time of the Fermat primality test
I have a question concerning the Fermat primality test and its running time. According to Wikipedia: "Using fast algorithms for modular exponentiation, the running time of this algorithm is $$O(k ...
0
votes
1answer
23 views
closest pair in N-Dimensional
I have to find the closest pair in n-dimension, and I have problem in the combine steps.
I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
1
vote
0answers
51 views
Is Risch's algorithm powerful enough to determine any integral of a function have a closed form or not?
Is Risch's algorithm powerful enough to determine any integral of a function have a closed form or not?
Is there a historic piece of reference that support your answer?
...
2
votes
2answers
33 views
Expressing a sequence as a recurrence relation
I've been working on a project, and it's come to that time when I have to prove the run time complexity of an algorithm. I've obtained my metric and those things that have nothing to do with you guys! ...
1
vote
0answers
17 views
Prove or disprove asymptotic relation of two sets
I am looking for a while to prove or disprove: (preparing for finals)
O(f(n)-g(n)) ⊂ |O(f(n)) - O(g(n))|
where || is absolute value. Note that ⊂ is needed and not ⊆
I assumed the a subtraction ...
0
votes
0answers
12 views
Number Theoretic Gaps for Shell Sort
Has anyone investigated the efficiency of certain number theoretic gaps for shell sort? I'm thinking the Fibonacci sequence may be interesting, or maybe the prime numbers since small coprime sets ...
1
vote
1answer
53 views
How to get the bounds of exponential function
I have this function $(\frac{d}{d+1})^d$. How can I get the lower and upper bound of this function
1
vote
1answer
34 views
Greedy Optimized Subset-Sum Problem
Given positive integers $a_1,...,a_n,b$, find $x_1,...,x_n \in \{0,1\}$ such that $a_1x_1 + ... + a_nx_n \lt b$ but is as large as possible.
How do I show that there is a greedy algorithm to this ...
0
votes
1answer
25 views
Probabilistic Polynomial Time Algorithm
Let $C$ be a language and $M$ be a probabilistic polynomial-time algorithm where $w \notin C$ implies $\mathbb{P}\{M\; accepts\; w\} \leqslant 1/8$, and $w \in C$ implies $\mathbb{P}\{M\; accepts\; ...
1
vote
2answers
41 views
Tight asymptotic upper bounds on specific recurrences
give a tight asymptotic upper bound (() notation) on the solution to each of the following recurrences.
$T(n)=2T(n/8) + \sqrt[3]n$
$T(n)=T(n/3) + T(n/4) + 5n$
1
vote
1answer
51 views
what if geometric sequence + geometric sequence
I wrote a program that basicly can find the formula of the sequence that created with any-degree equation.
For example if you give my program that sequence:
[1926, 2811, 833240, 28778265, 398155842, ...
1
vote
4answers
99 views
Error in “proof” of $n^2 \in O(n)$.
I need some help. I have homework:
I need to disprove that $f(n^2)$ belongs to $O(n)$.
Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
0
votes
1answer
61 views
What is the value of this loop counter
Came across this question but unable to solve. What will be the value of the variable "counter"
int counter = 0;
for (int loop_1=0; loop_1 < 10; loop_1++) {
for (int loop_2=loop_1 + 1; loop_2 < ...
0
votes
1answer
62 views
Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item
I have the following problem of which I am attempting to find a near optimal solution:
I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
0answers
65 views
Algorithm for Dynamic Programming of Kleinberg Book
I need help for this about answer and program of it with C.
From Kleinberg & Tardos's (2006) Algorithm Design, pp. 334–335:
29. Let $G = (V , E)$ be a graph with $n$ nodes in which each pair ...
1
vote
1answer
30 views
Solving recurrenc using recurrence tree method.
I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$.
I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
3
votes
1answer
52 views
Subtraction of Big $O$'s
So we were asked to prove something in class, but I can't understand the following expression:
What is $O(n^2)-O(n^2)$?
I understand big O notation, but what I don't understand is the ...
3
votes
2answers
99 views
Writing $n$ as $a*b$
This was asked in a facebook interview .
Given a number, find the number of ways you can split it into two
numbers such that each of them is greater than $1$ and both the
numbers don't have a ...
1
vote
0answers
87 views
Divide irregular polygon into hexagons
I'm working on an engineering project, i was asked to divide an irregular polygon into (n) hexagonals like in this image:
would like to know if there is an algorithm for distribution ?
0
votes
0answers
36 views
How does double hashing work?
Suppose we have a hash table with 13 elements, and we want to insert an element with key 14. If we're given hash functions $h_1(k) = k\mod13$ and $h_2(k) = 1+(k\mod11)$, how can we determine which ...
1
vote
1answer
22 views
tree that approximates the distances and total weight in graphs
I have this problem : given undirected graph we can build a tree that approximates the distances from given vertex ,r, and the total weight,
i.e. for every vertex x, $d_G(r,x) \le d_T(r,x) \le ...
0
votes
2answers
37 views
Determine no of combinations for cutting stock algorithm
I have to buy $n$ wooden logs of size 2000 each, from which I have to cut different pieces of smaller size say:
255*10
750*7
550*13
In a manner that cutting will ...
2
votes
2answers
55 views
Prove that consecutive Legendre Polynomials do not have a common root.
I am using the following definition of Legendre Polynomials:
$P_0(x)=1$
$P_1(x)=x$
$\displaystyle P_{k+1}(x)=\frac{2k+1}{k+1}x P_k(x)-\frac{k}{k+1} P_{k-1}(x)$
Q: Prove that for no $k\in ...
1
vote
2answers
44 views
gradient descent optimal step size
Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
1
vote
1answer
50 views
Is there an optimized version of rectangle packing algorithm?
I have a rectangle with 200 width and 100 height. I have a mix pool of 50 rectangles and boxes. The rectangles comes in shapes like 20x40, and 40x20. The boxes will come in shapes of 20x20 and 40x40. ...
1
vote
0answers
39 views
L-systems and Sierpinski Triangle
I was just shocked when I saw these consecutive outcomes of an L-system converging to the Sierpinski triangle (shown in this picture).
I'm interested to know how can one arrange the rules of an ...
1
vote
1answer
49 views
Ranked Preference Matching Algorithm
first dropping the link that will serve as reference: NRMP Residency Matching
I have a sort of side project (nothing riding on it, computational performance not an issue, so feel free to go wild, I ...
2
votes
1answer
199 views
How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:
INDEPENDENT SET VALUE
Input: An undirected graph $G$.
Output:The size of the ...
4
votes
2answers
72 views
Accounting for changing radius of a paper roll to always unroll the same amount of paper
So I'm building a Post-Turing Machine that's running a 5-state busy beaver. It has a 300ft roll of receipt paper at each end simulating an infinite tape.
Hypothetically the tape is divided into ...
0
votes
1answer
47 views
How to derive this result?
Problem is to find the total number of zeroes in the decimal representation for the series with input $N$
$0, 1, 2, 3, 4, 5 ... \text{upto} \, N$
due to time limit constraints run time ...
1
vote
1answer
55 views
Generalized Josephus problem
I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as
f(1) = a
f(2n) = 2f(n) + b, for n >= 1
f(2n+1) = 2f(n) + y, for n >= 1
...
2
votes
0answers
24 views
Parametric Weighted Graph problem
Let $G=(V,E)$ be a weighted directed graph with edge-weights given by linear functions $f_i(x) = ax-b$, $0 < a < 1$, $b > 0$. For a given starting parameter $x_0$, a path from $v_i$ to $v_j$ ...
1
vote
2answers
65 views
genetic algorithm binary encoding
I am trying to write a program for maximizing a function using a genetic algorithm. The function has $n$ integer variables $x_1 \dots x_n$, such that each variable is in the range [-n,n].
What is ...
0
votes
1answer
58 views
How to use Warshall's Algorithm
This question appeared on my homework and I don't have the slightest idea how to solve it!
...
0
votes
1answer
38 views
Algorithm for root function $[2^{n-1}]$
I am attempting to convert this function $[2^{n-1}]$ into a root function to return original value. Thus far all my attempts have ended in abject failure.
Base : 1 2 3 4 5 6 7 8 9
Result : ...
1
vote
1answer
46 views
Recursive algorithm correctness: problem.
Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
0
votes
1answer
71 views
Find coordinates of n points uniformly distributed in a rectangle
I have a rectangle R of width W and height H.
I have N points inside this rectangle.
I need to find an algorithm to position my points in the rectangle in the most uniform way possible (no overlaps, ...
0
votes
1answer
37 views
A mathematical function for: Adding one to x if x is decimal
I was wondering if there is a mathematical function for this:
If x is a decimal value, we subtract all decimal values from x ...
