CS563 Assignment 4: Programming with Go
Instructor: Xinghui Zhao Due: 11:59pm, February 16, 2020
1 Overview
Communicating sequential processes (CSP) is a formal language for describing patterns of interac- tion in concurrent systems. It is a member of the family of mathematical theories of concurrency known as process algebras, or process calculi, based on message passing via channels. CSP was highly influential in the design of a number of programming languages, including Go. The purpose of this assignment is to give you some practice on programming using Go.
2 Merge
In Lecture 4 (message passing), we discussed a filter process which merges two input streams. The pseudo code is shown in Figure 1. If we create a number of merge processes, and organize them in a tree structure as shown in Figure 2, we can easily sort a data stream.
The pseudo code uses the traditional message passing syntax. Here, your task is to implement this algorithm using Go.
3 Sieve of Eratosthenes
We have discussed Sieve of Eratosthenes algorithm for generating prime numbers in Lecture 6 (CSP). This algorithm uses filer communication pattern. Figure 3 shows the algorithm.
Your task is to implement this algorithm using Go. 1
Figure 1: Merge Pseudo Code
Figure 2: Merge Processes
Figure 3: Sieve of Eratosthenes
2
4 One-Lane Bridge
Cars coming from the north and south arrive at a one-lane bridge. Cars heading in the same direction can across the bridge at the same time, but cars heading in opposite directions cannot.
Develop a Go program to simulate the use of the bridge. Assume the cars are client processes, and the bridge is the server process. Have cars repeatedly try to cross the bridge. They should spend a random amount of time on the bridge and should delay for a random amount of time before crossing again. Print a trace of the key events in your simulation.
5 Submission
Submit the following on Blackboard:
1. Source code for the three applications
2. Sample output for each of the applications (screenshots in png, pdf, jpeg, etc.)
6 Grading Scheme
This assignment will be graded out of 100. For your information, the grading scheme is shown in the following table. Note that for this assignment, code readability is evaluated in the grading process, so please include comments in the source code when necessary.
Item
Percentage
Merge Sieve One-lane bridge Code readability
30% 30% 30% 10%
3