# Tagged Questions

25 views

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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
674 views

...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...