Questions tagged [algorithms]
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).
0
votes
1answer
30 views
Finding the last non-zero digit of $n!$ in $O(1)$
I saw a few approaches of finding the last non-zero digit using recurrence relation, CRT etc. I came up with a trivial $O(1)$ approach but didn't find it anywhere so asking it here.
We can write $1\...
0
votes
0answers
10 views
Detect intersection in constant time?
I'm working in an algorithm and one of the steps requires me to check whether or not 2 sequences of integers are what I call 'compatible' this is, their intersection is empty. I managed to make this ...
1
vote
0answers
14 views
Characterization of totally-split primes in $\mathbb{Q}(\zeta_n)$
Let $K = \mathbb{Q}(\zeta_n)$.
If it makes it easier, feel free to restrict to $n = p^k$, or $n = 2^k$ even.
I want to find the factorization of any totally-split prime $p$ (smaller is better ...
1
vote
0answers
23 views
How to find the shortest path that pass through a group of Sets?
I have an algorithmic problem where I have a number of Unordered Sets of elements, and I need to find the shortest path (Ordered combination of the sets) that pass through all of those sets. There may ...
0
votes
0answers
29 views
Longest Increasing Subsequence Using Divide-And-Conquer
I'm required to solve the LIS problem using Divide-and-Conquer. The hint provided is the following: For each position in the array find the
cardinality of the longest sequence that ends up with it, ...
2
votes
1answer
47 views
Find two subsets with a common sum in two sequences
For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the ...
2
votes
2answers
52 views
$T(n) = T(\sqrt{n}) + \sqrt{n}$ solving recurrence
$T(n) = T(\sqrt{n}) + \sqrt{n}$
I would like to try solving this recurrence in big-O/$\Theta$/$\Omega$.
My first idea was to take $n = 2^m$ so:
$$T(2^m) = T(2^{m/2}) + 2^{m/2}$$
Which we rewrite as: ...
2
votes
0answers
24 views
Create a point with emptiest spaces in n-dimensional space
Given an n-dimensional space with boundaries and $k$ fixed points in the space. I would like to create a new point that has emptiest spaces in this set. An empty space would mean a sphere that:
has ...
1
vote
1answer
30 views
Big-O notation confusion regarding logarithms
I've been doing a series of problems regarding big-O notation, and I was under the impression that I had a grasp on it until I found this one:
'Is the statement $(\log n)^2+{1\over 30}\log n \in O((\...
0
votes
0answers
11 views
morse reduction
I was reading the paper by Mischaikow and was confused by how the MorseReduce function would run, particularly what the output would be.
Say I had a triangle with a simplex-wise filtration as given
<...
1
vote
0answers
24 views
Conjecture about smallest grammar problem.
Given an input string $s \in \Sigma^*$, we say $t \leqslant s$ if $t \in \Sigma^*$, and for some $\mu, \nu \in \Sigma^*$ we have $\mu t \nu = s$. In other words, $t$ is a substring of $s$.
Now ...
2
votes
1answer
16 views
SAT with DPLL algorithm: Why is this not correct?
I've got an exam soon and have problems understanding a specific error when performing the DPLL algorithm by hand:
We use 2 additional rules for the algorithm: One literal rule (OLR) and pure-literal ...
0
votes
0answers
13 views
Worst-case running time of getting “irreducible substrings” of an input string.
Define $t \leqslant s$ to mean that $t$ is a substring of $s$, which always includes the empty string.
Define $R_s = \{ t \leqslant s: |t| \geq 2, \ t \gamma t \leqslant s, \text{ for some } \gamma \...
0
votes
0answers
6 views
Maximal number of submatrixes in binary matrix
We have a matrix of size n x m. Elements of this matrix can be 0 or 1. We need to arrange submatrices of size 2 x 2 in such a matrix, but only with the condition that such matrices do not overlap and ...
0
votes
2answers
30 views
Straight to the point elipse drawing?
Ive been looking everywhere for a simple way of drawing elipses. However im unable to find any site that will show the algorithm in a simple straight forward way. They clutter it up with all the math ...
0
votes
1answer
28 views
Algorithm to compute $x, y$ from matrices [on hold]
For $n \times n$ matrices $A$ and $B$ where $A$ is nonsingular and b,c belong to $R^n$, design an effective algorithm to compute $x$ and $y$
$A^t x + By = b$;
$ Ay = c$
0
votes
1answer
32 views
Minimal Spanning Tree With Algorithms
So I have a homework problem as above. The topic covered in class before this homework was Dynamic Programming. I have very little clue about what the question is actually asking: what is the MST ...
0
votes
0answers
26 views
Equation/formula/algorithm for figuring out binary polynomial equation from integer
Say you have this sequence of examples:
2^0 = 1
2^1 = 2
2^1 + 2^0 = 3
2^2 = 4
2^2 + 2^0 = 5
2^2 + 2^1 + 2^0 = 6
2^3 - 2^0 = 7
2^3 = 8
...
There is some equation ...
1
vote
0answers
30 views
Are there any known methods for transforming a system of linear inequalities into a system of linear Equalities?
Begin Question
Are there any known algorithms for transforming a system of linear inequalities into a system of linear equalities? The resulting system is only allowed to use equality statements ($=$)...
0
votes
1answer
30 views
Knapsack Problem using Greedy Algorithm
I am required to show that using the obvious greedy algorithm (which I'm assuming is the approach of choosing the highest value-by-weight items first) to solve the Knapsack problem yields a result ...
0
votes
3answers
23 views
Prove that finding the maximum element is n-1
How it can be proved that finding the maximum element in the n-element set requires at least n-1 comparisons?
I think it requires proof by induction.
Thank You in Advance.
0
votes
0answers
21 views
Choice of augmenting path in the Augmenting Path Algorithm + Proof of correctness
I'm watching this video of an example of the Augmenting Path Algorithm.
https://youtu.be/C9c8zEZXboA?t=240
For convenience, I name the vertices of X, from left to right, $x_1, x_2, x_3, x_4, x_5, x_6$...
2
votes
0answers
35 views
Algorithm to calculate the positions of bezier curve control point handles to transform from circle to straight line
From the image linked below (in A, I don't have enough points to add it directly) I have approximated two bezier cubic curve segments to a circle.
I know how to move the anchor points AP1 and AP3 ...
1
vote
0answers
35 views
Choosing my most preferred card from a set of n cards.
I have $n$ cards, however, I like only 1 card the most out of all the $n$ cards and that card is my favourite. I consider the cards one by one, giving each an integer score, where the higher the score ...
1
vote
2answers
40 views
How many essentially different strings are there of length $\leq n$ and over an alphabet of size $|\Sigma| = m$?
For example, $aaaaaabb \simeq ccccccdd$ essentially, because a smallest grammar algorithm would perform the exact same steps to reduce one as the other. So how can I phrase this in terms of formal ...
0
votes
1answer
26 views
Number of iterations of a while loop
I need to find out number of iterations this while loop will perform before terminating.
I have calculated log(1000/n) and complexity is logb(n), is it correct?
...
0
votes
0answers
11 views
Complexity of A*-lasso algorithm (dynamic programming)
Consider Algorithm 1 in the Xiang & Kim (2013) paper known as A*-lasso for learning Bayesian Networks structure problem which is an NP-hard problem. It seems to me that Algorithm 1 has a ...
-1
votes
0answers
16 views
Why stable marriage algorithm outputs male optimal?
I am having trouble following this stable marriage optimal proof:
“The pairing output by the Stable Marriage algorithm is male optimal.
Proof. Suppose for sake of contradiction that the pairing is ...
1
vote
1answer
28 views
Invariant for Gale–Shapley algorithm (Mating Ritual Algorithm)?
I found the following invariant for Mating Ritual algorithm (Lehman, Leighton and Meyer, Mathematics for Computer Science, §6.4) while going through MIT reading material:
Definition. Let $P$ be the ...
1
vote
1answer
56 views
Is “type theory” the only way to get a computer to “do math” on its own? [on hold]
It seems like one of the direct applications of type theory definitions & algorithms is to implement them on a computer and use it for proof assistants, etc.
But why couldn't you just implement ...
-4
votes
0answers
23 views
Summation with nth power of n over n factorial [closed]
This problem was in one of my assignments this semester in Algorithm Analysis class and I really can not figure out anything. Can you help me to give bounds for this algorithm.(I think posting my old ...
0
votes
0answers
18 views
Creating the “most balanced” groups based on multiple metrics
I have data from ~850 labelled geographic regions, each with a value for 4 metrics and I am looking for a way to create the "most balanced groups".
If you measure the percentage difference of the sum ...
0
votes
0answers
28 views
Consider the following recursive algorithm, which takes as input a sequence $\left( a _ { 1 } , a _ { 2 } , \ldots , a _ { n } \right)$ of n numbers
Consider the following recursive algorithm, which takes as input a sequence
$\left( a _ { 1 } , a _ { 2 } , \ldots , a _ { n } \right)$ of $n$ numbers, where $n$ is a power of two, i.e., $n = 2 ^ { k ...
0
votes
0answers
20 views
How to find shortest bezier curve with N control points passing though N target points?
I'm working on a pattern making software (clothing). I have a set of N target points and I need to find the shortest bezier curve with N target points that goes through all the N target points.
My ...
0
votes
1answer
26 views
Is the generalized assignment problem with un-capacitated agents NP-hard?
I am working on a generalized assignment problem which I typed below. I know it is shown to be NP-hard. I am wondering whether the problem is still NP-hard when the capacity of the agents are assumed ...
2
votes
2answers
37 views
Finding an algorithm to fill in a matrix subject to conditions
I have a combinatorics problem and I am asking for a solution or a reference in order to solve it.
Since the problem is rather long, I will translate it mathematically.
Suppose I have a $n \times m$ ...
0
votes
1answer
50 views
Competition algorithm
$n$ athletes ($a_1,...,a_n$) are arranged in a line. At each time $t$, two adjacent athletes race each other. The loser is removed from the line and the winner stays in the same position. This ...
0
votes
1answer
15 views
Does k way merge sort defies the lower bound for sorting?
Support there is a Array A with size n and let n be a multiple of k. If we divide the A into sub arrays each with elements k and sort them individually, it would require k*log(k) time. Total initial ...
1
vote
0answers
28 views
How to encode a line of points so you can connect long distances using short lines
So this is mostly a computer problem but this aspect is really math heavy and could probably be easily solved with some math insight so I thought I'd ask here. It might seem a little computery at ...
0
votes
1answer
20 views
Directed Trees Question Help
For part (a), I assume we build some version of a minimal spanning tree. Instead of the total sum of edges being minimum, the path from s to every vertex must be minimal. Is there a way to reduce this ...
0
votes
0answers
10 views
Time Complexity of Building Heap
The Question is as given above. In this answer: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity,
I note that the building a heap is already O(n) complexity, ...
0
votes
0answers
28 views
How to divide people into groups to maximize happiness
I need to split about 100 people into n number of groups:
There should be equal numbers of freshmen, sophomores, juniors and seniors in each group.
There are certain preferences, such as the ...
0
votes
0answers
19 views
List of graph algorithm problems which can turn to polynomials
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
2
votes
1answer
53 views
Asymptotics of a coupled sequence
In this paper, the authors make the passing remark "simple analysis reveals that" the coupled sequence
$\mu_k = \theta_k \left(\theta_{k-1}^{-1} - 1\right)$
$\theta_{k+1} = \frac{\sqrt{\theta_k^4 + ...
0
votes
0answers
16 views
Find radius of best fit cylinder from cloud
I want to find the radius of the cylinder that best fits a cloud of points.
I used 3DReshaper to calculate the radius of the best fit cylinder for this points (format: x y z):
...
0
votes
1answer
29 views
Conditional gamma distribution
Let $X_1,X_2,X_3,X_4$ be iid and $X_1\sim \text{Gamma}(\alpha,\beta)$. Let us fix
$$T_1(X_1,X_2,X_3,X_4)=\frac1n \sum_{i=1}^4X_i=t_1,$$
$$T_2(X_1,X_2,X_3,X_4)=\frac{\left( \prod_{i=1}^4X_i\right)^{1/...
0
votes
3answers
57 views
Solving a recurrence relation: can't figure out how to convert from summation
I am really struggling to solve this recurrence.
$$
T(n) = T(\sqrt{n}) + n.
$$
I am asked to give asymptotic upper and lower bounds for $T(n)$. I am free to use any method to arrive at my answer, ...
4
votes
2answers
257 views
How can I solve this problem : $2^{x} \equiv{2070442609 \cdots 226509} \pmod {6561}$
I want to solve this discrete logarithm problem with Pohlig–Hellman algorithm:
$$2^{x} \equiv{
2070442609353644988500364779751625112994538364565830646055667805\\
...
0
votes
0answers
38 views
What does the first “non-free” variable mean here when substituting in simple type theory?
See this screenshot of the book "Basic Simple Type Theory". The infinite sequence they refer to is just a way to formalize the concept of having enough variables to work with no matter what. In my ...
0
votes
2answers
86 views
What is meant by “free choice” in mathematics?
The following quoted text was written before 1963, so the authors didn't have the benefit of decades of automated computing machines to inform their statements.
The essential feature of an ...
