Practice exam 1¶

Question 1¶

part a)¶

Consider this code:

var cache = make(map[string]string)

func read(key string) string {
    return cache[key]
}

func write(key, val string) {
  cache[key] = val
}

Why can concurrent calls to read() and write() cause problems?

part b)¶

Which of strategies in Go can prevent race conditions when accessing shared memory?

Question 2¶

part a)¶

Why are unbuffered channels considered a synchronization point?

part b)¶

Given:

ch := make(chan string, 2)

ch <- "A"
ch <- "B"
ch <- "C"

What happens when the third value is sent?

Question 3¶

part a)¶

Write down the formula for speedup. And write down the formula for efficiency. Use \(T(1)\) for sequential time and \(T(p)\) for parallel time.

part b)¶

Gustafson states the assumptions:

\[ T_{n}(p) = T_{0} + T_{\shortparallel} \frac{n}{p} \]

and \(n = cp\) (\(c\) is fixed).

Derive what these assumptions mean for the speedup \(S_{n,p}\). Use the definitions

\[ \gamma = \frac{T_{0}}{T_{0} + T_{\shortparallel}\,c} \quad\text{and}\quad (1 - \gamma) = \frac{T_{\shortparallel}\,c}{T_{0} + T_{\shortparallel}\,c} \]

to simplify your derivations.

part c)¶

Explain by using your derivations in (b): What happens to the speedup of Gustafson's law when \(p\) goes to infinity?

Question 4¶

Consider the following Go program:

package main

import (
    "fmt"
)

func worker(ch chan int) {
    count := 0
    for i := 0; i < 5; i++ {
        if i%2 == 0 {
            count++
        }
    }
    ch <- count
}

func main() {
    k := 3
    ch := make(chan int)

    for i := 0; i < k; i++ {
        go worker(ch)
    }

    total := 0
    for i := 0; i < k; i++ {
        total += <-ch
    }

    fmt.Println(total)
}

part a)¶

How many goroutines are created in total (including the main goroutine)?

part b)¶

What value does each worker send to the channel? Briefly explain why.

part c)¶

What is the final output printed by the program?

part d)¶

Does the order in which goroutines execute affect the final result? Why or why not?

Question 5¶

We estimate the value of \(\pi\) using random sampling: generate points \((x,y)\) uniformly in \([0,1]\times[0,1]\), and count how many satisfy \(x^2 + y^2 \le 1\).

part a)¶

Write a Go function:

func countInside(n int) int

that generates n random points and returns how many fall inside the unit quarter-circle.

part b)¶

Using goroutines and channels, write a function:

func MonteCarloPI(n, k int) float64

that:

Splits the total work evenly across k workers,
Collects partial counts via a channel,
Returns the estimate of \(\pi\).

part c)¶

What formula is used to convert the number of points inside the circle into an estimate of \(\pi\)? Briefly justify it.

part d)¶

If n is fixed and k increases, what do you expect to happen to:

Execution time?
Accuracy of the estimate?

Explain briefly.

Question 6¶

Consider the following Go program:

package main

import (
    "fmt"
    "math/rand"
    "sync"
)

func worker(n int, hits *int, mu *sync.Mutex, wg *sync.WaitGroup) {
    defer wg.Done()
    local := 0
    for i := 0; i < n; i++ {
        x := rand.Float64()
        y := rand.Float64()
        if x*x+y*y <= 1.0 {
            local++
        }
    }
    mu.Lock()
    *hits += local
    mu.Unlock()
}

func main() {
    var wg sync.WaitGroup
    var mu sync.Mutex
    totalHits := 0

    k := 4
    n := 1000

    for i := 0; i < k; i++ {
        wg.Add(1)
        go worker(n, &totalHits, &mu, &wg)
    }

    wg.Wait()
    fmt.Println("Hits:", totalHits)
}

part a)¶

What is the role of sync.WaitGroup in this program?

part b)¶

Why is a sync.Mutex needed when updating totalHits?

part c)¶

What would potentially happen if the mutex was removed? Name the type of issue.

part d)¶

Modify the program so that instead of using a mutex, each worker sends its result over a channel and the main goroutine aggregates the results.