CS100M Spring 2001 Prelim T2: Questions and Solutions March 28 Q1. Use box scope diagrams to trace $a(1,1)$. function v = a(m, n) if m == 0 v = n + 1; elseif n == 0 v = a(m-1, 1); else v = a(m-1,a(m, n-1)); end Solution (arrows and parameters drawn for clarity -- not required): /-----------------------------V Command Window a(1,1) ---> a(1,0) ---> a(0,1) a(0,2) +---------+ +---------+ +---------+ +---------+ +---------+ | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | |ans| 3 | | | m | 1 | | | m | 1 | | | m | 0 | | | m | 0 | | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | +---------+ | +---+ | | +---+ | | +---+ | | +---+ | | n | 1 | | | n | 0 | | | n | 1 | | | n | 2 | | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | v | 3 | | | v | 2 | | | v | 2 | | | v | 3 | | | +---+ | | +---+ | | +---+ | | +---+ | +---------+ +---------+ +---------+ +---------+ In case you find it helpful, intermediate steps are shown below ($Command Window$ is abbreviated as $cmd$ and activation records that are "killed" are not shown). cmd a(1,1) | cmd a(1,1) | cmd a(1,1) a(1,0) +----+ +----+ | +----+ +---------+ | +----+ +---------+ +----+ | | | | | | | | +---+ | | | | | +---+ | | | +----+ +----+ | +----+ | m | 1 | | | +----+ | m | 1 | | +----+ | | +---+ | | | +---+ | | | +---+ | | | +---+ | | | n | 1 | | | | n | 1 | | | | +---+ | | | +---+ | | +---------+ | +---------+ _______________|______________________|__________________________________ | cmd a(1,1) a(1,0) | cmd a(1,1) a(1,0) a(0,1) +----+ +---------+ +---------+ | +----+ +---------+ +---------+ +----+ | | | +---+ | | +---+ | | | | | +---+ | | +---+ | | | +----+ | m | 1 | | | m | 1 | | | +----+ | m | 1 | | | m | 1 | | +----+ | +---+ | | +---+ | | | +---+ | | +---+ | | +---+ | | +---+ | | | +---+ | | +---+ | | n | 1 | | | n | 0 | | | | n | 1 | | | n | 0 | | | +---+ | | +---+ | | | +---+ | | +---+ | +---------+ +---------+ | +---------+ +---------+ ________________________________|________________________________________ cmd a(1,1) a(1,0) a(0,1) +----+ +---------+ +---------+ +---------+ | | | +---+ | | +---+ | | +---+ | +----+ | m | 1 | | | m | 1 | | | m | 0 | | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | n | 1 | | | n | 0 | | | n | 1 | | | +---+ | | +---+ | | +---+ | +---------+ +---------+ +---------+ _________________________________________________________________________ cmd a(1,1) a(1,0) a(0,1) +----+ +---------+ +---------+ +---------+ | | | +---+ | | +---+ | | +---+ | +----+ | m | 1 | | | m | 1 | | | m | 0 | | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | +---+ | | n | 1 | | | n | 0 | | | n | 1 | | | +---+ | | +---+ | | +---+ | +---------+ +---------+ | +---+ | | v | 2 | | | +---+ | +---------+ _________________________________________________________________________ | cmd a(1,1) a(1,0) | cmd a(1,1) a(0,2) +----+ +---------+ +---------+ | +----+ +---------+ +----+ | | | +---+ | | +---+ | | | | | +---+ | | | +----+ | m | 1 | | | m | 1 | | | +----+ | m | 1 | | +----+ | +---+ | | +---+ | | | +---+ | | +---+ | | +---+ | | | +---+ | | n | 1 | | | n | 0 | | | | n | 1 | | | +---+ | | +---+ | | | +---+ | +---------+ | +---+ | | +---------+ | v | 2 | | | | +---+ | | +---------+ | ________________________________|________________________________________ | cmd a(1,1) a(0,2) | cmd a(1,1) a(0,2) +----+ +---------+ +---------+ | +----+ +---------+ +---------+ | | | +---+ | | +---+ | | | | | +---+ | | +---+ | +----+ | m | 1 | | | m | 0 | | | +----+ | m | 1 | | | m | 0 | | | +---+ | | +---+ | | | +---+ | | +---+ | | +---+ | | +---+ | | | +---+ | | +---+ | | n | 1 | | | n | 2 | | | | n | 1 | | | n | 2 | | | +---+ | | +---+ | | | +---+ | | +---+ | +---------+ +---------+ | +---------+ | +---+ | | | v | 3 | | | | +---+ | | +---------+ ________________________________|________________________________________ | cmd a(1,1) | cmd +----+ +---------+ | +-----------+ | | | +---+ | | | +---+ | +----+ | m | 1 | | | | ans | 3 | | | +---+ | | | +---+ | | +---+ | | +-----------+ | n | 1 | | | | +---+ | | | +---+ | | | v | 3 | | | | +---+ | | +---------+ | =============================================================================== Q2. The *gradient* of a vector $v$ is the sequence of differences $v(i+1)-v(i)$ between consecutive elements $v(i)$ and $v(i+1)$ of $v$. Write a function $grad(v)$ to take a vector $v$ and return true if $v$'s gradient is strictly increasing, and return false otherwise. Examples: 2 3 5 6 8 true / \ / \ / \ / \ / \ v = [ 1 3 6 11 17 25 ] 2 3 3 4 false / \ / \ / \ / \ v = [ 1 3 6 9 13 ] 2 3 1 4 false / \ / \ / \ / \ v = [ 1 3 6 7 11 ] (a) Loop solution: function ans = grad(v) % ans = grad(v): return "gradient of $v$ is strictly increasing?" ans = logical(1); % answer so far <-- $logical$ not required i = 1; % [4/10] added % check pairs of successive differences; % stop if find pair that is not strictly increasing while ans & i <= length(v)-2 ans = ans & v(i+2) - v(i+1) > v(i+1) - v(i); i = i+1; end (b) Vectorized loop body solutions: 1: $ans = all(diff(diff(v)) > 0);$ 2: $v = v(2:end) - v(1:end-1); ans = all( v(2:end) - v(1:end)-1 > 0);$ 3: $ans = all(v(3:end) - 2*v(2:end-1) + v(1:end-2) > 0);$ Note: $sort(diff(v)) == diff(v)$ is wrong: it only checks non-decreasing, not strictly increasing. =============================================================================== Q3. Below is the Specification and a Flawed Implementation of a program. List all the flaws. For each flaw, + Briefly explain the problem in a few sentences. + Illustrate the problem with concrete values for the variables. Specification, with an example: You are given three string variables $new$, $old$, and $txt$: + String $new$ is a formal name, e.g. $new = 'Robert'$. + String $old$ is a nickname, e.g. $old = 'Bob'$. + String $txt$ is longer than $old$ and contains 0 or more occurrences (ignoring case) of $old$, e.g. $txt = 'Bob sees boBo, HIS friend'$ contains 2 occurrences of $'Bob'$. --- --- Assume occurrences of $old$ are non-overlapping, e.g. $'Bobob'$ cannot occur in $txt$. --=__ Replace all occurrences of $old$ in $txt$ with *exact* copies of $new$, e.g. the result for the values above should be $txt = 'Robert sees Roberto, HIS friend'$. ------ ------ Flawed Implementation: for i = findstr(txt, old) txt(i : i+length(old)-1) = new; end Solution: Flaw#1: string search/comparison is not case-insensitive Flaw#2: if $length(new) ~= length(old)$, assignment statement fails because $lhs = rhs$ requires $lhs$ and $rhs$ to be of equal size Flaw#3: if $length(new) ~= length(old)$, substituting in place shifts later occurences of $old$ to different positions Concrete examples illustrating each flaw: the original values provided. =============================================================================== Q4. Write a Matlab script to read a pre-sorted, 100-terminated input sequence of integers and print the value of the second to last mode. + Provide a correct & helpful loop invariant for each loop. + Make sure the program behaves reasonably for all legal inputs. + Do not use vectors of unbounded length. Example: -1 -1 0 1 1 1 1 2 2 3 3 3 3 6 6 6 7 8 8 8 8 9 9 9 100 \__ __/ \__ __/ \__ __/ V V V 3rd-to-last 2nd-to-last last mode mode mode Solution (similar to P3.1 and P4.1): stopping = 100; % stopping value prompt = ['number (' num2str(stopping) ' to stop) > ']; % input prompt num = input(prompt); % current input value % these variables are based on the input read so far, excluding $num$ mode = struct('value', nan, 'freq', 0); % value and frequency of last mode mode2 = nan; % second to last mode prev = mode; % previous input value and its frequency % read $stopping$-terminated input sequence % inv: maintain variable definitions above while num ~= stopping % update $prev$ if prev.value ~= num, prev.freq = 0; end; prev.value = num; prev.freq = 1 + prev.freq; % update $mode$, $mode2$ if prev.freq == mode.freq % another mode with same frequency? mode2 = mode.value; mode = prev; elseif prev.freq > mode.freq % new mode with new frequency? mode = prev; mode2 = NaN; % unique mode so far: no 2nd-to-last mode end % read next input num = input(prompt); end % display second-to-last mode disp(mode2);