CSCI 3333.3 Data Structures
Spring 2013
Suggested Solution to Homework #5

Exercises:

(1) For example:

Algorithm NumberOnes(N: integer)
Input: N: non-negative integer
Output: Number of 1's in the binary implementation of N

if (N <= 1)
return N;
else
return (N % 2) + NumberOnes(N div 2);
end if;

(2) Assume that N = 2^k.

(a) lgN +1 for N>= 1.
(b) 2N-1 for N>= 1.
(e) 4N²(1-(3/4)^(k+1))

(3)

(a)
potfix: abc+d*ef-/g/+
pretfix: +a//*+bcd-efg

(b)
postfix: cd*ea+b-*fg-h-/i-
prefix: -/**cd-+eab--fghi

Program:

(1) For example, the algorithm:

Algorithm NumberOnes(N: integer)
Input: N: non-negative integer
Output: Number of 1's in the binary implementation of N

if (N <= 1)
    return N;
else
    return (N % 2) + NumberOnes(N div 2);
end if;

Program (1):

Algorithm Lucas(N: integer)
Input: an integer
Output: the Nth Lucas number

if (N == 0) return 2;
if (N == 1) return 1;
if (N < 0) return (-1) ^ (-N) * Lucas (-N);
return LucasHelper(N, 2, 1, 2);

Algorithm LucasHelper(N, i, Lim1, Lim2);
Input: N: an integer > 1.
       i: Lucas(i) to be computed.
       Lim1: Lucas(i-1)
       Lim2: Lucas(i-2)
Output: Lucas(N)

if N == i
    return Lim1 + Lim2;
else
    return LucasHelper(N, i+1, Lim1+Lim2, Lim1);
end if;
 

A suggested program in Perl:

use strict;
# 
#    lucas.pl
#
#    Print the lucas number of an integer n
#    Usage: lucas.pl n
#     

#   Get num
@ARGV >= 1 || die "usage: lucas.pl n";
my $num = $ARGV[0];

print "Lucas(", $num, "): ", lucas($num), ".\n";
exit 0;

sub lucas {
    my $num = $_[0];
    if ($num == 0) { return 2; }
    if ($num == 1) { return 1; }
    if ($num < 0)  { return ((-1) ** (-$num)) * lucas(-$num); }
    return lucasHelper($num, 2, 1, 2);
}

sub lucasHelper {
    my ($num, $i, $lim1, $lim2) = @_;
    if ($num == $i) { return $lim1 + $lim2; }
    return lucasHelper($num, $i+1, $lim1 + $lim2, $lim1);
}