edited by
1,039 views
8 votes
8 votes

We use the notation $[x1,x2,...,xn]$ to denote a list of integers. $[]$ denotes the empty list, and $[n]$ is the list consisting of one integer $n$. For a nonempty list l, $head(l)$ returns the first element of $l$, and $tail(l)$ returns the list obtained by removing the first element from $l$. The function $length(l)$ returns the length of a list. For example,

  • $head([11,-1,5]) = 11, tail([11,-1,5]) = [-1,5]$.
  • $head([7]) = 7, tail([7]) = []$.
  • $length([]) = 0, length([7]) = 1, length([11,-1,5]) = 3$.

We use or, and and not to denote the usual operations on boolean values $true$ and $false$.
Consider the following functions, each of which takes a list of integers as input and returns a boolean value.

f(l)
    if (length(l) < 2) then return(true)
    else return(g(l) or h(l))
g(l)
    if (length(l) < 2) then return(true)
    else
        if (head(l) < head(tail(l)) then return h(tail(l))
        else return(false)
h(l)
    if (length(l) < 2) then return(true)
    else
        if (head(l) > head(tail(l)) then return g(tail(l))
        else return(false)

When does $f(l)$ return the value true for an input $l$? Explain your answer.

edited by

1 Answer

Best answer
8 votes
8 votes
For any list $L,$ if there exists $3$ consecutive numbers which are sorted or reverse sorted, then the function will return false .

Here, we assume that any $2$ consecutive elements will always be different. In the question they have not specified what happens when we compare $2$ consecutive similar numbers.

 Let me consider a list $L:$  $[ X_1,X_2,X_3,\ldots,X_n], n>2$

The $2$ possible input sequences for which the function returns true  will be,  

$X_1>X_2<X_3>X_4<X_5\ldots$
$X_1<X_2>X_3<X_4>X_5\ldots$
edited by

Related questions

8 votes
8 votes
5 answers
1
go_editor asked May 22, 2016
1,940 views
A man has three cats. At least one is male. What is the probability that all three are male?$\frac{1}{2}$$\frac{1}{7}$$\frac{1}{8}$$\frac{3}{8}$
12 votes
12 votes
4 answers
4
go_editor asked May 27, 2016
1,450 views
Let $A$ be an array of $n$ integers, sorted so that $A \leq A \leq \dots A[n]$. Suppose you are given a number $x$ and you wish to find out if there exist indices $k$ a...