Programming I, Winter 2017-8
Practice Exam - Solutions

1. Write a function `words` that determines the number of words in a string. For this problem, words are sequences of non-space characters separated by one or more spaces. For example, ```words(" big    yellow   hat")``` = 3.

```// iterative solution

function words(s: string): integer;
var
i, n: integer;
begin
if s = '' then exit(0);
if s[1] = ' ' then n := 0 else n := 1;

for i := 1 to length(s) - 1 do
if (s[i] = ' ') and (s[i + 1] <> ' ') then
n := n + 1;
words := n;
end;

// recursive solution

function words(s: string): integer;
var
w: integer;

begin
if length(s) = 1 then
if s[1] = ' ' then exit(0) else exit(1);

w := words(s[2 .. length(s)]);
if (s[1] <> ' ') and (s[2] = ' ')
then exit(w + 1) else exit(w);
end;
```

2. Write a function `ones` that takes an integer `i` and returns true iff there are any consecutive 1s in the binary representation of `i`. For example, `ones(5)` = false since 5 = 1012, and `ones`(6) = true since 6 = 1102.

```// iterative solution

function ones(i: integer): boolean;
begin
while i > 0 do
begin
if i mod 4 = 3 then exit(true);
i := i div 2;
end;
exit(false);
end;

// recursive solution

function ones(i: integer): boolean;
begin
if i = 0 then exit(false);
exit((i mod 4 = 3) or ones(i div 2));
end;
```

3. Write a function `most` that takes two arguments: (1) an array of integers and (2) a function f from integers to booleans. `most` should return true if the function f returns true for most (at least half) of the elements in the array. For example, if `a` and `odd` are defined as

```var a: array[1..5] of integer = (3, 4, 5, 6, 7)

function odd(i: integer): boolean;
begin
exit(i mod 2 = 1);
end;```

then `most(a, @odd)` = true.

```// iterative solution

type
cond = function(i: integer): boolean;

function most(a: array of integer; c: cond): boolean;
var
count: integer = 0;
i: integer;
begin
for i in a do
if c(i) then count := count + 1;
exit(count * 2 >= length(a));
end;

// recursive solution

type
cond = function(i: integer): boolean;

function count(a: array of integer; c: cond): integer;
var
i: integer;
begin
if c(a[0]) then i := 1 else i := 0;

if length(a) = 1 then exit(i)
else exit(i + count(a[1 .. high(a)], c));
end;

function most(a: array of integer; c: cond): boolean;
begin
exit(count(a, c) * 2 >= length(a));
end;```

4. Write a function `sub` that takes two linked lists of integers `s` and `t` and returns true iff any subsequence of nodes in s is identical to t. For example, if `s` = 3 → 4 → 2 → 7 → 8 → `nil` and `t` = 2 → 7 → `nil` then ```sub(s, t)``` = true.

```// iterative solution

type
node = record
i: integer;
next: ^node;
end;
pnode = ^node;

function startsWith(p, q: pnode): boolean;
begin
while q <> nil do
begin
if (p = nil) or (p^.i <> q^.i) then
exit(false);
p := p^.next;
q := q^.next;
end;
exit(true);
end;

function sub(p, q: pnode): boolean;
begin
while true do
begin
if startsWith(p, q) then
exit(true);
if p = nil then exit(false);
p := p^.next;
end;
end;

// recursive solution

type
node = record
i: integer;
next: ^node;
end;
pnode = ^node;

function startsWith(p: pnode; q: pnode): boolean;
begin
if q = nil then exit(true);
exit((p <> nil) and (p^.i = q^.i) and startsWith(p^.next, q^.next));
end;

function sub(p: pnode; q: pnode): boolean;
begin
exit(startsWith(p, q) or ((p <> nil) and sub(p^.next, q)));
end;```

5. The height of a node in a binary tree is its distance in edges from the root node. The root node has height 0, its children have height 1, and so on. Write a function that determines the sum of the heights of all nodes in a binary tree.

```type
treeNode = record
i: integer;
left, right: ^treeNode;
end;
pTreeNode = ^treeNode;

function height1(t: pTreeNode; h: integer): integer;
begin
if t = nil then exit(0);
exit(h + height1(t^.left, h + 1) + height1(t^.right, h + 1));
end;

function height(t: pTreeNode): integer;
begin
exit(height1(t, 0));
end;```