# NESL Exercises

• Sequence operations
• Nested parallelism
• Other exercises

• ## Sequence Operations

### Exercise 1

Write a function, that takes two sequences of equal length and takes their dot product. In particular for two sequences A and B of length n, it should return: Sumi=0n-1 Ai * Bi. The function should require O(n) work and constant depth. Note that in NESL, the `sum` operation is defined to have constant depth (I'll motivate this in class).

In the following code replace `"Fill in"` with the appropriate code.

This should return 19.

You might find the Nesl Quick Reference Guide helpful.

### Exercise 2

Write a function that takes two words (sequences of characters) and returns true if and only if they are palindromes.

Hint: you might find the function `all` useful. To test if two characters are equal, you can use `==`.

### Exercise 3

The stock market problem is as follows: given the price of a stock at each day for n days, determine the biggest profit you can make by buying one day and selling on a later day. For example:
```  stock([12, 11, 10, 8, 5, 8, 9, 6, 7, 7, 10, 7, 4, 2]);
```
would return 5 since we can buy at 5 on day 5 and sell at 10 on day 11. This has a simple linear time serial solution. Write a NESL program to solve the stock market problem with work complexity O(n) and constant depth. Hint: you might try one of the scan operations (the scan operations are defined to take constant depth).

## Nested Parallelism

### Exercise 4

Write a function that takes a sequence of words (a sequence of sequences of characters), and removes any words with the letter `t` in it. The expression
```  (char == `t)
```
will test if `char` is the letter `t`. Note that it is a back quote, not a forward quote.
It should return
```  ["is","a","of"]
```

### Exercise 5

Write a function that returns all the primes up to n by checking for each integer i from 2 through n if it is a multiple of some integer in the range `[2...1+sqrt(i)]`. The function `isqrt` takes the square root of an integer.

Hint: you can use the expression `[2:n]` to generate a sequences of integers from 2 to n. The function `mod(i,j)` takes the modulus of `i` and `j` (ie. the remainder).

## Other Exercises

### Exercise 6

The sparse-matrix section of the tutorial, showed how to represent sparse matrices as a nested sequence and how to execute a sparse-matrix vector multiply. Here you should write code that takes a sparse matrix (represented in the same way) and extracts any column `i`. For example, for a matrix:
```A = [[(0,  2.0), (1, -1.0)                      ],
[(0, -1.0), (1,  2.0), (2, -3.0)           ],
[           (1, -1.0), (2,  2.0), (3, -1.0)],
[                      (2, -1.0), (3,  2.0)]]
```
the function `get_column(A,2)` should extract column 2 and return `[0.0, -3.0, 2.0, -1.0]`.

Hint: You might find the construct `[0:n]` useful.

### Exercise 7

Let's say we want to write our own version of the `sum` operation, which sums the elements of a sequences. Here is one way to write it:
Another way to write it would be to take the odd indexed elements and the even indexed elements of `a`, sum them elementwise and then recursively sum this new sequence. Write a `my_sum` function that uses this other method. You can assume the length of the input is a power of 2.

Hint: you might find the `odd_elts` and `even_elts` functions useful.

What is the work and depth of this code?

Here are the solutions to the exercises. You should try them all, however, before looking at the solutions.

Guy Blelloch, blelloch@cs.cmu.edu.