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
1answer
24 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
16 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
27 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
26 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
32 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
35 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
14 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
10 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
39 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
15 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
21 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
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
0answers
41 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
43 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
12 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
48 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
175 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
32 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
75 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
44 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
133 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
45 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 ...
0
votes
1answer
54 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
349 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 ...
1
vote
2answers
36 views

Do most nonograms not require backtracking?

I get the impression that most Nonograms are "line solvable", meaning a computer never has to guess or backtrack. My understanding of this is that a tree searching algorithm isn't even necessary, ...
0
votes
1answer
20 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...