exercise-3.md

Exercise 3

Use the following commands to make a fresh clone of your repository:

git clone -b exercise-3 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git exercise-3

Update the README.md file with your solutions. Don't forget to list the group members's SCIPER numbers.

Problem 1: Parallel Encoding

In this exercise, your group will devise a parallel algorithm to encode sequences using the run-length encoding scheme. The encoding is very simple. It transforms sequences of letters such that all subsequences of the same letter are replaced by the letter and the sequence length. For instance:

"AAAAATTTGGGGTCCCAAC"  ⇒  "A5T3G4T1C3A2C1"

Your goal in this exercise is to come up with a parallel implementation of this algorithm. The function should have the following shape:

def rle(data: ParSeq[Char]): Buffer[(Char, Int)] =
  data.aggregate(???)(???, ???)

The Buffer class is already given to you. A buffer of type Buffer[A] represents sequences of elements of type A. It supports the following methods, all of which are efficient: