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)

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
31 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
39 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
54 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
14 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
34 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
147 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
55 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
52 views

About an integer factoring algorithm

I have been toying with the following algorithm: ...
1
vote
1answer
32 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
62 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
23 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
10 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
85 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
1answer
32 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
45 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
107 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
25 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 ...
-1
votes
1answer
35 views

A task about Bipartite Graph [closed]

You are given a number N. Your task is to find the number of Bipartite graphs on N vertices. It is possible that the number can be calculated using recurrent formula. The algorithm should be O(N^3) ...
0
votes
1answer
39 views

Automatic differentiation-Reverse mode

I am trying to understand very basics material and a bit confused about steps. If we have function $z=f(x_1,x_1)=x_1x_2+sinx_1=w_1w_2+sinw_1=w_1+w_4=w_5$ we need fix the dependent variable to be ...
2
votes
2answers
38 views

How many arithematic operations(flops) are to $n×(n+1)$ matrix of system?

Source: Linear Algebra and Its Applications David C. Lay A system of n equations in n unknows correspond to $n×(n+1)$ augmented matrix. One book says the reduction(elimination) to echelon form ...
1
vote
1answer
29 views

Generate all N-bit numbers in such an order that the number of 1s increases monotonically

For a given positive integer $N$, is there an efficient algorithm to generate all $N$-bit numbers in such an order that the number of 1s in the binary representation increases monotonically?
0
votes
0answers
119 views

Binary counting problems

Recall that counting from 1 to n in binary takes $\Theta$(n) steps; i.e., the increment operation has constant amortized cost as opposed to $\Theta$(logn) in the worst-case. a) Analyze the amortized ...
1
vote
0answers
48 views

Good books on Algorithms for a math major without any programming experience?

I couldn't find this question anywhere else so it may not be apt. I am an undergraduate mathematics major and during my discrete math class I really enjoyed the study of algorithms and recursive ...
4
votes
3answers
65 views

Minimum number of steps required to visit every corner of a rectangular grid

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 ...
0
votes
1answer
17 views

Branching/layered optimisation - how?

Imagine you had a collection of systems each with their own constraints and objective functions to optimise (likely similar in form to each other), these then collectively aggregated into a ...
3
votes
0answers
34 views

Is math recursive or iterative?

Is the process of solving a mathematical problem (algebraic equations, limits, derivatives, integrals, EDOs, trigonometric identities proof) recursive or iterative? For example, for solving $x=1+2+3$ ...
1
vote
0answers
87 views

Is there any online Huffman code/decoder?

I need to see and work with Huffman code and see how does it compress data. Anyone has any link of online Huffman coder and decoder (compressor)?
0
votes
0answers
16 views

Exact line Search in Steepest descent

I wanted to clarify the idea of the exact line search in steepest descent method. An exact line search involves starting with a relatively large step size ($\alpha$) for movement along the search ...
0
votes
0answers
34 views

Is there any two way algorithm for compressing numbers?

I have this question that is there any way we can convert a number to another number with less character in the new number? For example, Imagine we have 811008 and if we divide this 13 times by 2, we ...
3
votes
2answers
25 views

Minimal Subset that sums up to

Let $X \subsetneq \mathbb{N}$ be a finite set, and $c \in \mathbb{N}$ we are looking for a subset $$ Y \subseteq X $$ such that $\sum_{y \in Y} y \geq c$. Assuming a subset that satisfies the ...
0
votes
0answers
14 views

3SUM problem solution on the basis of cubic function and a line?

The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S. I am trying to understand mathematical solution of the 3SUM problem based on a polynomial ...
1
vote
1answer
25 views

Time Complexity of DFS

My understanding is that: 1) given a graph G with n vertices and m edges, DFS is O(n + m) 2) DFS can be used to produce a list of all simple paths between 2 vertices u and v This would mean that ...
0
votes
0answers
11 views

Does ray tracing have any speed ups in algorithm running time in the frequency domain?

Could ray tracing be Fourier-transformed so that all calculations are done in the frequency domain? I think ray-tracing a set of rays $S$ from the eye into the view frustum might be more efficient ...
3
votes
1answer
28 views

Re-Balancing Bins with Capacity Limit Problem

Let $\hat n = \{1, \dots, n\}$. Assume that we have a sequence of bins $$ B_1, B_2 ..., B_n $$ which all have the same capacity limit $c \in \mathbb{Q}$. Now, there is a finite set of items $I ...
2
votes
1answer
56 views

A smart algorithm to decide whether a simple graph is 2-regular

Given a simple graph $(V,E)$, is there a smart algorithm to decide if the graph is 2-regular? Is it really necessary to check that all nodes in the graph appears exactly twice? I have implemented ...