0
votes
0answers
6 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
11 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
28 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
22 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
1answer
45 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
43 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
56 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
39 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
41 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
267 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
71 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
106 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
135 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
102 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
217 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
194 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
216 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
50 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
85 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
850 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
182 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
298 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
235 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
421 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
885 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
133 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
127 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
99 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. ...