Tagged Questions
Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
0
votes
0answers
20 views
Inversion and permutations
Let call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x.
For two ...
1
vote
0answers
29 views
Easiest way to find the highest count of sequential numbers in an array? [on hold]
I'm having a programming problem that I'd like to know if there's an easy way to mathematically solve it.
Say I have an array of integers, how can I easily find the highest number of sequential ...
-1
votes
1answer
38 views
Probability of 1 at both end of string
Given a string S having N characters long and consists of only 1s and 0s.
Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive.
What's the probability ...
0
votes
0answers
23 views
Parity of number of factors up to a bound?
Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$.
The question is to find a fast algorithm to find that ...
0
votes
0answers
36 views
How to determine if a convex polytope is contained in a union of convex polytopes?
Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
1
vote
1answer
31 views
Normal number generator with digit extraction algorithm?
Are there any known ways to define an absolutely normal number (or very likely normal) number, which posses digits that can be extract via algorithm? I want to find numbers like pi that are normal and ...
2
votes
1answer
37 views
Checking connectivity of adjacency matrix
What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge.
There is another ...
0
votes
0answers
14 views
Data structure issues with incremental Delaunay triangulation
I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices.
The issue I have is that the structure ...
0
votes
1answer
37 views
Find longest vector by summing some vectors in given set
Given $n$ vector $(x_1, y_1), (x_2, y_2),(x_3, y_3),\dots,(x_n,y_n)$. Find a subset S of vector such that $\text{}\left |\sum_{v\in S} v\right |$
Sorry for my English.
Please give me a hint how to ...
-1
votes
1answer
20 views
Inductive Proof Algorithm
so I'm working on an algorithms assignment and am having a tough time understanding what to do:
The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$
Right now I have gotten this far:
$$T(1) = ...
0
votes
1answer
15 views
Building bicubic coons patch from four boundary curves
I want to create s coons patch surface from four boundary curves s1(u), s2(u) q1(v), q2(v)
I know that equations are the following (added screenshots from a presentation):
There are a few ...
0
votes
0answers
11 views
Question about set and series notation in the GSP Algorithm
I tried this in programming forums with no luck and since my primary issue is with the notation, I'm asking here:
I have the definition of the GSP Algorithm: Definition
However I don't understand ...
1
vote
2answers
40 views
How to find the asymptotic behavior of these sums?
Let
$$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$
$$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$
$$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$
For the first, I don't have a formal proof but I ...
2
votes
0answers
16 views
Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.
The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
0
votes
0answers
22 views
An algorithm for linear equation system problem
Is there an algorithm for the following:
I have 30 linear Diophantine equations of the following form:
$$a_{1,1}x_1+\cdots +a_{1,16}x_{16}=b_1$$
$$a_{2,1}x_1+\cdots +a_{2,16}x_{16}=b_2$$
...
0
votes
0answers
15 views
What's a method of finding when a repititious multi-dimensional function repeats when clamped?
Here's some code. Don't try to understand it, but refer to it:
...
1
vote
0answers
19 views
Enumerating certain size 15 square matrices
This is an attempt to tackle A zero sum subset of a sum-full set by complete enumeration.
I am looking for an algorithm which will efficiently (i.e. within reasonable time, several hours at the most) ...
1
vote
1answer
50 views
Find 3rd largest number out of 7 under at most 11 comparisons
I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
0
votes
3answers
26 views
Algorithms and their complexity [on hold]
For this algorithm... I have that it continuously multiplies the x and m terms together, but what would the proper wording for "what it does"? I know there has to be some reason that they do this ...
0
votes
1answer
27 views
How to simulate from a simple point process
Define a point process by the conditional intensity function
$$\lambda^*(t) = \mu + \alpha \sum_{t_i < t} e^{-(t-t_i)}$$
where $\mu$ and $\alpha$ are positive parameters.
I would like to ...
0
votes
1answer
30 views
formula for getting the least amount in the last column
I'm looking for a formula, that given $x ≥ 5$ , it will split $x$ over 3 columns with the least amount in the 3rd column, however the 3rd column must be > 0.
so where $x = 5$ it would look like:
...
2
votes
2answers
44 views
Is it possible that $j$ take the value $ n+1$?
I am looking at the algorithm of the insertion sort:
Input: $A[1 \dots n]$
...
0
votes
0answers
13 views
Produce a list of the most-similar units, given various correlations/relationships
I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
1
vote
0answers
25 views
Assign most people their first choice based on a list of preferred choices
Given a list of choices (say 100), each person in a list (say 30) has to choose 5 choices in the order they would like them to be assigned. How would I assign each person a choice making sure as many ...
1
vote
0answers
13 views
A good book with algorithmic puzzles with solutions (not of kind “how to pass and IT interview”)
can you please advise me a book with algorithmic and mathematical (IT-oriented) puzzles. But I want not one more book of kind "How to pass an interview in Microsoft / Google / any other big company" ...
3
votes
1answer
52 views
filling an occluded plane with the smallest number of rectangles
I've got a specific problem which I'll try to describe as clearly as possible.
I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
0
votes
1answer
27 views
Is there a quick way to obtain $a,b$ in $ax+by = z$ where $x,y,z$ are fixed and $x+1 = y$?
Suppose that all numbers are postive integers. Let $x,y,z$ be fixed/given and $x+1=y$. Then would there be a quick way to find set of solutions $(a,b)$ that satisfy $ax+by=z$? "Quick" would be ...
0
votes
0answers
31 views
Can I solve this problem with matrices?
So I have some two dimensional data sets thats I want to analyse. They can be viewed in 2D form as below:
$M1$:
$$\begin{matrix}00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 ...
3
votes
1answer
36 views
Total number of possible sub sequence with given condition
Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without ...
0
votes
0answers
16 views
scientific sources about modular exponentiation
Can someone provide peer-reviewed sources about modular exponentiation, particularly the right-to-left binary method?
So far, I've found the book "Applied Cryptography: Protocols, Algorithms, and ...
5
votes
2answers
114 views
How was the $3x+1$ problem checked up to $5 \times 2^{60}$?
The Wikipedia article for the Collatz conjecture states that:
The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$.
It gives ...
-1
votes
2answers
179 views
Count the whistles
Sports Teacher gathered all the players in his garden and ordered them to line up. After the whistle all players should change the order in which they stand.
Teacher gave all the students numbers ...
0
votes
0answers
2k views
Minimum moves to reach destination [closed]
Moderator Note: This is a current contest question on codechef.com.
Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to ...
1
vote
2answers
77 views
Most Efficient Method to Find Roots of Polynomial [duplicate]
I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
0
votes
0answers
33 views
Biggest common sub-string search asymptotics
What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
25 views
Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms
I want to better understand the following concepts: "n!", "e^n".
I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...
0
votes
0answers
76 views
Finding smaller matrix in bigger matrix
Given a bigger matrix of size R*C .Where each element of matrix is between [-20,20].
Now i need to find a smaller matrix of dimension H*W (H <= R, W <= C) in such a way that sum of squared ...
0
votes
0answers
12 views
(Algorithm complexity) Find properties of ≪ relation
I got a exercises related to algorithm complexity analysis as below
...
2
votes
0answers
45 views
Risch Algorithm for trigonometric functions
I've implemented the transcendental Risch integration algorithm for logarithmic and exponential extensions ('classical Risch').
If I want to integrate functions containing trig-functions I have to ...
5
votes
1answer
92 views
When does $(a,b) \to (2a, b-a)$ terminate? ($a \leq b$)
I've got a following problem.
Let's have two integers $a$ and $b$, assume $a \leq b$ (if not, we swap them)
Algorithm is just one step, produce new numbers: $2a$ and $b-a$
Algorithm stops when $a ...
4
votes
1answer
134 views
Find if a point lies in all given circles
I have a set of n given circles. I want to find that if there exists at least one point that lies in all of the given circles. Is there a method to do so? I can ...
0
votes
0answers
46 views
Probability with dice sum K
Alice rolls a N faced die M times. she adds all the numbers she gets on all throws. What is the probability that she has a sum of K.
A N faced die has all numbers from 1 to N written on it and each ...
1
vote
1answer
55 views
Count pairs with odd XOR
Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd.
Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
1
vote
0answers
27 views
Proper subsets with closest sum
Suppose you have sets $A$ and $B$ of positive reals, with $sum(A) = sum(B)$. Is there an efficient algorithm to find proper subsets $A_1$ of $A$ and $B_1$ of $B$ such that $abs(sum(A_1) - sum(B_1))$ ...
0
votes
4answers
36 views
Generate random numbers in a random fashion
How can I generate 9 random numbers between 1 to 9,without repetition, one after another. Its like:
Lets assume that the first random number generated is 4, then the next random number has to be in ...
1
vote
0answers
21 views
Splitting a graph into two isomorphic parts
Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
1
vote
2answers
41 views
Creating a mathematical formula to price a taxi booking
I've been asked to create a mathematical formula that will be used to price taxi bookings at a local taxi company.
Current system used:
A table is used as a reference
Variables:
x is the ...
0
votes
0answers
57 views
2 player team knowing maximum moves
Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know.
And also find out how ...
0
votes
2answers
29 views
In Dijkstra algorithm, it takes the source, what about the sink?
I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex?
How can it work?
Thanks a lot.
0
votes
2answers
350 views
Finding Coprime triplets
Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor.
Example : Let N=4 ...
