0
votes
3answers
25 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 ...
1
vote
1answer
60 views

How to prove a very basic algorithm by induction

I just studied proofs by induction on a math book here and everything is neat and funny: the general strategy is to assume the LHS to be true, and use it to prove the RHS (for the inductive step). Now ...
0
votes
1answer
55 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). ...
0
votes
0answers
9 views

Determining the minimal number of axis to test against in the SAT (Separating Axis Theorem)

Most implementations of the SAT algorithm I've seen involve testing each axis in either shape being tested against for collisions. But I recently implemented the SAT algorithm in python and noticed ...
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 ...
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 ...
1
vote
1answer
27 views

Showing that all regular languages are closed under reversal

I'm trying to show that $L^{reverse} = \{w^{reverse}:w \in L\}$ is a regular language. The first argument I can come up with is simply: if we have an NFA for $L$, then an NFA for $L^{reverse}$ can be ...
1
vote
0answers
48 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
1answer
49 views

Proof with $\Theta$

I am having a hard time proving the following statement: Suppose that the functions $f_1, f_2, g_1, g_2 : \mathbb{N} \rightarrow \mathbb{R}^{\ge 0}\ are \ such \ that \ f_1 \in \Theta (g_1) \ and ...
1
vote
1answer
58 views

Do this algorithm terminates?

Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in ...
0
votes
1answer
55 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 ...
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
70 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
2answers
410 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}$?
0
votes
0answers
106 views

In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?

Take the following insertion sort algorithm: I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
0
votes
1answer
158 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
144 views

Prove or counterexample: $f(cn) \in \theta (f(n))$

Prove or provide a counterexample: For every positive constant c, and every function f from nonnegative ints into nonnegative reals, $$f(cn) \in \theta (f(n))$$. At first, I thought this was obvious, ...
1
vote
1answer
123 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 ...
0
votes
0answers
236 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 ...
2
votes
2answers
265 views

find the largest integer less than a number

I'm trying to figure out this problem for few hours now. please help. Define $$\text{PCOM}(a,b,c) := \{ax + by + cz : x, y, z ≥ 0\}.$$ Given integers $t > c > b > a > 1,$ I need help ...
1
vote
2answers
255 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
1answer
51 views

Proof of algorithm refinement

I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k. I then had to increase the time efficiency of ...
0
votes
1answer
86 views

Big-O Big theta Big omega papers

I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...
0
votes
1answer
1k views

Proving Big-$\Theta$ if and only if Big-$O$ and Big-$\Omega$

Given the definitions of Big-$O$ and Big-$\Omega$, I'd like to prove that $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. Here's what I've come up with, but I'm not ...
2
votes
1answer
193 views

Growth of $ n^{\ln n}$ versus polynomial, exponential, and logarithmic forms

I'm attempting to clarify the proofs of these forms. Starting with $n^{ln\,n}$ I want to compare with polynomial, exponential, and logarithmic forms. I can understand just by looking at them which ...
1
vote
1answer
405 views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...
1
vote
1answer
256 views

Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, ...
1
vote
3answers
561 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
142 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 ...
1
vote
0answers
145 views

Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

My question is at the bottom. (Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition) let $w$ be the weight vector of the neural network and $E$ the error ...
0
votes
1answer
110 views

Prove that when computing gcd(m, n), n will always be smaller, Except for possibly on the first computation

From Donald Knuth's The Art of Computer Programming the following problem is given. Prove that $m$ is always greater than $n$ at the begining of step E1 (see below), except possibly the first time ...
0
votes
2answers
2k views

Proof of correctness of binary search

I have just written a pseudo-code (actually in Python) of a binary search algorithm. ...