Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...