NESL 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: Sum_i=0^n-1 A_i * B_i. 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 ==.

The Nesl Quick Reference Guide.

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).

The Nesl Quick Reference Guide.

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"]

The Nesl Quick Reference Guide.

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).

The Nesl Quick Reference Guide.

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.

The Nesl Quick Reference Guide.

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?

The Nesl Quick Reference Guide.

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

Guy Blelloch, blelloch@cs.cmu.edu.