# Tagged Questions

29 views

### How many majority elements can there be in a sequence?

You are given a sequence $S$ of $n$ numbers. An element $x$ in $S$ is called a majority element if it occurs more than $n$/2 times in $S$. This question asks you to describe two algorithms that decide ...
88 views

### Which greedy algorithm is optimal?

The following question is a homework problem for a course called Design and Analysis of Algorithms. In the problem, there is a minimized cost function and two greedy algorithms. I am asked to show ...
19 views

### determine the transitive closure of a relation using warshall's algorithm. [closed]

Let A={a,b,c.d} and R={(a,a), (b,c), (c,a), (c,c),(d,a)} determine the transitive closure of R, using warshall's algorithm.
52 views

### Assignment Problem

Given $N$ jobs and $M$ tasks, assign $K$ jobs to $K$ tasks where $K\leq min(M,N)$ so that the max_cost out of $K$ jobs is minimized. Can you help me with algorithm for the problem. I have tried brute ...
31 views

### Time efficiency of brute force algorithm as a function of number of bits?

This is homework help so advising how to solve such a problem is appreciated. The question reads as follows: What is the time efficiency of the brute-force algorithm for computing $a^n$ as a ...
30 views

### Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$

I want to prove the following that based on maximum rule of functions: $$\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$$ the base prove is for each 2 functions ...
19 views

### Subtracting Algorithm Efficiency?

I've completely understood Big-o and big Omega notation; how to show functions exist in them and what not, however one problem to subtract I do not know where to go. The problem as follows; ...
39 views

### Finding maximum differences in an array of real numbers .

This is an algorithm design question which often appears in exams in a course that I take in the university . Suppose I have an array $A\in\mathbb{R}$ of size $n$ . I am required to find the ...
30 views

### Getting some negative to positive interval from a positive random number generator?

Imagine I have a random generator. random(m, n) returns a random integer between 'm' and 'n' but both $m$ and $n$ needs to be positive integers. Is there any way I could get it to work if I was able ...
28 views

### A set is partitioned into $k$ non-empty sets, and the difference between elements of each subset is given, reconstruct each subset

We have a set $A = \{1, 2, 3, \dots, n\}$. This set is partitioned into $k$ non-empty subsets: $$A_1 = \{a_1, a_2, \dots, a_{m_1}\}$$ $$A_2 = \{a_{m_1 + 1}, a_{{m_1} + 2}, \dots, a_{m_2}\}$$ $$.$$ ...
52 views

### ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
51 views

### How to arrange $n$ pairs of numbers so that this expression is minimized

Consider $n$ pairs of positive integers, $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. Make a permutation $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ of these pairs, such that for all $x_i, y_i$, a ...
123 views

### Create a number by multi by $2$ and divide by $3$ (integer part)

How can I create a given postitive integer $N$ by multi by $2$ and divide by $3$ (integer part) ? (Write a computer program is allowed) For example: $$100 = 2*2*2*2*2*2*2*2*2*2*2/3/3/3/3*2*2$$ (The ...
107 views

### Horner Polynomial Evaluation: counting addition operations

We first note how the polynomial in Exercise 5 can be written in the nested multiplication method: ...
91 views

### Making sense of word problem

Suppose you begin with a pile of $n$ stones and split this pile into $n$ piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile ...
54 views

### Maximizing an algebraic expression using brackets

It's a riddle of sorts: given a list of numbers $\alpha_1 \dots \alpha_n$ and operators $o_1 \dots o_{n-1}$ which can be only $\times\, \mbox{or}\, +$ if the above is a specific algebraic expression ...
137 views

### Square root algorithm in modulo $n = pq$

I've been stuck in this problem quite a bit. I have to find an efficient algorithm wich, given: $$p = 4k+3\\ q = 4m+3\\ p,q \hspace{2mm} \text{odd primes}\\ a\in \mathbb{N}$$ verifies if there ...
22 views

### How to I change these numbers into a score out of 100

I have the following numbers in an excel file and I am trying to work out how to transform these into a score from 1 to 100. The bottom number (0.1) should be a 1 and the top number (61.2) should be ...
57 views

### Backward stable algorithm

Assume we have fixed unitary matrices $Q_1, \dots, Q_k \in \mathbb{C}^{m,m}$ and a matrix $A \in \mathbb{C}^{m,n}$ which can be perturbed. How can we proof that the algorithm on computing the product ...
68 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 ...
48 views

### Let $S, T$ be sets, such that $|S|=n$ and $|T|=m$. How many distinct functions from $S$ to $T$ is it possible to define? Please justify your answer

Let $S, T$ be sets, such that $|S|=n$ and $|T|=m$. How many distinct functions from $S$ to $T$ is it possible to define? Please justify your answer Thanks for any help. Even if you don't have ...
300 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 ...
92 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 ...
37 views

### Show that the summation is bounded by O(1)

How could I show that the following summation is O(1)? $$\sum\limits_{i=1}^{n} \frac{i^2}{2^i}\$$ I know that the idea is to find a geometric series approaching a ...
99 views

### Solving recurrence using Master Theorem: Change of variables

Solve the recurrence using the Master Theorem State case and constant values used. $$T(n)=3T(\sqrt[3]{n})+log^2n$$ The $\sqrt n$ has a 3.(The number is a little small) I need to solve this using ...
124 views

### Prove that Big O (lg n) is a subset of Big O(sqrt(n))…

Prove that Big O (lg n) is a subset of Big O(sqrt(n)) and exists an element x in set Big O(sqrt(n)) that is not in Big O(lg n). This is a home work question and I have no clue where to start. Do I use ...
57 views

### How to count this in a faster way?

It's a homework problem, it took me 20mins to do it, and what's even worse is that I didn't get the correct exact answer.... (we are only asked to give an approximate number, I didn't lose any point ...
184 views

### Let G = (V, E) be an undirected graph in which the degree of each vertex is a multiple of 10 or of 15. Show that |E| is a multiple of 5.

Let G = (V, E) be an undirected graph in which the degree of each vertex is a multiple of 10 or of 15. Show that |E| is a multiple of 5. Not really sure how to even think this one out. I know there ...
190 views

### Prove that the Euclidean algorithm for gcd works with polynomials

Given the algorithm $E$: ...
73 views

### a game of coloring edges of graph

I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the ...
42 views

### Calculating modular inverses with limited multiplication

Question Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications ...
114 views

### Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
65 views

### How to solve this system with conjugate gradient algorithm

CG Algorithm https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!386&v=3 System of equations, the question and the example https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!387&v=3 ...
97 views

### Prove correctness for this lcm iterative program

Studying for finals, trying to solve this problem: Given positive integers $n$ and $m$, we say that $m$ is a multiple of $n$ iff there is some $k \in N$ such that $m = kn$. For positive ...
569 views

### What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no ...
64 views

### Is polynomial time reduction commutative?

True or False: $D_1$ and $D_2$ are decision problems, and $D_1 \leq_p D_2$, then cannot be that $D_2 \leq_p D_1$ I think it is false because we already have a mapping for all yes instance from $D_1$ ...
98 views

### The basis of a subgroup $H \subset \mathbb Z^4$

Dear fellow mathstack exchangers, There is a question in my Abstract Algebra syllabus I have trouble with solving, the main problem is is that there is no clear description of the algorithm I need. ...
60 views

### Finding in a string S if is possible to create a set with perfect cubes or perfect squares with elements of S.

You have a sequence $S[1...n]$ with $n$ digits(0 to 9) and you wanna know if its possible break then in perfect square or perfect cube. For example, if $S = 1252714481644$, then the answer is $YES$ ...
53 views

### Greedy algorithm for Nephite coinage system

I have a question about problem 2 of this homework set and its solution. The task is to show whether the greedy algorithm works or not for the Nephite coinage system from the Book of Mormon (with ...
181 views

### Maximum product consecutive subsequence

I need find the maximum product of a consecutive subsequence in sequence of $n$ integers. Example: In: $3$, $1$, $-2$, $4$. Out: $4$. In $2$, $5$, $-1$, $-2$, $-4$. Out: $20$. $(2*5*(-1)*(-2))$. ...
38 views

### Does this algorithm terminate in finite time?

I am trying to determine whether the following algorithm terminates: ...
98 views

### count the number of connected induced subgraphs in a graph with bounded degree

Let $G=(V,E)$ be a graph where the maximum degree of a vertex is 4. I've been asked to find an efficient algorithm for counting how many connected induced subgraphs are in $G$. What I have so far is a ...
34 views

### Divide an array in 3 subarrays satisfying some properties.

Given an array $S[p\dots r]$ and a pivot rearrange the elements such that the returned array follow this properties. Algorithm sould be $O(n)$ if $p \le k \le q_1$, then $S[k] < \mathrm{piv}$; if ...
110 views

### Error in “proof” of $n^2 \in O(n)$.

I need some help. I have homework: I need to disprove that $f(n^2)$ belongs to $O(n)$. Why in question $n^2 = (n-1)^2+2n-1$? It must be $(n-1)^2-2n+1$. Am I right?
61 views

### Solving recurrenc using recurrence tree method.

I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$. I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and ...
70 views

### How would I create a birthday attack? (Hash Functions)

I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
207 views

### Prove that a greedy algorithm selects the maximum number of programs

This is a homework problem. Intuitively, I know it to be true, because the largest group of programs (say, $j$ programs) must be composed of the smallest $j$ programs. But how to go about formally ...
134 views

### Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where e is the natural logarithm}$$ To solve this and find a Θ bound, i tried the following: I ...
The recurrence relation $T(n)=4T\left(\frac{n}{2}\right)+n^2$ describes the running time of an algorithm $A$. Competing algorithm $A'$ has the running time of $T'=aT'\left(\frac{n}{4}\right)+n^2$. ...