BSCS BenchAgent Work: GitHub Contributions (Parallel)
Claude Haiku 4.5 · 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_hw2To 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
finishorasync - 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(implementloadContributorsPar)src/main/java/edu/rice/comp322/LoadContributors.java(parallel method)
--- *COMP 322: Fundamentals of Parallel Programming, Rice University*
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);
}
}
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);
}
}
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);
}
}
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:
// Parallel IsKColorable Algorithm using finish and async
finish(() -> {
for (each assignment f in all k^n possible assignments) {
async(() -> {
boolean colorable = true;
for (each edge {u,v} in E) {
if (f(u) == f(v)) {
colorable = false;
break;
}
}
if (colorable) {
// Signal that we found a valid coloring
// Use a shared variable to store result
found.compareAndSet(false, true);
}
});
}
});
// Return true if found flag was set
return found.get();Parallelization Strategy:
- Each assignment is checked in a separate async task, allowing multiple assignments to be validated concurrently
- The finish block ensures all async tasks complete before returning
- A shared AtomicBoolean
foundtracks whether any valid coloring was discovered - Tasks can exit early once a valid coloring is found (the
foundflag prevents further checking)
Correctness: The algorithm maintains correctness because:
- All k^n assignments are evaluated (either sequentially or in parallel)
- The finish ensures synchronization - we don't return until all async tasks complete
- Using AtomicBoolean ensures thread-safe access to the result
- The sequential per-edge checking within each task remains correct
---
1.1.2 Total Work Analysis (5 points)
> What is the big-O for total WORK?
Your Answer:
O(k^n · |E|) where n = |V|
Explanation:
- Total assignments to check: k^n (each of n vertices can be assigned one of k colors)
- Work per assignment: O(|E|) (must check all edges to determine validity, worst case we check all before finding an invalid edge)
- Total work is the product: O(k^n · |E|)
This is the same as the sequential version because we must ultimately check the validity of each assignment against all edges. Parallelization improves the span (critical path length) but not the total work.
---
1.1.3 Larger Work Than Sequential? (5 points)
> Can your parallel algorithm have LARGER WORK than sequential? Explain.
Your Answer:
No, the parallel algorithm cannot have larger WORK than the sequential version.
Explanation:
- Both algorithms check exactly the same k^n assignments
- Both perform the same edge-checking logic for each assignment: O(|E|) per assignment
- Total WORK is the sum of all computations: k^n · |E|
- WORK is a fundamental property of the algorithm and doesn't increase with parallelization
- However, if we add synchronization overhead (atomic operations, thread management, etc.), that could increase total work slightly in practice, but theoretically the essential algorithm work remains O(k^n · |E|)
---
1.1.4 Smaller Work Than Sequential? (5 points)
> Can your parallel algorithm have SMALLER WORK than sequential? Explain.
Your Answer:
Yes, the parallel algorithm can have smaller WORK than sequential, but only if we consider early termination:
Without early termination:
- Both have same total WORK: O(k^n · |E|)
- Parallelization reduces SPAN (critical path length) but not WORK
With early termination (practical implementation):
- Parallel version: once one task finds a valid coloring, it can stop others from continuing
- Sequential version: must check more assignments even after finding a valid coloring
- Example: if a valid coloring exists at assignment 100 out of 1000 total, the sequential version checks 100, but a lucky parallel version might find it earlier and avoid ~900 assignments
- In this case, parallel WORK < sequential WORK
Key distinction:
- WORK = sum of all computation steps across all tasks (proportional to execution on infinite processors)
- SPAN = critical path length (execution on 1 processor would be sequential)
- Parallelization primarily reduces SPAN, not WORK
- WORK reduction only occurs with algorithmic optimizations like early termination
---
1.1.5 Data Race Analysis (5 points)
> Is a data race possible? If so, is it benign?
Your Answer:
Yes, a data race is possible on the `found` variable, but it is BENIGN.
Shared variable: found (AtomicBoolean tracking if a valid coloring was discovered)
Concurrent access pattern:
- Multiple async tasks read and potentially write to
foundconcurrently - Task 1 does:
found.compareAndSet(false, true) - Task 2 does:
found.compareAndSet(false, true)
The race:
- Tasks can have conflicting writes if multiple tasks try to set
found= true simultaneously - A task might read
found= false, then before writing, another task sets it to true
Why it's benign:
1. Atomicity: Using AtomicBoolean ensures the compareAndSet operation is atomic
2. Idempotence: Setting found = true multiple times has the same effect as setting it once
3. Correct result: The final value of found is correct regardless of race order
- If any task found a valid coloring, found = true
- If no task found a valid coloring, found = false
4. No correctness impact: The race never produces an incorrect result
Conclusion: This is a benign data race because the result is correct regardless of execution order.
---
Part 2: Report (15 points)
A. Algorithm Summary
Parallel Implementation of `loadContributorsPar`:
The implementation uses Java's CompletableFuture API to fetch contributor data from GitHub repositories concurrently:
1. Futures for Parallel API Calls:
- For each repository, a CompletableFuture is created using supplyAsync() with a shared ForkJoinPool
- Each future executes the GitHub API call concurrently: getRepContributorsCall(org, repoName).execute().body()
- Futures run asynchronously without blocking the UI thread
2. Stream-Based Aggregation:
- All futures are collected into a list
- futures.stream().map(CompletableFuture::join) waits for all futures to complete
- .filter() removes null results (failed API calls)
- .flatMap(List::stream) flattens the list of user lists into a single stream
- .collect(Collectors.toList()) collects into the final user list
3. Data Aggregation (Map-Reduce pattern):
- allUsers.stream().collect(Collectors.groupingBy(u -> u.login, Collectors.summingInt(u -> u.contributions)))
- Groups users by login (de-duplicates)
- Sums contributions for each unique user across all repositories
- Converts back to User objects
4. Sorting:
- Final list sorted by contributions in descending order using comparator (o1, o2) -> o2.contributions - o1.contributions
---
B. Correctness and Data-Race-Free Justification
1. Same results as sequential version:
- Both versions fetch the same set of repositories
- Both versions fetch contributors for each repository
- Both perform identical aggregation logic (grouping by login, summing contributions)
- Both sort results identically (descending by contributions)
- Only difference is parallelization of API calls, which is commutative
2. Data-race-free design:
- Each
CompletableFutureoperates on independent data (different repository) - No shared mutable state during API calls
- User list aggregation happens sequentially after all futures complete (no concurrent writes)
- Stream operations are functional (no mutable state)
- Even if futures complete in any order, the final aggregation produces identical results
3. Correct aggregation:
groupingBy(u -> u.login)ensures each unique user appears once in the mapsummingInt(u -> u.contributions)correctly adds contributions across repos- The final User objects represent the true total contributions per user
- Example: if user "alice" contributed 5 times to repo1 and 3 times to repo2, the final result shows alice with 8 contributions
Concurrency Safety: Java's CompletableFuture and Collectors.groupingBy() handle all synchronization internally. The main thread waits for all futures to complete with .join() before proceeding to aggregation.
---
C. Work Analysis
Let N = number of repositories and M = total number of contributors across all repos.
Work breakdown:
1. Initial API call to fetch repositories: O(1) work - Single synchronous call to get all repos
2. Parallel API calls for contributors: O(N) work total - N futures created, each makes one HTTP request - Each request is O(1) in terms of work units (blocking I/O, but counted as unit work) - Total: N API calls = O(N) work
3. Collecting future results: O(N) work - Joining N futures: O(N) - Flattening M user objects from all repos: O(M)
4. Data aggregation (grouping and summing): O(M) work - Stream operation over M total contributor entries - Each entry processed once: group lookup (O(1)) and sum update (O(1))
5. Sorting: O(U log U) work where U = unique users - U ≤ M (bounded by total contributors) - Sorting by contributions: O(U log U) comparison and swaps
Total expected WORK: O(N + M + U log U) = O(N + M log M) (worst case when U ≈ M)
This is optimal because:
- We must make N API calls to fetch all repositories' contributors
- We must process all M contributor entries at least once to aggregate them
- We must sort the results
The parallelization reduces SPAN (wall-clock time) from O(N) to O(1) when N repos can be fetched simultaneously, but doesn't reduce the total WORK because all N API calls must still execute.
COMP 322 Homework 2 - Grading Report
---
Question 1.1.1: Parallel Version (10 points)
Score: 10/10
Excellent answer. The student provides a correct parallel version with all key elements:
- async for each assignment in the outer loop ✓
- finish block to wait for all async tasks ✓
- AtomicBoolean with
compareAndSetfor thread-safe access to the shared result ✓ - Sequential inner edge-checking loop preserved (retaining the
breakoptimization) ✓ - Clear explanation of parallelization strategy and correctness justification ✓
The code closely matches the reference solution and the accompanying explanation is thorough.
---
Question 1.1.2: Total Work Analysis (5 points)
Score: 5/5
Correct answer: O(k^n · |E|) where n = |V|. The explanation clearly decomposes the work into k^n assignments × O(|E|) edge checks per assignment. The student also correctly notes that parallelization improves span but not total work.
---
Question 1.1.3: Larger Work Than Sequential? (5 points)
Score: 2/5
Incorrect answer. The student says No, but the correct answer is Yes.
The critical insight the student misses: the sequential algorithm can terminate early at line 8 (return True) as soon as it finds a valid coloring, skipping all remaining assignments. The parallel version, however, spawns all k^V async tasks upfront (or in large batches). Even with the AtomicBoolean early-exit check, asyncs that have already started will continue running and complete their edge checking. This means the parallel version can perform significantly more total WORK than the sequential version when a valid coloring is found early in the assignment enumeration.
The student states "Both algorithms check exactly the same k^n assignments," which is false — the sequential version can skip assignments via early return. The student does mention synchronization overhead as a minor practical concern, earning partial credit for engaging with the concept.
Per rubric: *"2 points: Incorrect answer (No) but shows understanding of parallelism."*
---
Question 1.1.4: Smaller Work Than Sequential? (5 points)
Score: 2/5
Incorrect answer. The student says Yes (with early termination), but the correct answer is No.
The student argues that "a lucky parallel version might find [a valid coloring] earlier and avoid ~900 assignments." This confuses SPAN (wall-clock time) with WORK (total operations). The sequential version *also* has early termination — it stops at line 8 as soon as it finds a valid coloring, checking only those assignments up to the first valid one. The parallel version spawns all (or many) asyncs, so its total WORK is at least as much as the sequential version's. Parallelism reduces the time to find the answer (SPAN), not the total number of operations (WORK).
Notably, the student correctly states the WORK/SPAN distinction in their "Key distinction" section, yet applies it incorrectly in their early-termination analysis. The student's answers to 1.1.3 and 1.1.4 are essentially swapped from the correct answers, suggesting a fundamental confusion about how early termination interacts differently with sequential vs. parallel execution.
Per rubric: *"2 points: Incorrect answer (Yes) but discusses relevant concepts."*
---
Question 1.1.5: Data Race Analysis (5 points)
Score: 4/5
The student correctly identifies:
- Yes, a data race is possible on the shared
foundvariable ✓ - Yes, it is benign because only
Trueis ever written (idempotent) ✓ - Concurrent reads/writes don't affect correctness ✓
Minor issue: The student's analysis is somewhat self-contradictory. They use AtomicBoolean with compareAndSet in their algorithm (which by definition *prevents* data races through synchronization), yet still claim a data race exists. The reference solution clarifies that AtomicBoolean *eliminates* the race, but the race would be benign even without it. Despite this conceptual muddiness, the core analysis is correct — the student understands the access pattern and why it's benign.
---
Report Section A: Algorithm Summary (5 points)
Score: 5/5
Excellent, thorough description covering:
- Futures for parallel API calls:
CompletableFuture.supplyAsync()withForkJoinPool✓ - Stream-based aggregation:
groupingBy+summingIntfor de-duplication ✓ - UI non-blocking: Async execution prevents UI freeze ✓
- Clear 4-step breakdown (futures → collection → aggregation → sorting) ✓
---
Report Section B: Correctness Justification (5 points)
Score: 5/5
Comprehensive justification covering:
- Functional equivalence: Same repos, same aggregation logic, same sorting ✓
- Data-race freedom: Independent futures, no shared mutable state, sequential aggregation after join ✓
- Correct aggregation:
groupingByensures uniqueness,summingIntcorrectly sums contributions ✓ - Concrete example (alice with contributions across repos) strengthens the argument ✓
---
Report Section C: Work Analysis (5 points)
Score: 5/5
Correct and thorough analysis:
- Variables defined: N = repos, M = contributors, U = unique users ✓
- Work breakdown: O(1) initial call + O(N) API calls + O(M) aggregation + O(U log U) sorting ✓
- Total: O(N + M log M) ✓
- Parallelism insight: Reduces SPAN from O(N) to O(1) for API calls, but total WORK unchanged ✓
---
Summary
| Question | Score | Max | Notes | ||
|---|---|---|---|---|---|
| 1.1.1 Parallel Version | 10 | 10 | Excellent — correct async/finish with AtomicBoolean | ||
| 1.1.2 Total Work | 5 | 5 | Correct: O(k^V · \ | E\ | ) |
| 1.1.3 Larger Work? | 2 | 5 | Wrong (said No); missed sequential early termination | ||
| 1.1.4 Smaller Work? | 2 | 5 | Wrong (said Yes); confused SPAN reduction with WORK reduction | ||
| 1.1.5 Data Race | 4 | 5 | Correct identification + benign; minor atomicity confusion | ||
| Report A: Algorithm Summary | 5 | 5 | Thorough and clear | ||
| Report B: Correctness | 5 | 5 | Comprehensive justification | ||
| Report C: Work Analysis | 5 | 5 | Correct with good breakdown | ||
| Total | 38 | 45 |
Overall Comments: Strong submission with excellent code, report sections, and most written answers. The main weakness is the WORK analysis for questions 1.1.3 and 1.1.4, where the answers are effectively reversed. The student understands the WORK/SPAN distinction in principle but misapplies it when reasoning about early termination — failing to recognize that sequential early termination (line 8's return True) means the sequential version can do *less* work than the parallel version (not more), and that parallel execution cannot reduce total WORK below the sequential baseline.
Total: 38/45
diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index d42bcdb..0000000
--- a/.mcp.json
+++ /dev/null
@@ -1,11 +0,0 @@
-{
- "mcpServers": {
- "bscs-bench": {
- "command": "/Users/bebe/Code/bscs-bench/bin/bscs-mcp",
- "args": [
- "--workspace",
- "/Users/bebe/Code/bscs-bench/workspaces/comp322_hw2_haiku"
- ]
- }
- }
-}
\ No newline at end of file
Sub-Model Usage
| Model | Input | Output | Cache Read | Cost |
|---|---|---|---|---|
| claude-haiku-4-5-20251001 | 198 | 27.3K | 1.6M | $0.37 |