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

learn more… | top users | synonyms (1)

0
votes
1answer
35 views

Algorithm for the independent domination number

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
0
votes
1answer
51 views

Is $n^2$ bigger than $n\log n $? [duplicate]

How to prove $n^2$ is bigger than $ n\log n $? Do I have to use L'Hôpital's Rule? Can you give me an idea?
0
votes
1answer
45 views

Proof that Gale-Shapley is man optimal

I'm having trouble following this proof that the Gale Shapley algorithm always outputs an optimal matching for men. Overall I find it hard to follow (probably because I find the notion of "optimal ...
0
votes
0answers
40 views

Sum of all numbers less than equal to X relatively prime to all number less than Y

Here's a programming question probably needing lots of math: Given two integers X and Y, you need to find the sum of all positive integers less than or equal to X, which have no divisor smaller ...
0
votes
0answers
12 views

Using radix sort for sorting $n$ real numbers (number of digits is bounded)

Let it be $N$, a set of $n$ real numbers. We will assume that the number of digits for all $n_i$ at $N$ is at most $c=O(1)$. I want to modify radix sort, so that I can sort with it the set $N$ in ...
1
vote
0answers
56 views

number of strings which differ at atmost n positions?

I have been given a string T comprised of only 's','t','u','v' as characters . I want to find numbers of strings with length |T| which differs at atmost n position from T. Also each such string must ...
0
votes
1answer
118 views

Multiply $3$ or more numbers at the same time.

Consider a set of numbers $N \in \Bbb N $ in the range $[1, M[$, where all the numbers are co-prime with $M$ How can we easily multiply certain numbers of that set at the same time, where computation ...
0
votes
0answers
25 views

Determining integer solution for the system of two linear equations

Let $a_1, a_2, \dots a_m$ be unknown non negative integers and $n_1, n_2, \dots n_m$ be strictly increasing sequence of positive integers. How to determine that if the system $$\sum_{i=1}^m a_i = P;\ ...
2
votes
1answer
83 views

Mathematically representing combinations with integers uniquely?

Say I want to pick up $k$ amongst $n$ with respect to order. I am thinking about splitting it into two separate problems. ...
-1
votes
0answers
6 views

Forming Equal distribution equation

I have a problem but I can't convert it to a math equation. I have an amount of xray films that I want to distribute to a number of radiologist for reading. The distrubtion should observe the no. of ...
0
votes
0answers
23 views

Algorithmic differentiation graph

I have very basic question about reverse mode algorithm calculation. It is well-known that we calculate derivatives according to chain rule, using sub expressions. I was trying to find kind of proof, ...
1
vote
1answer
29 views

The HITS Algorithm and its Authority Graph

I'm currently reading over this article about the HITS searching algorithm (note that this question doesn't require knowledge of HITS, only that of basic matrix theory). On page 14, Definition 4.3, ...
1
vote
1answer
44 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
4
votes
0answers
43 views

Are algorithms for elimination of quantifiers over the reals practical?

I wanted to find the semialgebraic set in the $(a_0,a_1,a_2,a_3)$ space that guarantees that there exists at least one real root of the general polynomial equation of degree 4. For that purpose, ...
0
votes
1answer
15 views

Explanation of proof of correctness of Gale-Shapley algorithm

I'm going over a proof that after the Gale-Shapley algo runs, all men and women are matched. From these slides Claim. In Gale-Shapley matching, all men and women get matched. Pf. [by ...
0
votes
0answers
20 views

Placing gas stations

This is similar to a vertex cover problem but it will be smaller than a vertex cover. Think of this problem as you have a map and the vertices are cities and the edges are the roads from one city to ...
2
votes
0answers
50 views

How to model task scheduling with constraints

I am trying to model a task scheduling with constraints, in order to understand which model or algorithm is better suited to compute an optimal solution. Suppose I have $n$ jobs with CPU loads ...
1
vote
0answers
23 views

How can one manually calculate the date conversion to the Hebrew calendar

There already are algorithms that can be used to concert a date from different calendars into the Julian Day Number (JDN) and a JDN into the Hebrew calendar. But how can one calculate the conversion ...
0
votes
0answers
29 views

General Multiplication Algorithm for Finite Field of GF(p^m) for small values of p^m

I am working on a small computer program to generate multiplication table of general finite field in form of GF(p^m) where p is a prime number and m is an integer greater than one. While the special ...
0
votes
0answers
36 views

How to argue a problem is NP

I was given an example where the last letter of the first word is the first letter of the second word and the last letter of the second word was the first letter of the third word and so on... So, ...
4
votes
1answer
52 views

How do I prove that this algorithm about selecting sets of 3 objects works?

I have a selection of balls of different colours. I want to remove selections of three differently coloured balls in order to leave as few as possible. For example if I have 3 red, 4 green, 5 blue ...
0
votes
0answers
14 views

QR algorithm didn't give the expected result

QR Algorithm can be Applied to any Hessenberg Matrix (source) https://en.wikipedia.org/wiki/Eigenvalue_algorithm#Iterative_algorithms $$A_{k-1}=Q_kR_k, ~A_k=R_kQ_k$$ EigenValues = $diag(A_k)$ ...
0
votes
0answers
13 views

Disjoint Ordering

Given $N$ sets, $S_1, S_2, S_3, ... , S_n$. Their elements are numbers from $1$ to $M$ and size of the sets could be different. Find an ordering $O_1, O_2, O_3, ..., O_n$ such that for every $i \neq ...
0
votes
0answers
13 views

Calculating Split Info with given equation not matching solution

I'm given the formula to calculate the Split info but cannot seem to calculate the correct answer of 0.926 that the example shows. Split Info $= -\Sigma \frac{\mid D_j\mid}{\mid D\mid} * log_2 ...
3
votes
0answers
21 views

Finding optimal connections between elements of set

I'm a $3$rd year Math undergrad and I decided to take an algorithms extra class. This question was a bonus one on my mid-term and I still have no idea on how to approach it. Given an array solely ...
0
votes
1answer
14 views

relations between Lower bound of 2 algorithems

I am given two algorithms A and B, with worst time complexity $$ f_A (n) $$ and $$f_B (n)$$ Respectively.Now it is given that: For each n there exists and input x of size n such that the number ...
0
votes
2answers
55 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - ...
1
vote
1answer
45 views

Algorithmic differentiation

If we have function $f(x)=(x+x^2)^2$ we need fix the dependent variable to be differentiated and computes the derivative with respect to each sub-expression recursively, according to chain rule we ...
0
votes
2answers
32 views

How can I effectively solve linear system $Ax = b$ with some known variables

Consider system $Ax = b, x = (x_1,\ldots, x_n)^T$. Suppose that some of variable $x_i$ is known. How can I find the rest of unknown variable effectively? Assume that system has unique solutions ...
1
vote
1answer
19 views

Computing (the number) of paths in a directed graph starting from the initial state

(This is related to one of my academic projects) Given a directed graph $G=(V,E)$, and $s_1\in V$ the initial state, Let's call a primitive path a path starting from the initial state and does not ...
1
vote
2answers
134 views

Check if a number is Carmichael

I am trying to implement Modified Miller-Rabin Algorithm by Shyam Narayanan (https://math.mit.edu/research/highschool/primes/materials/2014/Narayanan.pdf). The algorithm demands to check if a number ...
-1
votes
2answers
52 views

An algorithm for finding the intersection point between a center of vision and a surrounding rectangle

In plane $\mathbb{R}^2$, a rectangle $R$ with center $P_2(x_2,y_2)$ and vertices $(x_2 \pm w, y_2 \pm h)$ (sides parallel to axes) is given. We consider the transformation which, to a given point ...
0
votes
0answers
50 views

About an integer factoring algorithm

I have been toying with the following algorithm: ...
1
vote
1answer
31 views

What would “$a$” be in this scenario?

I was given the following description for a problem, and I'm uncertain on what $a$ is meant to represent Let $S(n)$ be the sum of all positive integers $m$ not exceeding $n$ having the following ...
1
vote
0answers
61 views

Finding all lattice point in bounded region

I have a closed region in n-dimensional space bounded by two inclined hyperplane and plane along the axes. What algorithm can I use to locate all the lattice points in the region? $$ \sum_{i=0}^n ...
0
votes
1answer
22 views

Big Omega and Not Big Omega proofs

I need to proove these three sentences: $g(n) = n + 2n^3-3n^4+4n^5$ $g(n) = \Omega(n^5) $ $g(n) \neq \Theta(5n^6)$ $g(n) = \Omega(nlogn)$ Now, for the Big Omega I have no clue how to do it, for ...
1
vote
1answer
21 views

Algorithm for generating all elements of a set consisting of specific $n$-tuples

I was working on functional analysis last night, and then my mind got distracted by the following problem. Consider a set $$I=\{0,1\}$$Now consider a subset of $\mathbb{R^n}$ $$X=\{(x_1,x_2,\dots ...
2
votes
0answers
8 views

Understanding linear separability

Having read the wikipedia article and a similar question on the topic of linear separability, I still lack the understanding of this concept to explain any more than the most rudimentary euclidian ...
2
votes
1answer
82 views

How to find all systems of distinct representatives using i.e. Hopcroft–Karp algorithm?

I would like to find all systems of distinct representatives in bipartite graph. I've found Hopcroft–Karp algorithm, which finds maximal matching, which I would like to implement. But I don't know how ...
0
votes
2answers
63 views

Some diffuculties trying to compute double sums

I have the following sum $$\sum_{i = 0}^{n-2}\sum_{j=i}^{n}(i + j) + \sum_{i = 0}^{n-2}\sum_{j=i}^{n}1$$? and i have no idea how to continue from here?
0
votes
0answers
28 views

How to find this unknown variable?

Known variables: Price = 52.89 Sales = 14121.63 Unit_Orders = Sales / Price = 267 max_orders = 31734 (600 units) max_units = 600 missing_orders = max_orders - Sales = 17612.37 = (Max_units - ...
0
votes
1answer
31 views

Minimum number of steps required to visit every “special” point on a rectangular gird

I am stucked at this problem: Suppose we have the following grid configuration (or matrix) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$ (I.e $G$ is a matrix that have $m$ rows and $n$ colums over the ...
3
votes
3answers
37 views

Algorithm/formula for computing the probability of winning a range of games

As of this post, the Golden State Warriors have 68 wins and need to win at least 5 of their remaining 7 games to break the record for most wins in a season. This article estimates the Warriors' chance ...
0
votes
0answers
19 views

Uniqueness of spanning trees made using search algorithms?

For undirected graphs, the corresponding spanning trees can be obtained using various search algorithms like Depth-first search algorithm , Bredth-first algorithm, etc. I am not sure whether the ...
0
votes
0answers
20 views

Complexity of a randomly-traveled N*M grid

I made an algorithm that compute a random-path across a N*M grid using backtracking. It start at [N / 2][0] and shall finish at [N / 2][M - 1]. Each iteration he choose a random direction (Left, ...
2
votes
2answers
96 views

Is there a way to mathematically prove my teaching assistant is wrong?

Our design of algorithms class requires all students to enroll in an online $AI$ competition, where each team has to come up with a bot. Before the final lockdown, each team is allowed to challenge ...
5
votes
1answer
102 views

Amount of zero in a range

I'm stuck with a calculation. If a person would write down, Everytime he sees a zero and counts +1. 10 counts as 1 zero. 100 counts as 2 zeros. 1000 has 3 zeros. 1005 counts as 2 zeros. Is there ...
2
votes
1answer
42 views

Proofs Involving an Algorithm

Okay. I've been trying to work on a math proof and then I fell asleep. I feel as if it should be obvious but I'm not getting it at all. The following is the info: $$\frac{A}{B} = \frac{1}{n_{1}} + ...
0
votes
0answers
23 views

Pattern matching algorithm

Given a text $t[1 . . . n, 1 . . . n]$ and $p[1 . . . m, 1 . . . m], n = 2m,$ from alphabet $[0, Σ−1]$, we say $p$ matches $t$ at $[i, j]$ if $t[i + k − 1, j + l − 1] = p[k, l]$ for all $k, l$. ...
1
vote
0answers
13 views

Potential Function Runtime

The potential function of a Fibonacci Heap is Φ(H) = t(H) + 2m(H) CLRS states in Figure 21.2 ...