0
votes
3answers
24 views

A property regarding intervals

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $ [a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that: $$ a_1 + a_2 + ... + a_n \leq T \leq ...
0
votes
1answer
18 views

Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
0
votes
2answers
71 views

Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges

Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph. The algorithm I have ...
0
votes
2answers
46 views

Using Euclid's Algorithm prove..

Using Euclid's Algorithm prove that the fraction $\frac{24n+5}{18n+4}$ is in lowest terms. Is this solution going to be correct as a proof? Thanks for help!
1
vote
1answer
42 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
1answer
54 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
10
votes
4answers
393 views

Application of computers in higher mathematics

Currently the main application of computers in mathematics seems to be to compute things, i.e. to solve equations, evaluate integrals, etc. It is at all possible to delegate the thinking of a ...
0
votes
0answers
15 views

Writing a proof that a certain algorithm generates the correct transition matrix for a quantum walk?

Regarding quantum walks, I have a transition matrix $M$ and a particle vector $P$ and I have determined that the elements of $M$ have to be positioned in a certain way so that the position of the ...
0
votes
2answers
161 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
1
vote
1answer
29 views

Multiplication cannot be obtained from zero, successor, and identity by composition without recursion

The task is to show that multiplication cannot be obtained by zero, successor, or identity functions by composition without using recursion at least twice. I'm primarily confused because it doesn't ...
0
votes
1answer
93 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...
0
votes
2answers
89 views

Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
0
votes
1answer
50 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
3
votes
1answer
382 views

Proving that a greedy algorithm yields the optimal solution for a problem

I'm a college computer science student, working on a project. In my project i have an optimization problem, which i belive is optimally solveable with a greedy algorithm approach. In every case i have ...
0
votes
1answer
61 views

Proof for hamiltonian cycle in grids having even no. of nodes

How can I go about proving that an undirected graph having even no. of nodes (at least one of the rows or columns are even - excluding line graphs of course) have a hamiltonian cycle? I have managed ...
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
0answers
40 views

In this proof, why did they choose the value n/2 for the assumption? And what bearing did that have on the rest of the proof?

For the assumption step, why did they assume it holds true for n/2 specifically? And when they prove that it holds true for n, how do the steps they do there have anything to do with the n/2 ...
0
votes
2answers
69 views

How does my professor go from this logarithm to the next?

In the above picture, how does he go from the third-last line to the second last?
0
votes
2answers
43 views

How does my professor go from this exponential equation to a logarithmic one?

How does the "therefore" portion work? How does that exponential equation come to equal n(lgn + 1)?
0
votes
1answer
80 views

Help me this proof! Related to RSA public key cryptosystem

Basically it is similar to the RSA algorithm. Let p and q be distince primes and let e and d be the integers satisfying $de≡1$ (mod (p-1)(q-1)). Suppose further that c is an integer with ...
0
votes
2answers
343 views

How do I prove that a function grows faster than another? [closed]

I need to prove that one function, say $n$ grows faster than say, $\sqrt{n}$?
2
votes
1answer
242 views
0
votes
1answer
130 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
0
votes
1answer
99 views

How does one prove this equation?

How does one prove the following equation , I am getting confused about this, I can't seem to find any proving technique, I tried plugging in the Stirling's formula for factorials but to no avail - ...
0
votes
1answer
86 views

Recursive fibonacci algorithm correctnes? [proof by induction]

im studying for the computer science GRE, as an exercise i need to provide a recursive fibonacci algorithm and show its correctness by mathematical induction. here is my recursive version of ...
1
vote
0answers
61 views

How can I prove this problem about ordering of differences of numbers?

This is the problem: Given several real numbers (arbitrary amount and values) : $A_1,A_2 \ldots A_n$ Find the combination which yields the maximum value for the following formula: $y = |A_x -A_y| + ...
2
votes
2answers
359 views

Dijkstra's Shortest-Path Algorithm

I'm presented with the following algorithm: Dijkstra's Shortest-Path Algorithm This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted ...
1
vote
1answer
121 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 ...
1
vote
1answer
85 views

Orange Juice, Milk, or Beer

Suppose that we have $n$ dollars and that each day we buy either orange juice for a dollar, milk for two dollars, or beer for two dollars. If $R_n$ is the number of ways of spending all the money, ...
0
votes
3answers
163 views

(CHECK) $n$-bit Strings Containing a Pattern

$$\text{$\bf{PLEASE~~~CHECK~~~AUTHOR'S~~~ANSWER}$}$$ If $S_n$ denotes the number of $n$-bit strings that do not contain the pattern $00$, then what is the underlying recurrence relation and ...
0
votes
1answer
111 views

Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number ...
0
votes
0answers
224 views

Optimality proof for greedy algorithm

Let $\mathcal{A} = \{a_1, \ldots, a_N\}$ be a set of actions that can be performed on a system $S$. Each action $a_i$, if performed, produces a gain $g_{a_i}(S)$. Moreover, the actions in ...
1
vote
2answers
248 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 ...
1
vote
3answers
170 views

Help with Big O and Big Omega problem.

this is a homework problem: 1) $$ \text{Let }f(n) = n^2+5000 \text{ and } g(n) = 5(n^2) + 100.\text{ Prove formally that }f(n) = \theta (g(n)) $$ My attempt: a)Prove f(n) is $ O(g(n)) $: When $ n ...
0
votes
1answer
133 views

Prove problem reduces to 0-1 knapsack problem

http://community.topcoder.com/stat?c=problem_statement&pm=12329 I was practicing on TopCoder and found this problem. I solved it by noticing that it looks a little like the 0-1 knapsack, but I do ...
1
vote
2answers
158 views

Prove that $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$ [closed]

Prove that : $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$
1
vote
0answers
73 views

Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
2answers
63 views

Show that: $t_{n-1}+t_n=n^2$

How to can prove that : $$ t_{n-1}+t_n=n^2.$$ where $t_n$ is number of points with integers coordinates in a square isosceles triangle of side $n$: http://i45.tinypic.com/ndse9.jpg
3
votes
0answers
598 views

proving a greedy algorithm with a exchange argument

I have the following problem: We have a set of tasks that requires some preprocessing time. When the job is preprocessed, the job can be executed on a parallel thread that also requires some time. ...
2
votes
3answers
331 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
1
vote
3answers
505 views

Proving a factorial is not a certain complexity

I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that? Problem: Prove ...
1
vote
2answers
1k views

Calculating Average Case Complexity

I am trying to find the average case complexity of a sequential search. I know that the value is calculated as follows: Probability of the last element is $\frac{1}{2}$ Probability of the next to ...
0
votes
1answer
1k views

how to prove optimality of this greedy algo

I need some suggestions on how to prove the below greedy algorithm is optimal. Problem: There are $n$ fires on a road. Each fire $i$ is given as an interval where it starts and ends $[s(i), f(i)]$. ...
0
votes
1answer
91 views

Does a Minimum Spanning Tree entail minimum cost between 2 vertices?

In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks
0
votes
1answer
140 views

how to prove this scheduling problem

I need some hints for proving the correctness/optimality of the below homework problem. It is a task-schedulding problem with deadlines and penalties. There are n tasks, each of which has a deadline ...
4
votes
1answer
410 views

Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
3
votes
2answers
1k views

How do I write this proof more formally?

So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree. My Proof: If the graph has unique edge weights, we can ...