Tagged Questions

Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
81 views

Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
0
votes
1answer
43 views

Find an algorithm with O(n) for making Chairlifts on N mountains

Today, I encountered an interesting problem in my textbook. The problem is: Utopia city has N mountains with height of $$h_{1}, h_{2}, h_{3}, ..., h_{n}$$. We want to make a chairlifts which pass from ...
1
vote
0answers
41 views

Modification of Levinson algorithm for hermitian toeplitz matrix

I have implemented Levinson algorithm for toeplitz matrix by book: Blahut "Fast algorithms for digital signal processing". Book said - modification of this algorithm for hermitian matrixes is simple ...
0
votes
1answer
19 views

compute an order value for an array of arrays

I am trying to find a solution to the following problem. I am not a mathematicians so my language might need some improvements, but here it is. I have $n$ groups of numbers. Each Group of numbers ...
1
vote
1answer
143 views

running time of a multiplication algorithm

Here is a multiplication algorithm: given inputs x and y, add x to itself y - 1 times: z = 0 while y > 0: z = z + x y = y - 1 return z What is the running time of this algorithm? Is it ...
0
votes
1answer
48 views

consider the following subroutine, what is the running time

Suppose A(.) is a subroutine that takes as input a number in binary, and takes time O($n^2$), where n is the length (in bits) of the number. (a) Consider the following piece of code, which starts ...
2
votes
3answers
142 views

how does the n-bit number related to big O notation

in algorithms you frequently have to evaluate problems like this, Let $x$ be an $n$-bit integer. For each of the following questions, give your answer as a function of $n$. my question is simple, ...
1
vote
2answers
3k views

Can you help me to solve the recurrence relation $T(n) = T(\sqrt n) + 1 $?

I have this recurrence relation to solve : $T(n) = T(\sqrt n) + 1 $ I have tried to expand the recursion but I stopped here: \begin{align} T(n) &= T(n^{\frac12})+1\\ &= ...
0
votes
2answers
68 views

Meaning of $O(n)$ in an expression

As my mathematical knowledge is increasing, I have been seeing more and more of $O(n)$ implementation in expressions. Here is what I mean. Example: $$z^{q_{N+1} + q_N} w^{q_{N+1} + q_N} (-1)^N (w-1)/w ...
2
votes
3answers
352 views

Project Euler's Problem Number 88

I am tackling Project Euler's problem number 88, which in a nutshell reads: Let $S_n$ be the set of sequences of natural numbers $(s_1,s_2,...,s_n)$ where $s_1\leqslant s_2\leqslant\cdots\leqslant ...
1
vote
1answer
64 views

Travelling Salesman on Subset of Points

I'd like to solve the travelling salesman problem, except that the salesman only needs to travel to a subset of the locations. Each location has exactly one client, and each client has a "type". For ...
1
vote
1answer
102 views

Quick algorithm to compute the order mod m for an element from quadratic field?

For $a+b\sqrt{q}$,where a, b, q are integers and q is square-free, what's the quick algorithm to find the minimal integer n that $(a+b\sqrt{q})^n=1\pmod{m}$? P.S. ...
0
votes
1answer
73 views

How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
1
vote
2answers
73 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
2
votes
1answer
93 views

What is the bound of: $T(n) = T(n-2) + (n)log(n)$?

I am given the following recurrence relationship: $\ T(n) = T(n-2) + nlog(n)\\ T(1) = T(0) = constant$, I need to find the order for the recurrence. So, using the iterative methodology, what I ...
1
vote
1answer
54 views

How does my textbook come up with this statement? I don't believe it to be true.

My textbook (Introduction to Algorithms) states the following: When polynomially comparing $n^\epsilon$ and $lgn$, it states that $n^\epsilon$ is polynomially greater for any positive $\epsilon$. ...
1
vote
3answers
79 views

Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem: As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence, we ...
2
votes
1answer
141 views

Identifying Ways of Dividing an Area into Merged Regions

Suppose an area is divided into N irregular regions. Unless N is very small there will be many ways in which a new division of the area can be obtained by merging adjacent regions. I want to ...
0
votes
1answer
274 views

Big Oh Notation for a Recursive Algorithm

I have a question that I'm unsure of: Express the complexity of the following method using big-O notation. You must explain how you arrived at your answer. What value is returned by the call ...
0
votes
1answer
39 views

Repeated Recurrence Substitution

T(n) = n + 2 * T((n − 1) / 2) Where n = 2^k - 1 I got to step i but I don't know how to get the general step i. Step 0: T(2^k - 1) = 2^k - 1 + 2T (2^k - 2) Step 1: T(2^k - 1) = 2^k - 1 + 2^k - 2 ...
1
vote
2answers
561 views

Newton's method for polynomial interpolation

I've seen that in Newton's method for interpolating polynomials, the coefficients can be found algorithmically using (in Python-ish): ...
1
vote
0answers
70 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
1
vote
2answers
192 views

Greedy algorithm

Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the denominations available are pennies (1-cent coins), nickels (5-cent coins), and quarters ...
1
vote
0answers
79 views

Deriving right relation from collected data.

This is an elaborate version of a question i asked earlier. Lets say I have a data set from a user, which is logs of event occurred. ...
1
vote
5answers
127 views

Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
0
votes
1answer
143 views

How to generate the n-simplex?

I was following this wikipedia section, in the simplex article to see if I could create a MATLAB algorithm to generate a simplex with $n$ points in $3$-dimensional space. Sure enough it works for 4 ...
0
votes
2answers
50 views

Algorithm analyse with Big-Theta notation

Is $(n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$ ? My solution: $$ \begin{aligned} c_1 \cdot (n \log n) \le\,& (n \log n) + \frac{\lfloor(\log n)^2\rfloor + ...
2
votes
2answers
132 views

Maximum number of seating plans

15 people will be seat in a row of 15 chairs. Two seating plan are considered the same if two plans share same adjacent quadruples. What is the maximum number of seating plans can be made? For ...
0
votes
1answer
14 views

Calculate the 1 in a value

I am getting different values from a computer program that I designed. I then want to formulate an algorithm to calculate the 1th value below it (and I'm not really sure the terminology for this so ...
1
vote
1answer
57 views

How would I computationally find a generating functions coefficient?

More specifically $a_n=(1,5,10,25,100,500,1000,2000,10000)$ $G(x)=\Pi_{n=0}^8 \sum_{i=0}^{\infty}x^{a_ni}$ So when $a_n=1$ the series = $1+x+x^2+x^3+...$ $a_n=5, 1+x^5+x^{10}+x^{15}+...$ $a_n=10, ...
0
votes
0answers
72 views

Maximum Network Flow To find the number of people

There are four groups of people who want to be carried to a destination. If we have three vehicle to carry the following number of people: Veh 1, five; Veh 2, four; Veh 3, four. ...
1
vote
2answers
60 views

How does my professor come up with the recursive case in this algorithm analysis?

My professor gave us the following explanation for the recursive algorithm for finding the permutations of a set of numbers: When he has (T(m+1), n-1)) where does that come from? Why is it m+1 ...
0
votes
1answer
229 views

optimizing prime number algorithm

I am doing a function to return a list of prime number up to "n", one what to optimize the algorithm is the following: "The next most obvious improvement would probably be limiting the testing ...
3
votes
0answers
49 views

Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
0
votes
2answers
890 views

Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent

Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to ...
0
votes
0answers
51 views

Operation count for Tridiagonal System

What is the operation count for solving the tridiagonal system $Ax=b$. I would guess it is $O(n^2)$ because all we are doing is making one sub-diagonal zero all the way across giving us $t(n)=n$ and ...
0
votes
2answers
236 views

Science Fair Project - Square roots

For a school science fair project, I need four or five square root algorithms to use. Googling gives sites like http://en.wikipedia.org/wiki/Methods_of_computing_square_roots with so many methods that ...
1
vote
3answers
58 views

Recurrence Tree for Recurrence Inequality

I'm used to solving recurrences that are in the form of T(n) = ... However, when analyzing an algorithm, its recurrence form is: $$ T(n) < \sqrt{n} \cdot T(\sqrt{n}) + n $$ How do I solve a ...
2
votes
1answer
141 views

Matrix Chain Multiplication Dynamic Equation

I am thinking about the derivation of the following dynamic equation: $$F(n_1,...,n_{k+1};k)=\min_{1<i<k+1}\{n_{i-1}n_i n_{i+1}+F(n_1,...,n_{i-1},n_{i+1},...,n_{k+1};k-1)\}, k=1,...,h$$ Let me ...
2
votes
0answers
331 views

How to reverse this bitwise AND-XOR encoding algorithm?

I have been given an "encoding" algorithm that does bitwise XOR and bitwise AND. Originally it's a C code that operates on integers with bit-shifts, but I have translated it into a simpler pseudocode ...
0
votes
1answer
41 views

Transforming rectangle to disk-shape

The problem is formed when I am doing image processing: transforming the left image to the right. I haven't found any proper method to transform the image directly, so an algorithm or function is ...
0
votes
0answers
105 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
1
vote
1answer
156 views

Given two overlapping datasets (think Venn Diagram), what is the point/plane called that separates the middle from either side?

Or, if you prefer a typed out version: Given the following two datasets: [Category A]: 1,3,4,7,8,9,13 ... 28,30 [Category B]: 29,32,33,37 ... 61,62,63 Plotted ...
2
votes
1answer
416 views

Algorithms to approximate trigonometric functions to n decimal digits

I'm currently writing a big number calculator program in C#.Net. What are some reasonably fast and easily implemented algorithms to compute trigonometric functions to $n$ correct decimal digits (where ...
5
votes
1answer
281 views

solve $\ln(n!) = \Theta(n\ln(n))$ without stirling approximation

My homework was proving this equation which is simple using Stirling approximation. I was wondering if there is any other method to prove it - whithout Stirling - I can prove $\ln(n!) = O(n\ln(n))$ ...
1
vote
0answers
56 views

Algorithm for finding power

I has been searching for a high precision library in PHP to do calculations like $$232323232323^{121212.2232323232}$$ etc (ie, with very large numbers, including decimals), but failed to get any. ...
4
votes
1answer
170 views

Fast bijective $\mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$

I am looking for a fast pairing function which maps two integers (cartesian coordinates) to a single unique integer. In other words, $$ \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}, $$ thats ...
1
vote
2answers
40 views

Show that the summation is bounded by O(1)

How could I show that the following summation is O(1)? \begin{equation} \sum\limits_{i=1}^{n} \frac{i^2}{2^i}\ \end{equation} I know that the idea is to find a geometric series approaching a ...
0
votes
3answers
466 views

If five teams are playing in a round robin tournament, is it possible for all five teams to tie for the first place?

If five teams are playing in a round robin tournament, is it possible for all five teams to tie for the first place? What if six teams are playing?
0
votes
1answer
36 views

Clockwise vs counterclockwise. What's with the DFT?

I had an algorithms tutorial today and I realized that many of my answers were incorrect, but any time I took the DFT and then DFT^-1 to find some real roots of a polynomial, I had the correct answer. ...