mikedll

Problem 3-1

In all cases we examine only the term $a_d n^d$, since it dominates the subject polynomial's running time. All the lower order terms would do is increase the $n_0$ needed to make the bounds hold true.

a.

We are seeking some constant $c$ such that $0 \le a_d n^d \le c n^k$.

mikedll

Exercise 3.3-6

Let $n$ be some input to each of the functions we're evaluating. Presume to calculate $i = \lg^{*} n$. Let $n_i$ be the number less than 1 that n was reduced to by the iterative logarithm function. Let $g(n) = 2^n$. Then $g^{(i)} n_i = n$.

Consider:

$$ \begin{align}

mikedll

There is a part in CLRS chapter 3 where they have $d^k$ and they convert this to an exponential expression with a different base. The way to see this is as follows:

$$ \begin{align} d^k &= C^{\log_{c} {d^k}} \\ &= C^{k \log_c d} \\ &= C^{k / log_d c} \end{align} $$

mikedll

Exercise 3.3-5

a. Restrict the domain to powers of 2, so $n = 2^{c_1}$ where $c_1$ is some integer greater than or equal to 1. Our restriction of the domain of $n$ to powers of 2 still permits a conclusive analysis of $\lceil \lg n \rceil !$ as to how it compares to $c n^k$ as $n$ increases.

We have $\lceil \lg n \rceil ! = \lceil \lg 2^{c_1} \rceil ! = c_1 !$ (by 3.1). By 3.29, this is:

$$ \begin{align}

mikedll

class Table
  def initialize(n, firstValue)
    @m = {}
    (0...n).each do |i|
      @m[i] = {}
      (0...n).each do |j|
        @m[i][j] = firstValue
      end
    end
  end

mikedll

#!/usr/bin/ruby

#require 'test/unit'
require 'test/unit/testcase'

class TestBST < Test::Unit::TestCase

  # ... tests omitted...

  def test_no_crashes

mikedll

using System;
class EnemyTowers
{
    const int INF = int.MaxValue;
    public int sim( int s, int h, int a, int t)
    {
        int ret = 0;
        int p = h;

        while( s > 0 && t > 0 ) {

mikedll

// requires prototype for some of its synctactic sugar

var Undiscovered = 0;
var Discovered = 1;
var Processed = 2;
var time = 0;
var scc_count = 0;
var states = {};
var et = {};
var low = {};

mikedll

require 'test/unit'

class Nisoku
  def theMax(input)
    max_so_far = -1

    input = input.map { |e| e.to_f }.sort

    s = 0
    while s <= input.length

mikedll

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TopCoderCSharp
{
  class PeopleYouMayKnow
  {
    const int MaxFriendDepth = 4;