Agent Work: GitHub Contributions (Parallel)

Claude Opus 4.6 · COMP 322: Fundamentals of Parallel Programming

COMP 322 Homework 2: GitHub Contributions (Parallel)

Total: 100 points

Overview

Implement a concurrent version of a program that fetches and displays GitHub contributors and their total contributions across all repositories under a given organization.

Testing Your Solution

Important: This homework requires GitHub API credentials.

# Set credentials before testing
export GITHUB_USERNAME=your-username
export GITHUB_TOKEN=your-github-token

# Run tests
bin/grade workspaces/agent_hw2

To generate a GitHub token: 1. Go to https://github.com/settings/tokens/new 2. Select the repo scope 3. Generate and save the token

---

Part 1: Written Assignment (30 points)

1.1 Parallelizing the IsKColorable Algorithm (25 points)

Consider the pseudo-code of the IsKColorable algorithm:

Input: Graph g = (V, E) and k in N.
Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v)?

1  foreach Assignment f of a value in [k] to each node in V do
2      colorable <- True;
3      foreach {u, v} in E do
4          if f(u) = f(v) then
5              colorable <- False;
6              break;
7      if colorable = True then
8          return True;
9  return False;

1. (10 points) Create a parallel version using finish and async statements to maximize parallelism while ensuring correctness.

2. (5 points) What is the big-O for total WORK?

3. (5 points) Can your parallel algorithm have larger WORK than sequential? Explain.

4. (5 points) Can your parallel algorithm have smaller WORK than sequential? Explain.

5. (5 points) Is a data race possible? If so, is it benign?

---

Part 2: Programming Assignment (70 points)

Goal

The sequential version (loadContributorsSeq) causes the UI to freeze when loading. Implement loadContributorsPar with these requirements:

1. UI must NOT freeze when loading data 2. All requests and processing must be performed concurrently

Requirements

Use futures, data-driven tasks, and streams
Do NOT use finish or async
All aggregation and post-processing via concurrent streams

Test Organizations

revelation
galaxycats
moneyspyder
notch8
trabian
collectiveidea
edgecase

Implementation

Edit src/main/java/edu/rice/comp322/ContributorsUI.java: 1. Implement loadContributorsPar in the LoadContributors interface 2. Change line 65 from loadContributorsSeq to loadContributorsPar

---

Scoring

50 points: Parallel solution (no UI freeze, concurrent data loading)
5 points: Coding style and documentation
15 points: Report explaining:

- Parallel algorithm summary - Correctness and data-race-free justification - Expected work value as function of N

---

Files to Implement

src/main/java/edu/rice/comp322/ContributorsUI.java (implement loadContributorsPar)
src/main/java/edu/rice/comp322/LoadContributors.java (parallel method)

--- *COMP 322: Fundamentals of Parallel Programming, Rice University*

ContributorsUI.java5.7 KB

java

package edu.rice.comp322;

import java.awt.Dimension;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.List;
import java.util.prefs.Preferences;
import javax.swing.*;
import javax.swing.table.DefaultTableModel;

import static edu.rice.hj.Module0.launchHabaneroApp;

/**
 * User-Interface for loading the contributors for all repositories
 * under the given organization.
 */
public class ContributorsUI extends JFrame implements LoadContributors {

    private final JTextField username = new JTextField(20);
    private final JPasswordField password = new JPasswordField(20);
    private final JTextField org = new JTextField(20);
    private final JButton load = new JButton("Load contributors");
    private final Insets insets = new Insets(3, 10, 3, 10);
    private final String[] columns = {"Login", "Contributions"};
    private final DefaultTableModel resultsModel = new DefaultTableModel(columns, 0);
    public List<User> users = new ArrayList<>();
    private final JTable results = new JTable(resultsModel);
    private final JScrollPane resultsScroll = new JScrollPane(results);
    private Preferences pref;

    public ContributorsUI() {
        init();
    }

    /**
     * Updates the contributors list displayed on the user-interface.
     * @param users a list of Users
     */
    public void updateContributors(List<User> users) {
        Object[][] values = new Object[users.size()][2];
        for (int i = 0; i < users.size(); i++) {
            values[i] = new Object[]{users.get(i).login, users.get(i).contributions};
        }
        this.users = users;
        resultsModel.setDataVector(values, columns);
    }

    /**
     * Adds action listener for load button.
     */
    private void addLoadListener() {
        load.addActionListener(e -> {
            String userParam = username.getText();
            String passParam = String.valueOf(password.getPassword());
            String orgParam = org.getText();
            if (!userParam.isEmpty() && !passParam.isEmpty()) {
                saveParams(userParam, passParam, orgParam);
            }
            new Thread(()-> {
                launchHabaneroApp(() -> {
                    try {
                        System.out.println("Loading Users ...");
                        loadContributorsSeq(userParam, passParam, orgParam); //TODO change to use parallel implementation
                    } catch (Exception exception) {
                        exception.printStackTrace();
                    }
                });
            }).start();
        });
    }

    /**
     * Sets the parameters.
     */
    public void setParams(String userParam, String passParam, String orgParam) {
        username.setText(userParam);
        password.setText(passParam);
        org.setText(orgParam);
    }

    /**
     * Saves the parameter data.
     */
    public void saveParams(String userParam, String passParam, String orgParam) {
        this.pref.put("username", userParam);
        this.pref.put("password", passParam);
        this.pref.put("org", orgParam);
    }

    /**
     * Initializes the user interface.
     */
    private void init() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 500, 350);
        resultsScroll.setPreferredSize(new Dimension(200, 200));
        JPanel contentPane = new JPanel(new GridBagLayout());
        setContentPane(contentPane);
        addLabeled("GitHub Username", username);
        addLabeled("Password/Token", password);
        addWideSeparator();
        addLabeled("Organization", org);
        addWideSeparator();
        addLoad();
        addResultsScroll();
        this.pref = Preferences.userRoot().node("edu.rice.comp322.ContributorsUI");
        setParams(pref.get("username", ""), pref.get("password", ""), pref.get("org", ""));
        addLoadListener();
        updateContributors(new ArrayList<>());
    }


    /**
     * Adds labeled components.
     */
    private void addLabeled(String label, JComponent component) {
        GridBagConstraints constraintslbl =  new GridBagConstraints();
        constraintslbl.gridx = 0;
        constraintslbl.insets = insets;
        add(new JLabel(label), constraintslbl);
        GridBagConstraints constraintsComponent = new GridBagConstraints();
        constraintsComponent.gridx = 1;
        constraintsComponent.insets = insets;
        constraintsComponent.anchor = GridBagConstraints.WEST;
        constraintsComponent.fill = GridBagConstraints.HORIZONTAL;
        constraintsComponent.weightx = 1.0;
        add(component, constraintsComponent);
    }

    /**
     * Adds separator.
     */
    private void addWideSeparator() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.fill = GridBagConstraints.HORIZONTAL;
        add(new JSeparator(), constraints);
    }

    /**
     * Adds load button.
     */
    private void addLoad() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        add(load, constraints);
    }

    /**
     * Add scrollbar for results.
     */
    private void addResultsScroll() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.weightx = 1.0;
        constraints.weighty = 1.0;
        constraints.fill = GridBagConstraints.BOTH;
        add(resultsScroll, constraints);
    }

    public void start() {
        this.setVisible(true);
    }

}

ContributorsUI.java5.7 KB

java

package edu.rice.comp322;

import java.awt.Dimension;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.List;
import java.util.prefs.Preferences;
import javax.swing.*;
import javax.swing.table.DefaultTableModel;

import static edu.rice.hj.Module0.launchHabaneroApp;

/**
 * User-Interface for loading the contributors for all repositories
 * under the given organization.
 */
public class ContributorsUI extends JFrame implements LoadContributors {

    private final JTextField username = new JTextField(20);
    private final JPasswordField password = new JPasswordField(20);
    private final JTextField org = new JTextField(20);
    private final JButton load = new JButton("Load contributors");
    private final Insets insets = new Insets(3, 10, 3, 10);
    private final String[] columns = {"Login", "Contributions"};
    private final DefaultTableModel resultsModel = new DefaultTableModel(columns, 0);
    public List<User> users = new ArrayList<>();
    private final JTable results = new JTable(resultsModel);
    private final JScrollPane resultsScroll = new JScrollPane(results);
    private Preferences pref;

    public ContributorsUI() {
        init();
    }

    /**
     * Updates the contributors list displayed on the user-interface.
     * @param users a list of Users
     */
    public void updateContributors(List<User> users) {
        Object[][] values = new Object[users.size()][2];
        for (int i = 0; i < users.size(); i++) {
            values[i] = new Object[]{users.get(i).login, users.get(i).contributions};
        }
        this.users = users;
        resultsModel.setDataVector(values, columns);
    }

    /**
     * Adds action listener for load button.
     */
    private void addLoadListener() {
        load.addActionListener(e -> {
            String userParam = username.getText();
            String passParam = String.valueOf(password.getPassword());
            String orgParam = org.getText();
            if (!userParam.isEmpty() && !passParam.isEmpty()) {
                saveParams(userParam, passParam, orgParam);
            }
            new Thread(()-> {
                launchHabaneroApp(() -> {
                    try {
                        System.out.println("Loading Users ...");
                        loadContributorsSeq(userParam, passParam, orgParam); //TODO change to use parallel implementation
                    } catch (Exception exception) {
                        exception.printStackTrace();
                    }
                });
            }).start();
        });
    }

    /**
     * Sets the parameters.
     */
    public void setParams(String userParam, String passParam, String orgParam) {
        username.setText(userParam);
        password.setText(passParam);
        org.setText(orgParam);
    }

    /**
     * Saves the parameter data.
     */
    public void saveParams(String userParam, String passParam, String orgParam) {
        this.pref.put("username", userParam);
        this.pref.put("password", passParam);
        this.pref.put("org", orgParam);
    }

    /**
     * Initializes the user interface.
     */
    private void init() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 500, 350);
        resultsScroll.setPreferredSize(new Dimension(200, 200));
        JPanel contentPane = new JPanel(new GridBagLayout());
        setContentPane(contentPane);
        addLabeled("GitHub Username", username);
        addLabeled("Password/Token", password);
        addWideSeparator();
        addLabeled("Organization", org);
        addWideSeparator();
        addLoad();
        addResultsScroll();
        this.pref = Preferences.userRoot().node("edu.rice.comp322.ContributorsUI");
        setParams(pref.get("username", ""), pref.get("password", ""), pref.get("org", ""));
        addLoadListener();
        updateContributors(new ArrayList<>());
    }


    /**
     * Adds labeled components.
     */
    private void addLabeled(String label, JComponent component) {
        GridBagConstraints constraintslbl =  new GridBagConstraints();
        constraintslbl.gridx = 0;
        constraintslbl.insets = insets;
        add(new JLabel(label), constraintslbl);
        GridBagConstraints constraintsComponent = new GridBagConstraints();
        constraintsComponent.gridx = 1;
        constraintsComponent.insets = insets;
        constraintsComponent.anchor = GridBagConstraints.WEST;
        constraintsComponent.fill = GridBagConstraints.HORIZONTAL;
        constraintsComponent.weightx = 1.0;
        add(component, constraintsComponent);
    }

    /**
     * Adds separator.
     */
    private void addWideSeparator() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.fill = GridBagConstraints.HORIZONTAL;
        add(new JSeparator(), constraints);
    }

    /**
     * Adds load button.
     */
    private void addLoad() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        add(load, constraints);
    }

    /**
     * Add scrollbar for results.
     */
    private void addResultsScroll() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.weightx = 1.0;
        constraints.weighty = 1.0;
        constraints.fill = GridBagConstraints.BOTH;
        add(resultsScroll, constraints);
    }

    public void start() {
        this.setVisible(true);
    }

}

ContributorsUI.java5.6 KB

java

package edu.rice.comp322;

import java.awt.Dimension;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.List;
import java.util.prefs.Preferences;
import javax.swing.*;
import javax.swing.table.DefaultTableModel;

import static edu.rice.hj.Module0.launchHabaneroApp;

/**
 * User-Interface for loading the contributors for all repositories
 * under the given organization.
 */
public class ContributorsUI extends JFrame implements LoadContributors {

    private final JTextField username = new JTextField(20);
    private final JPasswordField password = new JPasswordField(20);
    private final JTextField org = new JTextField(20);
    private final JButton load = new JButton("Load contributors");
    private final Insets insets = new Insets(3, 10, 3, 10);
    private final String[] columns = {"Login", "Contributions"};
    private final DefaultTableModel resultsModel = new DefaultTableModel(columns, 0);
    public List<User> users = new ArrayList<>();
    private final JTable results = new JTable(resultsModel);
    private final JScrollPane resultsScroll = new JScrollPane(results);
    private Preferences pref;

    public ContributorsUI() {
        init();
    }

    /**
     * Updates the contributors list displayed on the user-interface.
     * @param users a list of Users
     */
    public void updateContributors(List<User> users) {
        Object[][] values = new Object[users.size()][2];
        for (int i = 0; i < users.size(); i++) {
            values[i] = new Object[]{users.get(i).login, users.get(i).contributions};
        }
        this.users = users;
        resultsModel.setDataVector(values, columns);
    }

    /**
     * Adds action listener for load button.
     */
    private void addLoadListener() {
        load.addActionListener(e -> {
            String userParam = username.getText();
            String passParam = String.valueOf(password.getPassword());
            String orgParam = org.getText();
            if (!userParam.isEmpty() && !passParam.isEmpty()) {
                saveParams(userParam, passParam, orgParam);
            }
            new Thread(()-> {
                launchHabaneroApp(() -> {
                    try {
                        System.out.println("Loading Users ...");
                        loadContributorsPar(userParam, passParam, orgParam);
                    } catch (Exception exception) {
                        exception.printStackTrace();
                    }
                });
            }).start();
        });
    }

    /**
     * Sets the parameters.
     */
    public void setParams(String userParam, String passParam, String orgParam) {
        username.setText(userParam);
        password.setText(passParam);
        org.setText(orgParam);
    }

    /**
     * Saves the parameter data.
     */
    public void saveParams(String userParam, String passParam, String orgParam) {
        this.pref.put("username", userParam);
        this.pref.put("password", passParam);
        this.pref.put("org", orgParam);
    }

    /**
     * Initializes the user interface.
     */
    private void init() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 500, 350);
        resultsScroll.setPreferredSize(new Dimension(200, 200));
        JPanel contentPane = new JPanel(new GridBagLayout());
        setContentPane(contentPane);
        addLabeled("GitHub Username", username);
        addLabeled("Password/Token", password);
        addWideSeparator();
        addLabeled("Organization", org);
        addWideSeparator();
        addLoad();
        addResultsScroll();
        this.pref = Preferences.userRoot().node("edu.rice.comp322.ContributorsUI");
        setParams(pref.get("username", ""), pref.get("password", ""), pref.get("org", ""));
        addLoadListener();
        updateContributors(new ArrayList<>());
    }


    /**
     * Adds labeled components.
     */
    private void addLabeled(String label, JComponent component) {
        GridBagConstraints constraintslbl =  new GridBagConstraints();
        constraintslbl.gridx = 0;
        constraintslbl.insets = insets;
        add(new JLabel(label), constraintslbl);
        GridBagConstraints constraintsComponent = new GridBagConstraints();
        constraintsComponent.gridx = 1;
        constraintsComponent.insets = insets;
        constraintsComponent.anchor = GridBagConstraints.WEST;
        constraintsComponent.fill = GridBagConstraints.HORIZONTAL;
        constraintsComponent.weightx = 1.0;
        add(component, constraintsComponent);
    }

    /**
     * Adds separator.
     */
    private void addWideSeparator() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.fill = GridBagConstraints.HORIZONTAL;
        add(new JSeparator(), constraints);
    }

    /**
     * Adds load button.
     */
    private void addLoad() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        add(load, constraints);
    }

    /**
     * Add scrollbar for results.
     */
    private void addResultsScroll() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.weightx = 1.0;
        constraints.weighty = 1.0;
        constraints.fill = GridBagConstraints.BOTH;
        add(resultsScroll, constraints);
    }

    public void start() {
        this.setVisible(true);
    }

}

ContributorsUI.java5.6 KB

java

package edu.rice.comp322;

import java.awt.Dimension;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.Insets;
import java.util.ArrayList;
import java.util.List;
import java.util.prefs.Preferences;
import javax.swing.*;
import javax.swing.table.DefaultTableModel;

import static edu.rice.hj.Module0.launchHabaneroApp;

/**
 * User-Interface for loading the contributors for all repositories
 * under the given organization.
 */
public class ContributorsUI extends JFrame implements LoadContributors {

    private final JTextField username = new JTextField(20);
    private final JPasswordField password = new JPasswordField(20);
    private final JTextField org = new JTextField(20);
    private final JButton load = new JButton("Load contributors");
    private final Insets insets = new Insets(3, 10, 3, 10);
    private final String[] columns = {"Login", "Contributions"};
    private final DefaultTableModel resultsModel = new DefaultTableModel(columns, 0);
    public List<User> users = new ArrayList<>();
    private final JTable results = new JTable(resultsModel);
    private final JScrollPane resultsScroll = new JScrollPane(results);
    private Preferences pref;

    public ContributorsUI() {
        init();
    }

    /**
     * Updates the contributors list displayed on the user-interface.
     * @param users a list of Users
     */
    public void updateContributors(List<User> users) {
        Object[][] values = new Object[users.size()][2];
        for (int i = 0; i < users.size(); i++) {
            values[i] = new Object[]{users.get(i).login, users.get(i).contributions};
        }
        this.users = users;
        resultsModel.setDataVector(values, columns);
    }

    /**
     * Adds action listener for load button.
     */
    private void addLoadListener() {
        load.addActionListener(e -> {
            String userParam = username.getText();
            String passParam = String.valueOf(password.getPassword());
            String orgParam = org.getText();
            if (!userParam.isEmpty() && !passParam.isEmpty()) {
                saveParams(userParam, passParam, orgParam);
            }
            new Thread(()-> {
                launchHabaneroApp(() -> {
                    try {
                        System.out.println("Loading Users ...");
                        loadContributorsPar(userParam, passParam, orgParam);
                    } catch (Exception exception) {
                        exception.printStackTrace();
                    }
                });
            }).start();
        });
    }

    /**
     * Sets the parameters.
     */
    public void setParams(String userParam, String passParam, String orgParam) {
        username.setText(userParam);
        password.setText(passParam);
        org.setText(orgParam);
    }

    /**
     * Saves the parameter data.
     */
    public void saveParams(String userParam, String passParam, String orgParam) {
        this.pref.put("username", userParam);
        this.pref.put("password", passParam);
        this.pref.put("org", orgParam);
    }

    /**
     * Initializes the user interface.
     */
    private void init() {
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setBounds(100, 100, 500, 350);
        resultsScroll.setPreferredSize(new Dimension(200, 200));
        JPanel contentPane = new JPanel(new GridBagLayout());
        setContentPane(contentPane);
        addLabeled("GitHub Username", username);
        addLabeled("Password/Token", password);
        addWideSeparator();
        addLabeled("Organization", org);
        addWideSeparator();
        addLoad();
        addResultsScroll();
        this.pref = Preferences.userRoot().node("edu.rice.comp322.ContributorsUI");
        setParams(pref.get("username", ""), pref.get("password", ""), pref.get("org", ""));
        addLoadListener();
        updateContributors(new ArrayList<>());
    }


    /**
     * Adds labeled components.
     */
    private void addLabeled(String label, JComponent component) {
        GridBagConstraints constraintslbl =  new GridBagConstraints();
        constraintslbl.gridx = 0;
        constraintslbl.insets = insets;
        add(new JLabel(label), constraintslbl);
        GridBagConstraints constraintsComponent = new GridBagConstraints();
        constraintsComponent.gridx = 1;
        constraintsComponent.insets = insets;
        constraintsComponent.anchor = GridBagConstraints.WEST;
        constraintsComponent.fill = GridBagConstraints.HORIZONTAL;
        constraintsComponent.weightx = 1.0;
        add(component, constraintsComponent);
    }

    /**
     * Adds separator.
     */
    private void addWideSeparator() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.fill = GridBagConstraints.HORIZONTAL;
        add(new JSeparator(), constraints);
    }

    /**
     * Adds load button.
     */
    private void addLoad() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        add(load, constraints);
    }

    /**
     * Add scrollbar for results.
     */
    private void addResultsScroll() {
        GridBagConstraints constraints = new GridBagConstraints();
        constraints.gridx = 0;
        constraints.gridwidth = 2;
        constraints.insets = insets;
        constraints.weightx = 1.0;
        constraints.weighty = 1.0;
        constraints.fill = GridBagConstraints.BOTH;
        add(resultsScroll, constraints);
    }

    public void start() {
        this.setVisible(true);
    }

}

COMP 322 Homework 2: GitHub Contributions (Parallel)

Part 1: Written Questions (30 points)

1.1 Parallelizing the IsKColorable Algorithm

Consider the pseudo-code of the IsKColorable algorithm:

Input: Graph g = (V, E) and k in N.
Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v)?

1  foreach Assignment f of a value in [k] to each node in V do
2      colorable <- True;
3      foreach {u, v} in E do
4          if f(u) = f(v) then
5              colorable <- False;
6              break;
7      if colorable = True then
8          return True;
9  return False;

---

1.1.1 Parallel Version (10 points)

> Create a parallel version using finish and async statements to maximize parallelism while ensuring correctness.

Your Answer:

Input: Graph g = (V, E) and k in N.
Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v)?

1  result <- False
2  finish {
3      foreach Assignment f of a value in [k] to each node in V do
4          async {
5              colorable <- True
6              foreach {u, v} in E do
7                  if f(u) = f(v) then
8                      colorable <- False
9                      break
10             if colorable = True then
11                 result <- True
12         }
13 }
14 return result

The key parallelization strategy is to make each assignment check an independent async task within a finish block. The outer loop (over all possible k-colorings) has independent iterations since checking whether a given assignment is a valid coloring does not depend on any other assignment. Each async task checks all edges for its assignment and sets the shared result variable to True if a valid coloring is found. The finish block ensures all async tasks complete before returning. We cannot use return True inside an async, so we instead write to a shared variable result and return it after the finish completes.

---

1.1.2 Total Work Analysis (5 points)

> What is the big-O for total WORK?

Your Answer:

The total work is **O(k^|V| * |E|)**.

There are k^|V| possible assignments (each of the |V| nodes can be assigned one of k colors). For each assignment, the inner loop checks up to |E| edges. Since every async task runs to completion (the finish block waits for all), the total work across all tasks is O(k^|V| * |E|). This is the same as the worst-case work of the sequential algorithm (when no valid coloring exists).

---

1.1.3 Larger Work Than Sequential? (5 points)

> Can your parallel algorithm have LARGER WORK than sequential? Explain.

Your Answer:

Yes. The sequential algorithm can terminate early via return True on line 8 as soon as it finds the first valid coloring. If a valid coloring is found in the first iteration, the sequential algorithm does only O(|E|) work. In contrast, the parallel version spawns async tasks for all k^|V| assignments simultaneously, and the finish block must wait for all of them to complete. There is no mechanism to cancel the remaining async tasks once one finds a valid coloring. Therefore, the parallel version always performs O(k^|V| * |E|) work regardless of where a valid coloring appears in the enumeration, which can be significantly larger than the sequential work when a valid coloring is found early.

---

1.1.4 Smaller Work Than Sequential? (5 points)

> Can your parallel algorithm have SMALLER WORK than sequential? Explain.

Your Answer:

No. The parallel algorithm cannot have smaller total WORK than the sequential algorithm. Work is the total amount of computation performed across all processors. In the worst case (no valid coloring exists), both algorithms check all k^|V| assignments and all |E| edges per assignment, resulting in O(k^|V| * |E|) work. In the best case, the sequential algorithm benefits from early termination, while the parallel algorithm always checks all assignments. Therefore the parallel WORK is always greater than or equal to the sequential WORK.

Note: While the parallel algorithm cannot reduce WORK, it can significantly reduce SPAN (critical path length). The span is O(|E|) since all assignment checks run in parallel. This gives a parallelism of O(k^|V|), meaning the wall-clock time can be dramatically reduced even though total work stays the same or increases.

---

1.1.5 Data Race Analysis (5 points)

> Is a data race possible? If so, is it benign?

Your Answer:

Yes, there is a data race on the shared variable result. Multiple async tasks may concurrently write True to result (line 11), and these writes are not protected by any synchronization. Additionally, there are concurrent reads and writes between different tasks.

However, this data race is benign for the following reasons:

1. The variable result is initialized to False and is only ever written with the value True (line 11). It is never set back to False. 2. All concurrent writes store the same value (True), so the order of writes does not matter. 3. The variable is only read after the finish block completes (line 14), at which point all async tasks have finished and all writes are visible. 4. The correctness of the algorithm depends only on whether result is True after the finish block. Since any valid coloring sets it to True and it is never reset, the final value is correct regardless of write ordering.

Therefore, the data race does not affect the correctness of the algorithm.

---

Part 2: Report (15 points)

A. Algorithm Summary

The loadContributorsPar implementation uses HJlib futures and Java Streams for concurrent data loading:

1. Repository Listing (Sequential): A single API call fetches the list of repositories for the given GitHub organization. This is inherently sequential since it's one request.

2. Contributor Fetching (Parallel with Futures): For each repository, an HjFuture<List<User>> is created using future(() -> ...). Each future concurrently makes an HTTP GET request to fetch the contributors for that repository. All N futures are created in the main task and execute concurrently.

3. Result Collection: The main task iterates through the list of futures, calling f.get() on each to retrieve the contributor lists. HJlib's data-driven task mechanism ensures the main task blocks on each f.get() only until that specific future completes.

4. Aggregation (Streams): Java Streams are used to aggregate contributions: Collectors.groupingBy(u -> u.login, Collectors.summingInt(u -> u.contributions)) groups users by login name and sums their contributions across all repositories. This replaces the sequential manual deduplication loop.

5. Sorting: The aggregated list is sorted by contributions in descending order, matching the sequential output.

---

B. Correctness and Data-Race-Free Justification

1. Same results as sequential: Each future fetches the exact same data from the same API endpoint as the sequential loop iteration it replaces. The stream-based aggregation (groupingBy + summingInt) produces mathematically identical results to the manual deduplication loop (both sum contributions per unique login). The final sort order is identical (descending by contributions).

2. Data-race-free: The implementation is free from data races because: - Each future operates on completely independent data: separate HTTP call, separate response object, separate local variable for the result list. - No mutable state is shared between futures. - The f.get() calls in the main task enforce a happens-before relationship: all writes within a future are visible to the main task after f.get() returns. - The allUsers list is only modified by the main task (after collecting future results), never concurrently. - Stream operations are functional and do not mutate shared state.

3. Correct aggregation: Collectors.groupingBy partitions users by login (achieving deduplication), and Collectors.summingInt correctly sums the integer contributions for each group. This is equivalent to the sequential approach of checking contains() and adding to existing entries.

---

C. Work Analysis

Let N = number of repositories and M = total number of contributors across all repos.

Work breakdown:

Fetching repos: 1 task (the initial sequential API call)
Fetching contributors: N tasks (one future per repository), each performing one API call. In HJlib abstract metrics, each future counts as 1 unit of work, giving N work units.
Total HJlib work: N + 1 (N futures + 1 main task)

This matches the test assertion that work <= repos + 1.

Computational work (beyond HJlib metrics):

Result collection: O(M) to iterate through all future results and build the combined user list
Stream aggregation: O(M) for the groupingBy and summingInt operations
Sorting: O(U * log(U)) where U = number of unique users (U <= M)
Total computational work: O(N + M + U * log(U))

Parallelism:

Critical Path Length (CPL): 2 (the main task creates all futures, then waits for the longest one to complete)
Parallelism ratio: (N + 1) / 2, meaning with sufficient processors, the parallel version achieves approximately N/2 speedup over sequential execution of the API calls

---

COMP 322 Homework 2 — Grading Report

---

Part 1: Written Questions (30 points)

1.1.1 Parallel Version (10 points)

Score: 9/10

The student provides a clean, correct parallel version that:

Wraps the entire computation in a finish block ✓
Creates an async for each of the k^|V| assignment checks ✓
Keeps the inner edge loop sequential within each async (preserving break optimization) ✓
Uses a shared result variable instead of return True (correctly noting you cannot return from an async) ✓
Returns result after the finish block completes ✓

The accompanying explanation is excellent and clearly articulates the design rationale.

Deduction (−1): The pseudocode does not use AtomicBoolean or isolated for the shared result variable. The rubric requires "proper synchronization for shared result (isolated/atomic)" for full marks. While the student correctly identifies the resulting data race as benign in Q1.1.5, the parallel code as written lacks explicit synchronization. Per rubric: "Correct structure with minor issues (missing isolated)" → 8–9 points.

---

1.1.2 Total Work Analysis (5 points)

Score: 5/5

The student gives the correct answer: O(k^|V| · |E|) with a clear derivation:

k^|V| assignments (k colors for each of |V| vertices) ✓
O(|E|) work per assignment to check all edges ✓
Correct multiplication for total work ✓
Notes this matches the worst-case sequential work ✓

Matches the reference solution exactly.

---

1.1.3 Larger Work Than Sequential? (5 points)

Score: 5/5

The student answers Yes and provides an excellent explanation:

Sequential terminates early via return True on line 8 ✓
Parallel spawns all k^|V| asyncs; finish must wait for all to complete ✓
No mechanism to cancel remaining asyncs after one finds a valid coloring ✓
Concrete example: sequential could do O(|E|) if valid coloring found first, while parallel always does O(k^|V| · |E|) ✓

Thorough and well-reasoned.

---

1.1.4 Smaller Work Than Sequential? (5 points)

Score: 5/5

The student answers No with a correct explanation:

Work is total computation across all processors, not wall-clock time ✓
Parallel work ≥ sequential work in all cases ✓
Clearly distinguishes WORK from SPAN ✓
Bonus insight: parallelism reduces span to O(|E|), giving parallelism of O(k^|V|) ✓

Matches the reference solution and adds valuable context about span.

---

1.1.5 Data Race Analysis (5 points)

Score: 5/5

The student correctly identifies:

Yes, data race on shared result variable (concurrent reads and writes without synchronization) ✓
Yes, it is benign ✓

Justification is thorough and covers all key points: 1. result initialized to False, only ever written as True ✓ 2. All concurrent writes store the same value ✓ 3. result is only read after finish completes (happens-before guarantee) ✓ 4. Final correctness depends only on whether any valid coloring was found ✓

Excellent analysis that matches the reference solution.

---

Part 2: Report (15 points)

Section A: Algorithm Summary (5 points)

Score: 5/5

The student provides a clear, well-structured 5-step description: 1. Sequential repo listing (single API call) ✓ 2. Parallel contributor fetching via HjFuture per repo ✓ 3. Result collection via f.get() with data-driven blocking ✓ 4. Stream-based aggregation (groupingBy + summingInt) ✓ 5. Sorting in descending order ✓

All three required elements addressed: futures for parallel API calls, data aggregation via streams, and UI blocking avoided through concurrent futures.

---

Section B: Correctness Justification (5 points)

Score: 5/5

Comprehensive justification covering:

Equivalence to sequential: Same API endpoints, same aggregation logic, same sort order ✓
Data-race-free: Independent futures, no shared mutable state, happens-before from f.get(), allUsers only modified by main task ✓
Correct aggregation: groupingBy + summingInt mathematically equivalent to manual deduplication loop ✓

The happens-before analysis referencing f.get() is particularly well done.

---

Section C: Work Analysis (5 points)

Score: 5/5

Clear and thorough analysis:

Defines N (repos) and M (total contributors) ✓
HJlib work: N + 1 tasks (N futures + 1 main task) ✓
Matches test assertion work <= repos + 1 ✓
Computational work: O(N + M + U·log(U)) ✓
Parallelism: CPL = 2, parallelism ratio ≈ N/2 ✓

Goes beyond the minimum by providing both HJlib abstract metrics and computational complexity analysis.

---

Summary

Problem	Score	Max	Notes
1.1.1 Parallel Version	9	10	Missing explicit synchronization (atomic/isolated) on shared `result`
1.1.2 Total Work	5	5	Correct: O(k^{\	V\	} · \	E\	)
1.1.3 Larger Work?	5	5	Yes — early termination lost
1.1.4 Smaller Work?	5	5	No — work ≠ span
1.1.5 Data Race?	5	5	Yes, benign — only writes True
Report A: Summary	5	5	Clear 5-step algorithm description
Report B: Correctness	5	5	Strong happens-before analysis
Report C: Work Analysis	5	5	Both HJlib and computational complexity
Total	44	45

Overall: This is an excellent submission. The written answers demonstrate strong understanding of parallel algorithm design, work/span analysis, and data race reasoning. The report is thorough and well-organized. The only minor deduction is the absence of explicit synchronization (AtomicBoolean or isolated) in the parallel pseudocode — though the student clearly understands the issue, as evidenced by the insightful benign data race analysis in Q1.1.5.

Total: 44/45

.mcp.json

diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index c393978..0000000
--- a/.mcp.json
+++ /dev/null
@@ -1,11 +0,0 @@
-{
-  "mcpServers": {
-    "bscs-bench": {
-      "command": "/Users/bebe/Code/bscs-bench/bin/bscs-mcp",
-      "args": [
-        "--workspace",
-        "./writeup.md b/writeup.md
index 5e8f3d0..8b257ac 100644
--- a/writeup.md
+++ b/writeup.md
@@ -29,11 +29,27 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 **Your Answer:**
 
-```java
-// Write your parallel pseudocode here
 ```
+Input: Graph g = (V, E) and k in N.
+Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v)?
 
-[Explain your parallelization strategy and synchronization approach]
+1  result <- False
+2  finish {
+3      foreach Assignment f of a value in [k] to each node in V do
+4          async {
+5              colorable <- True
+6              foreach {u, v} in E do
+7                  if f(u) = f(v) then
+8                      colorable <- False
+9                      break
+10             if colorable = True then
+11                 result <- True
+12         }
+13 }
+14 return result
+```
+
+The key parallelization strategy is to make each assignment check an independent async task within a finish block. The outer loop (over all possible k-colorings) has independent iterations since checking whether a given assignment is a valid coloring does not depend on any other assignment. Each async task checks all edges for its assignment and sets the shared `result` variable to `True` if a valid coloring is found. The finish block ensures all async tasks complete before returning. We cannot use `return True` inside an async, so we instead write to a shared variable `result` and return it after the finish completes.
 
 ---
 
@@ -43,7 +59,9 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 **Your Answer:**
 
-[Provide the big-O formula in terms of k, |V|, and |E|, with explanation]
+The total work is **O(k^|V| * |E|)**.
+
+There are k^|V| possible assignments (each of the |V| nodes can be assigned one of k colors). For each assignment, the inner loop checks up to |E| edges. Since every async task runs to completion (the finish block waits for all), the total work across all tasks is O(k^|V| * |E|). This is the same as the worst-case work of the sequential algorithm (when no valid coloring exists).
 
 ---
 
@@ -53,7 +71,7 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 **Your Answer:**
 
-[Yes/No with detailed explanation]
+Yes. The sequential algorithm can terminate early via `return True` on line 8 as soon as it finds the first valid coloring. If a valid coloring is found in the first iteration, the sequential algorithm does only O(|E|) work. In contrast, the parallel version spawns async tasks for all k^|V| assignments simultaneously, and the finish block must wait for all of them to complete. There is no mechanism to cancel the remaining async tasks once one finds a valid coloring. Therefore, the parallel version always performs O(k^|V| * |E|) work regardless of where a valid coloring appears in the enumeration, which can be significantly larger than the sequential work when a valid coloring is found early.
 
 ---
 
@@ -63,7 +81,9 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 **Your Answer:**
 
-[Yes/No with detailed explanation. Distinguish between Work and Span.]
+No. The parallel algorithm cannot have smaller total WORK than the sequential algorithm. Work is the total amount of computation performed across all processors. In the worst case (no valid coloring exists), both algorithms check all k^|V| assignments and all |E| edges per assignment, resulting in O(k^|V| * |E|) work. In the best case, the sequential algorithm benefits from early termination, while the parallel algorithm always checks all assignments. Therefore the parallel WORK is always greater than or equal to the sequential WORK.
+
+Note: While the parallel algorithm cannot reduce WORK, it can significantly reduce SPAN (critical path length). The span is O(|E|) since all assignment checks run in parallel. This gives a parallelism of O(k^|V|), meaning the wall-clock time can be dramatically reduced even though total work stays the same or increases.
 
 ---
 
@@ -73,7 +93,16 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 **Your Answer:**
 
-[Identify shared variables, analyze concurrent access patterns, and determine if any race is benign]
+Yes, there is a data race on the shared variable `result`. Multiple async tasks may concurrently write `True` to `result` (line 11), and these writes are not protected by any synchronization. Additionally, there are concurrent reads and writes between different tasks.
+
+However, this data race is **benign** for the following reasons:
+
+1. The variable `result` is initialized to `False` and is only ever written with the value `True` (line 11). It is never set back to `False`.
+2. All concurrent writes store the same value (`True`), so the order of writes does not matter.
+3. The variable is only read after the finish block completes (line 14), at which point all async tasks have finished and all writes are visible.
+4. The correctness of the algorithm depends only on whether `result` is `True` after the finish block. Since any valid coloring sets it to `True` and it is never reset, the final value is correct regardless of write ordering.
+
+Therefore, the data race does not affect the correctness of the algorithm.
 
 ---
 
@@ -81,19 +110,32 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 ### A. Algorithm Summary
 
-[Describe your parallel implementation of loadContributorsPar:
-- What parallel constructs did you use (futures, streams)?
-- How are API calls parallelized?
-- How is data aggregation performed?]
+The `loadContributorsPar` implementation uses HJlib futures and Java Streams for concurrent data loading:
+
+1. **Repository Listing (Sequential):** A single API call fetches the list of repositories for the given GitHub organization. This is inherently sequential since it's one request.
+
+2. **Contributor Fetching (Parallel with Futures):** For each repository, an `HjFuture<List<User>>` is created using `future(() -> ...)`. Each future concurrently makes an HTTP GET request to fetch the contributors for that repository. All N futures are created in the main task and execute concurrently.
+
+3. **Result Collection:** The main task iterates through the list of futures, calling `f.get()` on each to retrieve the contributor lists. HJlib's data-driven task mechanism ensures the main task blocks on each `f.get()` only until that specific future completes.
+
+4. **Aggregation (Streams):** Java Streams are used to aggregate contributions: `Collectors.groupingBy(u -> u.login, Collectors.summingInt(u -> u.contributions))` groups users by login name and sums their contributions across all repositories. This replaces the sequential manual deduplication loop.
+
+5. **Sorting:** The aggregated list is sorted by contributions in descending order, matching the sequential output.
 
 ---
 
 ### B. Correctness and Data-Race-Free Justification
 
-[Explain why your implementation:
-1. Produces the same results as the sequential version
-2. Is free from data races
-3. Correctly handles aggregation (e.g., summing contributions)]
+1. **Same results as sequential:** Each future fetches the exact same data from the same API endpoint as the sequential loop iteration it replaces. The stream-based aggregation (`groupingBy` + `summingInt`) produces mathematically identical results to the manual deduplication loop (both sum contributions per unique login). The final sort order is identical (descending by contributions).
+
+2. **Data-race-free:** The implementation is free from data races because:
+   - Each future operates on completely independent data: separate HTTP call, separate response object, separate local variable for the result list.
+   - No mutable state is shared between futures.
+   - The `f.get()` calls in the main task enforce a happens-before relationship: all writes within a future are visible to the main task after `f.get()` returns.
+   - The `allUsers` list is only modified by the main task (after collecting future results), never concurrently.
+   - Stream operations are functional and do not mutate shared state.
+
+3. **Correct aggregation:** `Collectors.groupingBy` partitions users by login (achieving deduplication), and `Collectors.summingInt` correctly sums the integer contributions for each group. This is equivalent to the sequential approach of checking `contains()` and adding to existing entries.
 
 ---
 
@@ -101,9 +143,21 @@ Output: Does there exist f : V -> [k] such that for all {u, v} in E, f(u) != f(v
 
 Let N = number of repositories and M = total number of contributors across all repos.
 
-[Provide the Work formula as a function of N and M, and explain:
-- Work for API calls
-- Work for data aggregation
-- Total expected Work]
+**Work breakdown:**
+- **Fetching repos:** 1 task (the initial sequential API call)
+- **Fetching contributors:** N tasks (one future per repository), each performing one API call. In HJlib abstract metrics, each future counts as 1 unit of work, giving N work units.
+- **Total HJlib work:** N + 1 (N futures + 1 main task)
+
+This matches the test assertion that `work <= repos + 1`.
+
+**Computational work (beyond HJlib metrics):**
+- **Result collection:** O(M) to iterate through all future results and build the combined user list
+- **Stream aggregation:** O(M) for the groupingBy and summingInt operations
+- **Sorting:** O(U * log(U)) where U = number of unique users (U <= M)
+- **Total computational work:** O(N + M + U * log(U))
+
+**Parallelism:**
+- **Critical Path Length (CPL):** 2 (the main task creates all futures, then waits for the longest one to complete)
+- **Parallelism ratio:** (N + 1) / 2, meaning with sufficient processors, the parallel version achieves approximately N/2 speedup over sequential execution of the API calls
 
 ---

Duration

4m 26s

Turns

Cost

$0.94

Status

Success

API Time

4m 12s

Tokens

595.2K

Claude Code

v2.1.63

Sub-Model Usage

Model	Input	Output	Cache Read	Cost
claude-opus-4-6	14	11.0K	540.9K	$0.82
claude-haiku-4-5-20251001	38	5.4K	393.0K	$0.12