Agent Work: Functional Trees & Java Streams

Claude Haiku 4.5 · COMP 322: Fundamentals of Parallel Programming

COMP 322 Homework 1: Functional Programming & Java Streams

Total: 100 points

Overview

This assignment covers functional programming with trees and Java Streams for data processing.

Testing Your Solution

Use the grade tool to run tests:

# From the workspace directory
bin/grade .

# Or from the project root
bin/grade workspaces/agent_hw1

Tests are run in a Docker container with Maven and HJlib pre-configured.

---

Part 1: Written Assignment (15 points)

Write a PDF report analyzing recursive Fibonacci complexity.

1.1 Recursive Fibonacci (15 points)

Consider the Java code shown below to compute the Fibonacci function using recursion:

public class RecursiveFib {
    public static int fib(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else return fib(n - 1) + fib(n - 2);
    }
}

1.1.1 Recursive Fibonacci Complexity (5 points)

What is the formula (exact answer) for the *total work* performed by a call to fib(n)? Assume that a single call to fib() (without any recursive calls inside) has a total WORK of 1. Include an explanation of the analysis, and state what expression you get for WORK(n) as a function of n. The exact answer should not be recursive.

1.1.2 Memoized Fibonacci Complexity (10 points)

Consider the memoized version:

public class MemoizationFib {
    private static final int MaxMemo = 1000000;
    private static final Lazy<Integer>[] memoized =
        IntStream.range(0, MaxMemo)
        .mapToObj(e->Lazy.of(()->fib(e)))
        .toArray(Lazy[]::new);

    public static int fib(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n >= MaxMemo) return fib(n - 1) + fib(n - 2);
        else return memoized[n-1].get() + memoized[n-2].get();
    }
}

(5 points) What is the big-O for WORK performed by fib(n) when called for the very first time?
(5 points) After many random calls to fib(k), what is the big-O for expected WORK of a subsequent fib(n) call?

---

Part 2: Programming Assignment (85 points)

2.1 Functional Trees

Write solutions in src/main/java/edu/rice/comp322/solutions/TreeSolutions.java.

1. Problem 1: Write a recursive sum function to calculate the sum of all node values in a Tree<Integer>. No higher-order functions, mutation, or loops allowed.

2. Problem 2: Calculate the same sum using higher-order GList functions: map, fold, and filter.

3. Problem 3: Complete the higher-order fold function for trees. (Already implemented in Tree.java)

4. Problem 4: Use fold to calculate the sum of tree nodes.

2.2 Java Streams: Sales Data

Write solutions in src/main/java/edu/rice/comp322/solutions/StreamSolutions.java.

For each problem, implement both sequential and parallel versions using Java Streams API.

Stream Operations:

1. Calculate maximum possible revenue from February online sales (full price) 2. Get order IDs of the 5 most recently placed orders 3. Count the number of distinct customers making purchases 4. Calculate total discount for March 2021 orders

Data Map Creation:

5. Create mapping: customer IDs -> total amount spent (full price) 6. Create mapping: product categories -> average item cost 7. Create mapping: Tech product IDs -> customer IDs who ordered them 8. Create mapping: tier-0 customer IDs -> sales utilization rate

Data Model

The database contains Products, Orders, and Customers. Access data via repositories:

productRepo.findAll().stream()   // Sequential stream of products
orderRepo.findAll().parallelStream()  // Parallel stream of orders
customerRepo.findAll().stream()  // Stream of customers

---

Scoring

60 points: Programming solutions (12 problems)
10 points: Coding style and documentation
15 points: Report comparing sequential vs parallel Java Streams performance

---

Files to Implement

src/main/java/edu/rice/comp322/solutions/TreeSolutions.java
src/main/java/edu/rice/comp322/solutions/StreamSolutions.java
src/main/java/edu/rice/comp322/provided/trees/Tree.java (fold method in Node class)

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

TreeSolutions.java694 B

java

package edu.rice.comp322.solutions;

import edu.rice.comp322.provided.trees.GList;
import edu.rice.comp322.provided.trees.Tree;

public class TreeSolutions {

    // @TODO Implement tree sum
    public static Integer problemOne(Tree<Integer> tree) {
        return null;
    }

    // @TODO Implement tree sum using higher order list functions
    public static Integer problemTwo(Tree<Integer> tree) {
        return null;
    }

    /*
     * Problem 3's solution should be written in the Tree.java class at line 118.
     */

    // @TODO Calculate the sum of the elements of the tree using tree fold
    public static Integer problemFour(Tree<Integer> tree) {
        return null;
    }

}

TreeSolutions.java694 B

java

package edu.rice.comp322.solutions;

import edu.rice.comp322.provided.trees.GList;
import edu.rice.comp322.provided.trees.Tree;

public class TreeSolutions {

    // @TODO Implement tree sum
    public static Integer problemOne(Tree<Integer> tree) {
        return null;
    }

    // @TODO Implement tree sum using higher order list functions
    public static Integer problemTwo(Tree<Integer> tree) {
        return null;
    }

    /*
     * Problem 3's solution should be written in the Tree.java class at line 118.
     */

    // @TODO Calculate the sum of the elements of the tree using tree fold
    public static Integer problemFour(Tree<Integer> tree) {
        return null;
    }

}

Tree.java5.5 KB

java

package edu.rice.comp322.provided.trees;

import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.NoSuchElementException;
import java.util.function.Predicate;

/**
 * A very simple functional tree implementation
 * A tree can either be Empty, or a Node.
 */
public interface Tree<T> {

    /**
     * Create a new empty tree of the given parameter type.
     */
    @SuppressWarnings("unchecked")
    static <T> Tree<T> empty() {
        return (Tree<T>) Tree.Empty.SINGLETON;
    }

    /**
     * Builder for making a tree node.
     */
    static <T> Tree<T> makeNode(T value, GList<Tree<T>> children) {
        return new Node<>(value, children);
    }

    /**
     * Getter for value.
     */
    T value();

    /**
     * Getter for the children.
     */
    GList<Tree<T>> children();

    /**
     * Return true if this is an empty tree.
     */
    boolean isEmpty();

    /** Returns a new tree equal to the old tree with the function applied to each value. */
    <R> Tree<R> map(Function<T, R> f);

    /** Returns a new tree equal to all the nodes in the old tree satisfying the predicate. */
    Tree<T> filter(Predicate<T> p);

    <U> U fold(U zero,  BiFunction<U, T, U> operator);


    /**
     * Class Node implements a non-empty tree.
     * A Node has a value, and a GList of children (which could be empty).
     */
    class Node<T> implements Tree<T> {
        private final T value;
        private final GList<Tree<T>> children;

        public Node(T value, GList<Tree<T>> children) {
            this.value = value;
            this.children = children;
        }

        @Override
        public T value() {
            return value;
        }

        @Override
        public GList<Tree<T>> children() {
            return children;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        /**
         * It should return a new tree equal to the old tree with the function applied to each value.
         * @param f   the function for mapping every value in the tree
         * @param <R> the type of the values in the new tree
         * @return the tree with the exact same structure as the original one, but with f applied to each value
         */
        @Override
        public <R> Tree<R> map(Function<T, R> f) {
            return Tree.makeNode(f.apply(value()), children().map(tree -> tree.map(f)));
        }

        /**
         * It should return a new tree that only contains the nodes whose values satisfy the predicate.
         * @param p   the predicate for determining if the node should stay in the tree
         */
        @Override
        public Tree<T> filter(Predicate<T> p) {
            var newChildren = children().map(child -> child.filter(p)).filter(child -> !child.isEmpty());
            if (p.test(value())) {
                return makeNode(value(), newChildren);
            } else if (newChildren.isEmpty()) {
                return empty();
            } else {
                return makeTreeHelper(newChildren);
            }
        }

        /**
         * @TODO Implement this function to complete problem 3 of section one of hw 1
         *
         * @param zero The base value to start the fold operation with. Should be of type U.
         * @param operator The function for how to combine a new tree's value into the accumulated
         *                 value.
         * @param <U> The return type as well as the type of the zero value.
         * @return a value of type U representing the folding of the entire tree.
         */
        @Override
        public <U> U fold(U zero, BiFunction<U, T, U> operator) {
            U result = operator.apply(zero, value());
            return children().foldLeft(result, (acc, child) -> child.fold(acc, operator));
        }

        /**
         * A helper function for making a tree out of a GList of trees. It picks the root of the first
         * tree as the root of the result, then adds the remaining trees to the children of the first tree
         */
        private Tree<T> makeTreeHelper(GList<Tree<T>> treeList) {
            if (treeList.isEmpty()) {
                return empty();
            } else {
                var firstChild = treeList.head();
                return makeNode(firstChild.value(), firstChild.children().appendAll(treeList.tail()));
            }
        }

    }

    /**
     * The empty tree.
     */
    class Empty<T> implements Tree<T> {
        /**
         * The constructor is private.
         */
        private Empty() {}

        /**
         * There is only one empty tree.
         */
        private static final Tree<?> SINGLETON = new Empty<>();

        /**
         * The map for an empty tree is simple: just return an empty tree.
         */
        @Override
        public <R> Tree<R> map(Function<T, R> f) {
            return empty();
        }

        /**
         * The filter for an empty tree is simple: just return an empty tree.
         */
        @Override
        public Tree<T> filter(Predicate<T> p) {
            return empty();
        }

        @Override
        public <U> U fold(U zero, BiFunction<U, T, U> operator) {
            return zero;
        }

        @Override
        public T value() {
            throw new NoSuchElementException("can't get a value from an empty tree");
        }

        @Override
        public GList<Tree<T>> children() {
            throw new NoSuchElementException("can't get children from an empty tree");
        }

        @Override
        public boolean isEmpty() {
            return true;
        }

    }
}

Tree.java5.5 KB

java

package edu.rice.comp322.provided.trees;

import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.NoSuchElementException;
import java.util.function.Predicate;

/**
 * A very simple functional tree implementation
 * A tree can either be Empty, or a Node.
 */
public interface Tree<T> {

    /**
     * Create a new empty tree of the given parameter type.
     */
    @SuppressWarnings("unchecked")
    static <T> Tree<T> empty() {
        return (Tree<T>) Tree.Empty.SINGLETON;
    }

    /**
     * Builder for making a tree node.
     */
    static <T> Tree<T> makeNode(T value, GList<Tree<T>> children) {
        return new Node<>(value, children);
    }

    /**
     * Getter for value.
     */
    T value();

    /**
     * Getter for the children.
     */
    GList<Tree<T>> children();

    /**
     * Return true if this is an empty tree.
     */
    boolean isEmpty();

    /** Returns a new tree equal to the old tree with the function applied to each value. */
    <R> Tree<R> map(Function<T, R> f);

    /** Returns a new tree equal to all the nodes in the old tree satisfying the predicate. */
    Tree<T> filter(Predicate<T> p);

    <U> U fold(U zero,  BiFunction<U, T, U> operator);


    /**
     * Class Node implements a non-empty tree.
     * A Node has a value, and a GList of children (which could be empty).
     */
    class Node<T> implements Tree<T> {
        private final T value;
        private final GList<Tree<T>> children;

        public Node(T value, GList<Tree<T>> children) {
            this.value = value;
            this.children = children;
        }

        @Override
        public T value() {
            return value;
        }

        @Override
        public GList<Tree<T>> children() {
            return children;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }

        /**
         * It should return a new tree equal to the old tree with the function applied to each value.
         * @param f   the function for mapping every value in the tree
         * @param <R> the type of the values in the new tree
         * @return the tree with the exact same structure as the original one, but with f applied to each value
         */
        @Override
        public <R> Tree<R> map(Function<T, R> f) {
            return Tree.makeNode(f.apply(value()), children().map(tree -> tree.map(f)));
        }

        /**
         * It should return a new tree that only contains the nodes whose values satisfy the predicate.
         * @param p   the predicate for determining if the node should stay in the tree
         */
        @Override
        public Tree<T> filter(Predicate<T> p) {
            var newChildren = children().map(child -> child.filter(p)).filter(child -> !child.isEmpty());
            if (p.test(value())) {
                return makeNode(value(), newChildren);
            } else if (newChildren.isEmpty()) {
                return empty();
            } else {
                return makeTreeHelper(newChildren);
            }
        }

        /**
         * @TODO Implement this function to complete problem 3 of section one of hw 1
         *
         * @param zero The base value to start the fold operation with. Should be of type U.
         * @param operator The function for how to combine a new tree's value into the accumulated
         *                 value.
         * @param <U> The return type as well as the type of the zero value.
         * @return a value of type U representing the folding of the entire tree.
         */
        @Override
        public <U> U fold(U zero, BiFunction<U, T, U> operator) {
            U result = operator.apply(zero, value());
            return children().foldLeft(result, (acc, child) -> child.fold(acc, operator));
        }

        /**
         * A helper function for making a tree out of a GList of trees. It picks the root of the first
         * tree as the root of the result, then adds the remaining trees to the children of the first tree
         */
        private Tree<T> makeTreeHelper(GList<Tree<T>> treeList) {
            if (treeList.isEmpty()) {
                return empty();
            } else {
                var firstChild = treeList.head();
                return makeNode(firstChild.value(), firstChild.children().appendAll(treeList.tail()));
            }
        }

    }

    /**
     * The empty tree.
     */
    class Empty<T> implements Tree<T> {
        /**
         * The constructor is private.
         */
        private Empty() {}

        /**
         * There is only one empty tree.
         */
        private static final Tree<?> SINGLETON = new Empty<>();

        /**
         * The map for an empty tree is simple: just return an empty tree.
         */
        @Override
        public <R> Tree<R> map(Function<T, R> f) {
            return empty();
        }

        /**
         * The filter for an empty tree is simple: just return an empty tree.
         */
        @Override
        public Tree<T> filter(Predicate<T> p) {
            return empty();
        }

        @Override
        public <U> U fold(U zero, BiFunction<U, T, U> operator) {
            return zero;
        }

        @Override
        public T value() {
            throw new NoSuchElementException("can't get a value from an empty tree");
        }

        @Override
        public GList<Tree<T>> children() {
            throw new NoSuchElementException("can't get children from an empty tree");
        }

        @Override
        public boolean isEmpty() {
            return true;
        }

    }
}

COMP 322 Homework 1: Functional Programming & Java Streams

Part 1: Written Questions (15 points)

1.1 Recursive Fibonacci Analysis

1.1.1 Recursive Fibonacci Complexity (5 points)

> What is the formula (exact answer) for the total work performed by a call to fib(n)? Assume that a single call to fib() (without any recursive calls inside) has a total WORK of 1. Include an explanation of the analysis, and state what expression you get for WORK(n) as a function of n. The exact answer should not be recursive.

Your Answer:

Recurrence Relation:

W(0) = 1 (base case: 1 function call)
W(1) = 1 (base case: 1 function call)
W(n) = W(n-1) + W(n-2) + 1 for n ≥ 2

The "+1" accounts for the current function call, plus the recursive calls to fib(n-1) and fib(n-2).

Solution and Analysis:

Computing the first few values:

W(0) = 1
W(1) = 1
W(2) = 1 + 1 + 1 = 3
W(3) = 3 + 1 + 1 = 5
W(4) = 5 + 3 + 1 = 9
W(5) = 9 + 5 + 1 = 15

We can observe that W(n) = 2·Fib(n+1) - 1, where Fib(k) is the standard Fibonacci sequence.

Exact Closed-Form Formula:

WORK(n) = 2·Fib(n+1) - 1

Or equivalently: WORK(n) = Θ(φ^n) where φ = (1 + √5)/2 ≈ 1.618 (the golden ratio)

This represents exponential growth, making recursive Fibonacci extremely inefficient for large n.

---

1.1.2 Memoized Fibonacci Complexity (10 points)

Consider the memoized version using Lazy evaluation:

public class MemoizationFib {
    private static final int MaxMemo = 1000000;
    private static final Lazy<Integer>[] memoized =
        IntStream.range(0, MaxMemo)
        .mapToObj(e->Lazy.of(()->fib(e)))
        .toArray(Lazy[]::new);

    public static int fib(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n >= MaxMemo) return fib(n - 1) + fib(n - 2);
        else return memoized[n-1].get() + memoized[n-2].get();
    }
}

a) First Call (5 points)

> What is the big-O for WORK performed by fib(n) when called for the very first time?

Your Answer:

Big-O Complexity: O(n)

Explanation: When fib(n) is called for the first time, it accesses memoized[n-1].get() and memoized[n-2].get(). The Lazy.of() creates lazy evaluations, and the .get() method forces evaluation. This triggers a chain of Lazy evaluations from memoized[n-1] down to memoized[0], and from memoized[n-2] down to memoized[0]. However, due to the Lazy optimization, each unique index is computed exactly once during the call chain. The work done is proportional to evaluating O(n) distinct Lazy objects, plus the arithmetic operations connecting them. Therefore, the first call to fib(n) takes O(n) time.

---

b) Subsequent Calls (5 points)

> After many random calls to fib(k), what is the big-O for expected WORK of a subsequent fib(n) call?

Your Answer:

Big-O Complexity: O(1) expected, O(n) worst-case

Explanation: After many random calls to fib(k), most Lazy objects in the memoized array up to some threshold have already been evaluated and cached. A subsequent call to fib(n) will access memoized[n-1].get() and memoized[n-2].get(). Since these Lazy objects are already evaluated (from previous calls), calling .get() on them returns the cached result in O(1) time. Thus, the subsequent call does O(1) work.

However, in the worst case where fib(n) is called with a value n much larger than any previous call, the algorithm would need to evaluate all Lazy objects from n down to the highest previously evaluated value, taking O(n) time.

For a uniform random distribution of calls, the expected complexity is O(1) for typical subsequent calls on previously-computed values.

---

Part 2: Performance Report (15 points)

A. Machine Description

System Specifications:

CPU: [Model name]
Cores: [Number of cores]
Memory: [RAM size]
OS: [Operating system]

---

B. Performance Measurements

Stream Operations Timing (milliseconds):

Operation	Sequential	Parallel	Speedup
Max February Revenue
Recent Order IDs
Distinct Customers
March Discounts
Customer Spend Map
Category Avg Cost
Tech Product Orders
Tier-0 Utilization

Test Configuration:

Data size: [Number of records]
Warm-up runs: [Number]
Measured runs: [Number]

---

C. Speedup Analysis

[Calculate and discuss the speedup ratios. Which operations benefit most from parallelization? Which show minimal improvement?]

---

D. Discussion

[Analyze your results. Consider:

Why do some operations show better speedup than others?
What is the overhead of parallel stream creation?
At what data size does parallel processing become beneficial?
How does the nature of the operation (aggregation vs. collection) affect parallelism?]

---

COMP 322 Homework 1 — Grading Report

---

Part 1: Written Questions (15 points)

1.1.1 Recursive Fibonacci Complexity — 5/5

Feedback: Excellent answer. The student correctly identifies the recurrence relation W(n) = W(n-1) + W(n-2) + 1 with base cases W(0) = W(1) = 1, computes several values to verify the pattern, and arrives at the correct exact closed-form formula WORK(n) = 2·Fib(n+1) − 1. The asymptotic bound Θ(φⁿ) is also correctly stated. The derivation is clear and well-organized.

---

1.1.2a Memoized Fibonacci — First Call — 5/5

Feedback: Correct answer of O(n) with a clear and accurate explanation. The student correctly explains that Lazy evaluation ensures each index is computed exactly once, resulting in O(n) distinct evaluations cascading down from memoized[n-1] to the base cases. Well-reasoned.

---

1.1.2b Memoized Fibonacci — Subsequent Calls — 5/5

Feedback: Correct answer of O(1) expected. The student correctly explains that after many random calls, the Lazy objects are already evaluated and cached, so .get() returns in O(1). The additional note about O(n) worst-case for a previously-uncomputed large value demonstrates strong understanding beyond what was required.

---

Part 2: Performance Report (15 points)

Section A: Machine Description — 0/3

Feedback: The submission contains only placeholder text ([Model name], [Number of cores], [RAM size], [Operating system]). No actual machine specifications were provided.

---

Section B: Performance Measurements — 0/6

Feedback: The timing table is entirely empty — all data cells are blank. No performance measurements were collected or reported for any stream operation, sequential or parallel.

---

Section C: Speedup Analysis — 0/3

Feedback: Only the placeholder prompt text remains. No speedup calculations (T_seq / T_par) were performed or discussed.

---

Section D: Discussion — 0/3

Feedback: Only the template's suggested discussion prompts remain. No actual analysis or discussion of results was provided.

---

Summary

Section	Score	Max	Notes
1.1.1 Recursive Fib Complexity	5	5	Perfect — correct formula, derivation, and asymptotics
1.1.2a Memoized Fib (First Call)	5	5	Correct O(n) with clear lazy-evaluation explanation
1.1.2b Memoized Fib (Subsequent)	5	5	Correct O(1) expected with insightful worst-case note
Report A: Machine Description	0	3	Empty — only placeholders
Report B: Performance Measurements	0	6	Empty — no data collected
Report C: Speedup Analysis	0	3	Empty — no calculations
Report D: Discussion	0	3	Empty — no analysis
Total	15	30

Overall Comments: The theoretical portion (Part 1) is outstanding — all three questions are answered correctly with clear, well-structured explanations that demonstrate strong understanding of both the recursive and memoized Fibonacci complexity. However, the performance report (Part 2) is entirely incomplete, consisting only of empty templates with placeholder text. No measurements, calculations, or analysis were provided. The student should run the sequential and parallel stream implementations, record timing data, compute speedups, and discuss the results.

Total: 15/30

.mcp.json

diff --git a/.mcp.json b/.mcp.json
deleted file mode 100644
index 8c7fe4d..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_hw1_haiku"
-      ]
-    }
-  }
-}
\ No newline at end of file

Agent Work: Functional Trees & Java Streams

COMP 322 Homework 1: Functional Programming & Java Streams

Overview

Testing Your Solution

Part 1: Written Assignment (15 points)

1.1 Recursive Fibonacci (15 points)

1.1.1 Recursive Fibonacci Complexity (5 points)

1.1.2 Memoized Fibonacci Complexity (10 points)

Part 2: Programming Assignment (85 points)

2.1 Functional Trees

2.2 Java Streams: Sales Data

Data Model

Scoring

Files to Implement

COMP 322 Homework 1: Functional Programming & Java Streams

Part 1: Written Questions (15 points)

1.1 Recursive Fibonacci Analysis

1.1.1 Recursive Fibonacci Complexity (5 points)

1.1.2 Memoized Fibonacci Complexity (10 points)

Part 2: Performance Report (15 points)

A. Machine Description

B. Performance Measurements

C. Speedup Analysis

D. Discussion

COMP 322 Homework 1 — Grading Report

Part 1: Written Questions (15 points)

1.1.1 Recursive Fibonacci Complexity — 5/5

1.1.2a Memoized Fibonacci — First Call — 5/5

1.1.2b Memoized Fibonacci — Subsequent Calls — 5/5

Part 2: Performance Report (15 points)

Section A: Machine Description — 0/3

Section B: Performance Measurements — 0/6

Section C: Speedup Analysis — 0/3

Section D: Discussion — 0/3

Summary

Sub-Model Usage