New answers tagged

3 votes
Accepted

Prove maximum score is achieved by being greedy

If $(t_0, t_1, …, t_{n-1})$ is the sequence of tokens played by your greedy solution, you can show by induction that for any $k\in \{0, …, n\}$, the sequence $(t_0, …, t_{k-1})$ is the sequence of $k$ ...
Nathaniel's user avatar
  • 15.5k
0 votes

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

Proof by picture. There is an straightforward bijection between the (binary) numbers $1$ to $\underbrace{1\dots 1}_k$ and the available node positions in a binary tree of $k$ levels (where we count te ...
Hendrik Jan's user avatar
  • 30.6k
0 votes

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

This is a classic textbook problem. You can find plenty of solutions online. A direct derivation can be made to prove the statement as well. For that, we would argue about two things: First, we argue ...
codeR's user avatar
  • 565
1 vote

Prove that in a complete binary tree with $L$ levels, the total number of nodes $N \leq 2^{(L+1)} - 1$

You should really show what you tried before asking, this is not a site for answering homework questions. Still, some hints. You can use the principle of mathematical induction. Start with your base ...
codeing_monkey's user avatar
3 votes
Accepted

can we computably list every primitive recursive function?

I'll build on Pål's answer to be a bit more explicit about how we can code PR functions using those operations. First of all, note that we can code any finite sequence of (positive) numbers into a ...
Steven Stadnicki's user avatar
6 votes

can we computably list every primitive recursive function?

The primitive recursive functions can be defined in terms of the following five axioms: Constant function: $C_n^k$ is a $k$-ary function that always returns $n$ Successor function: $S$ is a 1-ary ...
Pål GD's user avatar
  • 16.1k
0 votes

Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω

I would suggest checking exact definitions of asymptotic notations, to say informally: $\Omega(f(n))$ is set of functions that are lower bounded by $f(n)$, while $O(f(n))$ are set of functions upper ...
math boy's user avatar
  • 353
0 votes

Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST

There is a proof on the internet without distinct edge weights assumption found in this document from flashmt's comment in codeforces. It is the equivalent of the proof provided, only written more ...
Kenneth Kho's user avatar

Top 50 recent answers are included