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
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
145 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
54 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
84 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
24 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
63 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
76 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
24 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 ...
3
votes
5answers
80 views

Tricky Nested Summation

I am trying to analyze a programming algorithm that has three nested loops. The algorithm looks like this: $$\sum_{i=0}^{n} \sum_{j=i}^{n}\sum_{k=i}^{j} 1$$. I am trying to simplify it. These are the ...
1
vote
1answer
52 views

Subsequence occurring exactly twice in pattern

Given a string $S$, consisting of letters from the set $\{0, 1\}$. We need to find a string $T$ that appears in $S$ as a subsequence exactly twice. How to tackle this problem, without enumerating all ...
10
votes
3answers
207 views

What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number: 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350 692006139 And am told that one of ...
2
votes
1answer
60 views

From currency conversions to graph modeling

The problem I am trying to solve the following programming problem (in C++). I have tried to solve it thoughtlessly just typing code and observing what happens, but, as expected, I have reached ...
0
votes
0answers
15 views

Why does knuth mastermind algorithm favour guesses in S?

From wikipedia : Mastermind > algorithms: From the set of guesses with the maximum score select one as the next guess, choosing a member of S whenever possible. I understand that the hidden ...
1
vote
1answer
24 views

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$?

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$? So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow ...
0
votes
0answers
7 views

Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
0
votes
0answers
21 views

Contour and perimeter recognition in binary image

I need to detect contour (object) and find the perimeter of a detected object. For example, I have the following image: http://i.stack.imgur.com/40TTX.png All images are binary, so they consist of ...
0
votes
2answers
37 views

How to prove $\frac15 n^2-42n-8\in Ω(n^2)$?

Here is my procedure: So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow \frac15 n^2-42n-8\ge cn^2]]$ Taking $B=1$. We have $\frac15 ...