CS 350 2014-15 Homework 1

1 Instructions
2 Questions

1 Instructions

Use only the declarative style of coding. Do not use Cell s in Oz.
Please attempt the questions on your own.
If you refer to other sources, please cite them in your work.
The homework is due on August 24, at midnight.

2 Questions

Programming with Lists.
1. Define a function
```
fun {Take Xs N}
```
  which returns a list of the first N elements in Xs if Xs has at least N elements, otherwise returns Xs itself.
  [5 points]
2. Define the function
```
fun {Drop Xs N}
```
  which returns a list of all but the first N elements in Xs if Xs has at least N elements, otherwise returns nil.
  [5 points]
3. Define the function
```
fun {CrossProduct Xs Ys}
```
  which forms the cross-product of the two lists, by looking at the following examples.
```
{CrossProduct nil Ys} = nil
{CrossProduct Xs nil} = nil
{CrossProduct [a b c] [1 2 3] = [[a 1] [a 2] [a 3] [b 1] [b 2]
[b 3] [c 1] [c 2] [c 3]]
```
  [5 points]
Higher-Order Programming
1. Define a function Filter
```
fun {Filter F Xs}
```
  where
  1. F is a function which takes an input value and returns true if the value satisfies a condition and false otherwise,
  2. Xs is a list of elements.
  which does the following: create a sublist of Xs where each element satisfies the condition in F. Example
```
{Filter fun {$ X} X > 0 end [1 2 ~1]}
```
  should evaluate to [1 2].
  [5 points]
2. Define the function
```
define {FoldR F Xs Partial}
```
  where F is a binary function, which behaves as follows.
```
{FoldR F [a b c] Id} = {F a {F b {F c Id}}}
```
  [10 points]
3. Define Map using FoldR.
  [10 points]
You want to determine which movie is generating the most amount of buzz in the current month. You are given a collection of "feeds", which is a list of list of literals. Write an Oz function which takes a list of keywords, and a feed, and returns a list of lists of the form [K N] where N is the number of feeds in which the keyword K occurs. Example
```
{Count [planetOfTheApes kick] [[planetOfTheApes is boring]
                               [kick is terrible]
                               [dabangg rocks]]}
```
should evaluate to
```
[[planetOfTheApes 1] [kick 1]]
```
Try to write the function by using higher-order programming whenever possible.
[20 points]
Tail Recursion: Let N be a positive integer. Write a tail recursive function in Oz to generate the N th Fibonacci number. (Hint: Write the iterative code in C and compare.)
[10 points]
Lazy Evaluation. Write a lazy Oz function Sieve which produces an infinite list of primes, using the Eratosthenes' Sieve.
[20 points]
Lazy Evaluation: Write a lazy Oz function
```
fun lazy {ExpSeries X}
```
which computes the infinite list of terms in the Taylor series expansion of $e^X$. Further, write a function
```
fun {Approximant Epsilon Xs}
```
which is a function which takes an infinite list Xs as input, sums up terms in the series until adjacent terms are within Epsilon of each other, and returns the value.
[20 points]
Threads: Write a function taking an input Count. The function should run with two threads, the first producing an infinite sequence of random bits, and the second computing the average of the first Count number of random bits. You can use {OS.rand} mod 2 to produce random bits.
[15 points]

CS 350 2014-15 Homework 1

Table of Contents

1 Instructions

2 Questions