Paul Bodily About Courses Research Outreach Tips for Communicating Teaching Philosophy Vitae

Assignment Descriptions

A substantial portion of our in-class discussions will be based off of your experience with these assignments. Ultimately, the goal will be to synthesize your experiences with the assignments into a final group paper and presentation. I anticipate that several opportunities to participate in publishing could arise from this work.

All written assignments are to be done with Overleaf or LetX and be neat and professional. Good writing, grammar, punctuation, etc. are important and can affect your grade.

Virtual Intro

A link for joining us on Discord is posted on Canvas. Once joined, use the "introductions" channel to post a brief introduction of yourself and your skills that are relevant to our class goals. In your introduction, be sure to specifically address the following questions (try to be as specific as you can):

  1. What experience do you have with Redux, if any?
  2. What experience do you have with computational theory, especially NP-completeness?
  3. Which LLMs do you/have you used and for what purposes?

Use the "computational creativity theory" channel to post your preliminary thoughts on the controversial question: "Do LLMs exhibit 'creative' behavior?" Be sure to support your position with evidence and reasoning. You will be asked to revisit this question at the end of the semester.

Problem Brainstorming

You should NOT use an LLM in this assignment. The purpose of this assignment is to get you to think about the problem you want to implement in Redux and to do some preliminary research on it. You will be asked to use an LLM in the next assignment. The expertise you develop in this assignment will be valuable to allow you to evaluate the LLM's performance in the next assignment.

Use the "project-ideas" channel to post two or more NP-complete problems that you would be interested in focusing on for a class project that aren't already in Redux. Here are some places to look for NP-complete problems:

The success of your group project, which will occupy most of the semester and your grade, will depend heavily on the problem you choose to investigate. As such, use the following questions to guide you in choosing a problem that will work well for our purposes. In your post for this assignment, please motivate your problem selection with some comments about the following criteria as they relate to your problem (in what follows, "published" simply means "readily available in the public domain", not necessarily published in a journal or conference proceedings):

  1. Ensure that the problem is, in fact, NP-complete (not NP-Hard, not polynomial). Part of your project will involve mapping reductions, a phenomenon uniquely relevant to NP-complete problems. Remember that many NP-complete problems are decision problems with an NP-hard optimization variant. If your problem is an optimization problem, it's probably not NP-complete.
  2. Shoot for problems with simple problem instance representations (i.e., simple inputs). For example, is the input just a boolean formula or simple data structure (i.e., set, list, graph)? Or does it require a litany of input parameters of disparate types?
  3. Do there exist published solution algorithms that solve (either optimally or suboptimally) the problem? You will implement existing solution algorithms and you will ask an LLM to implement existing solutions as part of the group project. The more obscure your problem, the fewer published algorithms and the harder this task will be for you and for the LLM. Note that solutions for the NP-hard variant are generally easily adapted to solve the NP-complete variant of the same problem by simply adding an early cut-off criteria once the algorithm finds a solution better than the threshold specified by the decision problem.
  4. Do there exist published mapping reductions (aka reduction function) from an NP-complete problem that is already in Redux? Note that reductions are not commutative, so a reduction from A to B is very different from B to A. As part of your group project you will implement and ask an LLM to implement a reduction from a problem in Redux (otherwise you'll have to implement the other problem, too). You do not want to have to come up with a mapping reduction on your own (unless you want to do it as a Master's thesis or PhD dissertation). This may take some digging around to find. Come to me if you need help. Ideally, the reduction is also accompanied by a proof of correctness.

LLM Problem Brainstorming

Use an LLM, prompted with the criteria from the previous assignment, to generate a list of NP-complete problems that could work well for the group project. Post your findings in the "project-ideas" channel. Comment on any overlap between the problems discovered by students without the aid of LLM (in the previous assignment) and those suggested by the LLMs. Work together with other students to collectively validate which of the problems listed by the LLMs meet the criteria for a good project problem.

At this stage you should use the "project-ideas" channel to begin to identify 1-2 other students with whom you would like to form a group for the project and begin narrowing down which problem you want to work on. You will be asked to form a group and submit a project proposal in the next assignment.

Project Proposal

You should NOT use an LLM in this assignment. The purpose of this assignment is to get you to think about the problem you want to implement in Redux and to do some preliminary research on it. You will be asked to use an LLM in the next assignment. The expertise you develop in this assignment will be valuable to allow you to evaluate the LLM's performance in the next assignment.

Form a small group of 2-3 classmates and send me a link (with editing permissions) to an Overleaf document (use this template) or a LetX document (use this template) entitled "CS 4473/5573 Project Proposal: [Name of your NP-complete problem]" with the following information:

  1. Names of all group members
  2. Which NP-complete problem you will implement on redux.isu.edu. Include:
    1. Other names the problem goes by
    2. A succinct problem definition (see other problem definitions on redux.isu.edu for examples), including a URL to Wikipedia or another authoritative source where additional descriptive information about the problem can be found
    3. A citation in IEEE style and URL for where the problem was first published (do the best you can, see Redux for examples)
    4. Confirmation that the problem is a) NP-complete and b) not currently implemented in Redux (even by another name)
  3. A list of 3-5 published algorithms that solve your problem (this is an exploratory phase; you only have to implement one for the project). For each algorithm include:
    1. Other names the algorithm goes by
    2. A brief, one-line description of the algorithm (i.e., what algorithmic paradigm it uses)
    3. A citation in IEEE style and URL for where the problem was first published (do the best you can, this need not be a formal academic publication, see Redux for examples)
  4. A list of published mapping reductions from NP-complete problems that are already in Redux to the problem you chose. Treat this as an exploratory phase, finding as many as you can to give you options later. You will only have to implement one for the project. For each reduction, include:
    1. Which NP-complete problem in Redux the reduction maps from
    2. Confirmation that the reduction maps from an existing NP-complete problem in Redux to the problem you have chosen
    3. A citation in IEEE style and URL for where the reduction was first published (do the best you can, this need not be a formal academic publication, see Redux for examples)
  5. A list of LLM(s) your group could use to implement and assess the various tasks for your chosen problem. This, again, is an exploratory phase. You will only have to choose one for your trials. For each LLM, include:
    1. The name and version(s) of the LLM model
    2. What usage limits you have on the model
    3. How you have access to the model
    4. Any additional pros/cons for using the model
  6. What each member of the group contributed to this proposal assignment.

Keep track of how much time you spend on this assignment for later reference.

LLM Project Proposal

As a group, use your LLM to generate a project proposal for your chosen NP-complete problem. The prompt for the LLM should be as follows: "Generate a project proposal for a group of students in a computational creativity course to implement the [insert your problem name here] problem on redux.isu.edu. The proposal should be in LaTeX format, should be entitled "CS 4473/5573 LLM Project Proposal: [Name of your NP-complete problem]", and should include the following information:". Then copy and paste specification items 2-4 from the Project Proposal section above.

Copy and paste the LaTex output from the LLM into an Overleaf document (always using this template) or a LetX document (use this template) and share it with me (with editing permissions). Underline anything in the LLM proposal that is new with respect to the Human-Generated proposal.

In a separate Overleaf or LetX document entitled "CS 4473/5573 LLM vs. Human Project Proposal Comparison: [Name of your NP-complete problem]", with all team members listed as authors, report succinctly on the following questions, each in their own section named as follows:

  1. Link to the Human-Generated Proposal: What is the link for the Overleaf or LetX document containing your group's Human-Generated project proposal (the share link)?
  2. Link to the LLM-Generated Proposal: What is the link for the Overleaf or LetX document containing the output from the LLM?
  3. Prompt(s): What was the full prompt(s) you used for the LLM?
  4. Time Spent on the Human-Generated Proposal: How much time did your group spend on the Human-Generated proposal?
  5. Time Spent on the LLM-Generated Proposal: How much time did your group spend on the LLM-Generated proposal?
  6. Similarities (X%): What are the similarities between the Human-Generated and LLM-Generated project proposals? (Replace X with a rough estimate of how similar content-wise the two proposals are)
  7. Differences (X%): What are the differences between the Human-Generated and LLM-Generated project proposals (i.e., what aspects are unique to each)? (Replace X with a rough estimate of how different content-wise the two proposals are)
  8. Strengths of LLM-Generated Proposal: What are the general strengths of the LLM-Generated proposal relative to the Human-Generated Proposal?
  9. Weaknesses of LLM-Generated Proposal: What are the weaknesses of the LLM-Generated Proposal relative to the Human-Generated Proposal?
  10. LLM Hallucinations (X%): Verify all claims the proposal makes. What did the LLM hallucinate? (Replace X with a rough estimate of the percentage of hallucinated content)
  11. Choose one: If you had to choose only one of the two proposals to use for your project, which would you choose?
  12. LLM Feedback: Feed your Human-Generated Proposal into the LLM and ask it simply for feedback on your Proposal. Include a succinct summary of that feedback in this section of your comparison document.
  13. Thoughts on the LLM's feedback: What did you think of the LLM's feedback? Was it useful? Did it help you improve your implementation? Why or why not?
  14. Changes to the Human-Generated Proposal: What changes would you make to the Human-Generated Proposal based on the LLM-Generated Proposal and based on the LLM feedback?
  15. Link to Updated Final Proposal: Make a copy of your group's Human-Generated project proposal entitled "CS 4473/5573 Final Project Proposal: [Name of your NP-complete problem]" and update it with the insights from the LLM-Generated proposal and feedback. Include a link to this document here. All insights from the LLM-Generated proposal and feedback should be underlined in the updated Human-Generated proposal. List the LLM as an "author" in the updated proposal with its name also underlined as a reminder of what the underlined text represents.
  16. Lessons learned: What new takeaways about the LLM did you learn from this assignment? How much does the LLM seem to be aware of the problem you've chosen and its associated solution algorithms and reductions? How do you think the LLM's understanding of the problem compares to your own? Based on this assessment, how well do you expect the LLM to perform when asked to implement these tasks in Redux?
  17. Attributions: What did each member contribute to this assignment?

Group Battle

These are a chance for your group to meet with another group to foster "interdisciplinary" thinking. One group will begin by briefly explaining their current progress and challenges and then both groups will spend time brainstorming ways to overcome those challenges. Halfway through the class period, you will start over and focus on the second group's progress and challenges. I will wander around and listen in on the various "battles". Please be punctual and come prepared with talking points, questions, etc. for your "opponent" group and take advantage of their time and ideas.

Round Match 1 Match 2 Match 3 Match 4
Round 1 Team 1 vs Team 8 Team 2 vs Team 7 Team 3 vs Team 6 Team 4 vs Team 5
Round 2 Team 1 vs Team 7 Team 8 vs Team 6 Team 2 vs Team 5 Team 3 vs Team 4
Round 3 Team 1 vs Team 6 Team 7 vs Team 5 Team 8 vs Team 4 Team 2 vs Team 3
Round 4 Team 1 vs Team 5 Team 6 vs Team 4 Team 7 vs Team 3 Team 8 vs Team 2
Round 5 Team 1 vs Team 4 Team 5 vs Team 3 Team 6 vs Team 2 Team 7 vs Team 8
Round 6 Team 1 vs Team 3 Team 4 vs Team 2 Team 5 vs Team 8 Team 6 vs Team 7
Round 7 Team 1 vs Team 2 Team 3 vs Team 8 Team 4 vs Team 7 Team 5 vs Team 6

Systematic Literature Review

As a group (class?), and using the skills for Systematic Literature Review discussed in class, conduct a Systematic Literature Review on the topic of LLMs being used to programmatically implement NP-complete problems, problem instances, solution algorithms (of any kind), reduction proofs, and reduction algorithms. This would generally be too broad a topic for a Systematic Literature Review, but since LLMs have only been around for a few years, it should be feasible.

In an Overleaf or LetX document entitled "CS 4473/5573 Systematic Literature Review: [Name of your NP-complete problem]", report succinctly on the following questions, each in their own section named as follows:

  1. What were your PICO criteria for your Systematic Literature Review? (Population, Intervention, Comparison, Outcome)
  2. What were your research questions for your Systematic Literature Review? (3 to 5)
  3. What were your Boolean search strings for your Systematic Literature Review?
  4. What were your inclusion/exclusion criteria for your Systematic Literature Review? Time period? Language?
  5. What databases did you search for your Systematic Literature Review?
  6. How many rounds of snowballing did you do for your Systematic Literature Review? Include a figure characterizing the number of papers found in each step, like this:
    7. Identify Screen Snowball Database search IEEE n = __ · ACM n = __ · … Manual search n = __ Records after duplicate removal n = __ Duplicates removed n = __ Screen 1 — title and abstract retained n = __ Excluded (by criterion) n = __ Screen 2 — introduction and conclusions retained n = __ Excluded (by criterion) n = __ Screen 3 — full text retained n = __ · versions collapsed n = __ Excluded (by criterion) n = __ Primary studies from search n = __ (seed set for snowballing) Snowball round 1 — backward and forward examined n = __ · added n = __ · total n = __ Excluded n = __ Snowball round k — one node per round examined n = __ · added n = __ · total n = __ Excluded n = __ Final set of primary studies n = __ (stopping condition: ______)
  7. What were your results for your Systematic Literature Review? (Include a table of all papers found, including title, authors, year, journal/conference, and URL)

LLM Systematic Literature Review

You should NOT use an LLM in this assignment. The purpose of this assignment is to get you to think about the problem you want to implement in Redux and to do some preliminary research on it. You will be asked to use an LLM in the next assignment. The expertise you develop in this assignment will be valuable to allow you to evaluate the LLM's performance in the next assignment.

As a group, use your LLM to generate a Systematic Literature Review. The prompt for the LLM should be as follows: "Generate a Systematic Literature Review on the topic of LLMs being used to programmatically implement NP-complete problems, problem instances, solution algorithms (of any kind), reduction proofs, and reduction algorithms. The proposal should be in LaTeX format, should be entitled "CS 4473/5573 LLM Systematic Literature Review: [Name of your NP-complete problem]", and should include the following information:". Then copy and paste specification items 1-7 from the Systematic Literature Review section above.

Copy and paste the LaTex output from the LLM into an Overleaf document (always using this template) or a LetX document (use this template) and share it with me (with editing permissions). Underline anything in the LLM Systematic Literature Review that is new with respect to the Human-Generated Systematic Literature Review.

In a separate Overleaf or LetX document entitled "CS 4473/5573 LLM vs. Human Systematic Literature Review Comparison: [Name of your NP-complete problem]", with all team members listed as authors, report succinctly on the following questions, each in their own section named as follows:

  1. Link to the Human-Generated Systematic Literature Review: What is the link for the Overleaf or LetX document containing your group's Human-Generated Systematic Literature Review (the share link)?
  2. Link to the LLM-Generated Systematic Literature Review: What is the link for the Overleaf or LetX document containing the output from the LLM?
  3. Prompt(s): What was the full prompt(s) you used for the LLM?
  4. Time Spent on the Human-Generated Systematic Literature Review: How much time did your group spend on the Human-Generated Systematic Literature Review?
  5. Time Spent on the LLM-Generated Systematic Literature Review: How much time did your group spend on the LLM-Generated Systematic Literature Review?
  6. Similarities (X%): What are the similarities between the Human-Generated and LLM-Generated Systematic Literature Reviews? (Replace X with a rough estimate of how similar content-wise the two reviews are)
  7. Differences (X%): What are the differences between the Human-Generated and LLM-Generated Systematic Literature Reviews (i.e., what aspects are unique to each)? (Replace X with a rough estimate of how different content-wise the two reviews are)
  8. Strengths of LLM-Generated Systematic Literature Review: What are the general strengths of the LLM-Generated Systematic Literature Review relative to the Human-Generated Systematic Literature Review?
  9. Weaknesses of LLM-Generated Systematic Literature Review: What are the weaknesses of the LLM-Generated Systematic Literature Review relative to the Human-Generated Systematic Literature Review?
  10. LLM Hallucinations (X%): Verify all claims the Systematic Literature Review makes. What did the LLM hallucinate? (Replace X with a rough estimate of the percentage of hallucinated content)
  11. Choose one: If you had to choose only one of the two Systematic Literature Reviews to use for your project, which would you choose?
  12. LLM Feedback: Feed your Human-Generated Systematic Literature Review into the LLM and ask it simply for feedback on your Systematic Literature Review. Include that feedback in this section of your comparison document.
  13. Thoughts on the LLM's feedback: What did you think of the LLM's feedback? Was it useful? Did it help you improve your implementation? Why or why not?
  14. Changes to the Human-Generated Systematic Literature Review: What changes would you make to the Human-Generated Systematic Literature Review based on the LLM-Generated Systematic Literature Review and based on the LLM feedback?
  15. Lessons learned: What new takeaways about the LLM did you learn from this assignment? How much does the LLM seem to be aware of with respect to literature about the topic? How do you think the LLM's understanding of the literature compares to your own? How does this affect your expectations for how well the LLM will perform when asked to implement these tasks in Redux?
  16. Attributions: What did each member contribute to this assignment?

Make a copy of your group's Human-Generated project proposal entitled "CS 4473/5573 Final Systematic Literature Review: [Name of your NP-complete problem]" and update it with the insights from the LLM-Generated Systematic Literature Review and feedback, then share it with me (with editing permissions). All insights from the LLM-Generated Systematic Literature Review and feedback should be underlined in the updated Human-Generated Systematic Literature Review. List the LLM as an "author" in the updated Systematic Literature Review with its name also underlined as a reminder of what the underlined text represents.

Metrics Brainstorming

We have read that there are various criteria that are useful for attributing creativity to a system. For example, Boden (1998) suggests that creativity can be attributed to a system if it is capable of generating ideas that are novel, surprising, and valuable. Others have added to this list, suggesting such criteria as typicality, autonomy, and self-awareness. In the context of our class, we will be investigating the performance of LLMs as creative agents in implementing NP-complete problems, problem instances, solution algorithms (of any kind), reduction proofs, and reduction algorithms. As such, we will need to develop metrics for evaluating the performance of LLMs in each of these tasks. Use the "metrics" channel to post your ideas (as individuals, not project groups) for metrics that could be used to evaluate the performance of LLMs in these tasks. Be sure to include a brief description of each metric and how it could be measured.

LLM Metrics Brainstorming

As a group, use your LLM to generate a list of metrics that could be used to evaluate the performance of LLMs in implementing NP-complete problems, problem instances, solution algorithms (of any kind), reduction proofs, and reduction algorithms. The prompt for the LLM should be as follows: "Generate a list of metrics that could be used to evaluate the performance of LLMs in implementing NP-complete problems, problem instances, solution algorithms (of any kind), reduction proofs, and reduction algorithms. For each metric, include a brief description of the metric and how it could be measured."

Human vs. LLM Programming Task Assignments

As a group, you will be assigned a set of programming tasks to implement your chosen NP-complete problem in Redux. You will be asked to implement these tasks both by hand and by using an LLM. The goal of this assignment is to compare the performance of the LLM to that of the human programmers in your group. You will be asked to report on the performance of the LLM and the human programmers in your group in a final report at the end of the semester.

Create an Overleaf or LetX document entitled "CS 4473/5573 Human vs. LLM Programming Task Assignments: [Name of your NP-complete problem]" and share it with me (with editing permissions). In this document, you will have a section for each task below. Within each section, include the following information:

  1. Prompts: What was the full prompt(s) you used for the LLM?
  2. Time Spent on the Human-Generated implementation
  3. Time Spent on LLM-Generated implementation
  4. General description of how the Human-Generated implementation compared to the LLM-Generated implementation, including general similarities and differences and general strengths and weaknesses of each.
  5. Metrics: What metrics did you use to evaluate the performance of the Human-Generated implementation and the LLM-Generated implementation? How did each implementation perform on these metrics?
  6. LLM Feedback: Feed your Human-Generated implementation into the LLM and ask it simply for feedback on your implementation. Include that feedback in this section of your comparison document.
  7. Thoughts on the LLM's feedback: What did you think of the LLM's feedback? Was it useful? Did it help you improve your implementation? Why or why not?
  8. Changes to the Human-Generated implementation: What changes would you make to the Human-Generated implementation based on the LLM-Generated implementation and based on the LLM feedback?
  9. Lessons learned: What new takeaways about the LLM did you learn from this assignment? How much does the LLM seem to be aware of with respect to literature about the topic? How do you think the LLM's understanding of the literature compares to your own? How does this affect your expectations for how well the LLM will perform when asked to implement these tasks in Redux?
  10. An answer to the following question: "Was the LLM's output novel or previously published in some form? Did the LLM exhibit any creative behavior in its implementation of the task? If so, describe the behavior and how it was creative. If not, explain why you think the LLM did not exhibit any creative behavior."
  11. Attributions: What did each member contribute to this assignment?
  12. GitHub link to the Human-Generated implementation
  13. GitHub link to the LLM-Generated implementation
  14. GitHub link to the Final Implementation(s) for inclusion in Redux: describe how the final implementation(s) differs from the initial implementations and what improvements were made.

It is implied in each programmatic task that you will include unit tests for your implementation. You should go through the same comparative process with both human-generated and LLM-generated unit tests and include the results in a separate, final section at the end of your (growing) document (one subsection for the unit tests for each task).

Below are details about each of the programming tasks you will be asked to implement. You will be asked to implement these tasks first by hand and then using an LLM.

Problem Implementation

This task involves implementing your chosen NP-complete problem in the Redux backend. To be specific, you will implement the [problem name]_Class.cs file for your problem, similar to those implemented for other NP-complete problems that have been implemented.

To work in Redux, you will need to represent an instance of your problem as a composite of simple data structures. This is fairly straightforward for most problems, and I or a TA can help you do it. Currently, SPADE (the parser for Redux) supports compositions of the following data types:

  • boolean formula
  • set
  • list (note that a matrix is just a list of lists)
  • graph (directed, undirected, weighted, and unweighted)

For now, don't spend too much time devising a good default instance of your problem. You will be asked to do that in the next task. For now, just implement a simple instance of your problem that is easy to work with and that you can use for testing purposes.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Problem Instances

In the Problem Implementation Task, you will have implemented the [problem name]_Class.cs file for your problem. As part of this task, you will have included a "_defaultInstance" property. You probably didn't give too much thought to the instance at the time. In this task, your goal is to brainstorm a few different instances of your problem that are pedagogically valuable for illustrating the complexity and nuance of the problem, particularly instances that highlight the differences in performance when solved using different algorithms. The instance should be as simple as possible while still being pedagogically valuable.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Verifier Implementation

In this task, you will implement a verifier for your problem. A verifier is a function that takes an instance of your problem and a proposed solution and returns true if the proposed solution is valid for the given instance and false otherwise. The verifier should be implemented in the [problem name]Verifier.cs file in the Verifiers folder for your problem, similar to those implemented for other NP-complete problems that have been implemented.

For example, if your problem is the Hamiltonian Cycle problem, the verifier would take a graph and a proposed cycle and return true if the proposed cycle is a valid Hamiltonian cycle for the given graph and false otherwise.

For a problem to be NP-complete, it must be in NP, which means that there must be a polynomial-time verifier for the problem. Therefore, your verifier should be implemented in such a way that it runs in polynomial time with respect to the size of the input instance.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Brute Force Solver Implementation

In this task, you will implement a brute force solver for your problem. A brute force solver is a function that takes an instance of your problem and returns a solution (if one exists) or indicates that no solution exists. The brute force solver should be implemented in the [problem name]BruteForce.cs file in the Solvers folder for your problem, similar to those implemented for other NP-complete problems that have been implemented.

A brute force solver is not expected to be efficient, but it should be correct. It should (unintelligently) explore all possible solutions to the problem instance and return a valid solution if one exists. If no solution exists, it should indicate that as well.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Backtracking Solver Implementation

In this task, you will implement a backtracking solver for your problem. A backtracking solver is a function that takes an instance of your problem and returns a solution (if one exists) or indicates that no solution exists. The backtracking solver should be implemented in the [problem name]Backtracking.cs file in the Solvers folder for your problem, similar to those implemented for other NP-complete problems that have been implemented.

A backtracking solver is expected to be more efficient than a brute force solver, but it may still have exponential time complexity in the worst case.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Intelligent Solver Implementation

In this task, you will implement an intelligent solver for your problem. An intelligent solver is a function that takes an instance of your problem and returns a solution (if one exists) or indicates that no solution exists. The intelligent solver should be implemented in an appropriately named file (based on the name of the algorithm) in the Solvers folder for your problem, similar to those implemented for other NP-complete problems that have been implemented.

An intelligent solver is expected to be more efficient than a backtracking solver, but it may still have exponential time complexity in the worst case. The intelligent solver should use a more sophisticated algorithm than backtracking, such as dynamic programming, branch and bound, or a heuristic algorithm.

Be sure to include all of the necessary information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Reduction Proof

In this task, you will implement a proof for a reduction from an NP-compelte problem A already in Redux to your problem. A reduction proof is a function that takes an instance of problem A and returns an instance of your NP-complete problem (the "target" problem) such that the original instance has a solution if and only if the target instance has a solution.

It is intended that you will not devise a novel reduction, but rather that you will research and implement a known reduction from problem A to your problem. It should be sufficient to find a published reduction, even if it is not accompanied by a proof. All reductions follow a similar pattern which we will look at together in class.

This task is not a programmatic task, but rather a theoretical task. The proof is prerequisite to implementing the reduction because it establishes the computational equivalence between the two problems. You will need to research and understand the reduction from problem A to your problem and then implement the proof in a clear and concise manner.

This is one of the tasks that requires the most creativity and insight, and thus serves as a good litmus test for your creative problem-solving skills and those of the LLM. You will need to think deeply about the structure of your problem and how it relates to the structure of problem A. You will also need to consider how to construct an instance of your problem from an instance of problem A in such a way that the solution to the original instance can be transformed into a solution to the target instance and vice versa.

Be sure to include all of the necessary and relevant information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Reduction Implementation

In this task, you will implement the reduction deriving fromt the proof in the previous task. The reduction should be implemented in an appropriately named file (based on the name of the reduction algorithm or its originator) in a subdirectory of the ReduceTo folder for your problem where the name of the subdirectory is the name of problem A in the Redux library. See examples for other NP-complete problems that have been implemented in Redux.

Be sure to include all of the necessary and relevant information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Creative Leap

In this task, the goal is to extend your understanding of the power and limitations of LLMs by pushing the LLM to its creative limits. This is the one task that you, as the humans, don't have to first (or at all). You only need to validate the LLM's output. The task is divided into the following three subtasks:

  1. Can an LLM come up with a novel, heretofore unpublished solution algorithm for your problem on the fly?
  2. Can an LLM come up with a novel reduction to/from another problem already in Redux? (Try to find a pair of problems without a published reduction)
  3. Can the LLM come up with a pedagogically useful visualization on the Redux frontend for your problem, just by looking at other front end examples in the Redux codebase?

Particularly with the last of these subtasks, the visualization, feel free to work with the LLM to come up with a visualization that is pedagogically useful and that is also visually appealing. You may need to iterate with the LLM a few times to get a good result, but the goal is to see how creative the LLM can be in coming up with a visualization that is both pedagogically useful and visually appealing. Learning to program front end visualizations is non-trivial and takes time. If you find that the LLM is unable to accomplish the subtask without substantial guidance and human know-how, do not feel obligated to go down the rabbit hole of learning to program front end visualizations. This could also be a good opportunity to try some vibe coding (i.e., iteratively feed error messages to the LLM and let it try to fix them without explicit programming instructions).

Though you don't have to implement these tasks yourselves, you should do your due diligence both to vaidate the LLM's output and to verify that the LLM's output is novel and not previously published.

Be sure to include all of the necessary and relevant information in your report for this task, as detailed in the Human vs. LLM Programming Task Assignments section above.

Group Topic Presentation

As a group, choose a paper of interest that arises during your Systematic Literature Review that is relevant to your project and, ideally, to the topic of computational creativity (check with me to make sure this is a good choice). We will read (in advance) your paper, and you will lead a group discussion during a class period (similar to what we did for the first few classes of the semester). The goal for this assignment is two-fold: to help you better understand the power and limitations of LLMs and to give you an opportunity to teach what you've learned to the class (and to help us see the broader computational creativity implications).

Students will have read the paper before coming to class so as to be prepared to engage in a meaningful discussion about the paper and its relevance to CC and to group projects. When your group presents, I encourage you to prepare a good set of slides for facilitating a meaningful discussion that first reviews the main points of the paper and then has us engage in a broader discussion of its relevance to what we've already discussed in the course and/or to group projects. Please be sure to take into account Presentation Tips from the Tips for Communicating tab on the course website.

Midterm Presentation

Prepare a 10 minute presentation on the state of your project. Your presentation will be evaluated on the presence and quality of the following elements:

  • clear description of the chosen problem
  • includes slides
  • preliminary results
  • a demo of the project in its current state
  • argument for why the LLM has or has not thus far shown creative behavior from the basis of CC theory
  • challenges and next steps
  • good presentation skills (eye contact, volume, etc.)
  • individual contribution (please send me email with a brief summary of the contributions of each member)

Your presentation will be peer-reviewed using the Midterm Presentation Survey.

Final Presentation and Paper

Prepare a polished, 13-minute presentation that demonstrates your contributions to Redux and highlights the role LLMs played in your overall project. The presentation should include a significant demonstration component (ideally on the live Redux site) and should be fun, informative and interesting to a broad audience.Your presentation will be evaluated on the presence and quality of the following elements:

  1. An effective introduction/motivation for the problem the system solves (max 1-2 minutes)
  2. A brief (max 1-2 minutes) summary of related works
  3. An effective demonstration that shows inputs and outputs
  4. A discussion of metrics and evaluations used to evaluate the LLM's creativity
  5. A brief (max 1 minute) description of where you would go next

In addition your presentation will be graded on the audience's perception of the following criteria:

  • The appropriateness of level of effort for a semester project
  • The presentation makes sufficient and appropriate connections with elements of CC theory
  • Presentation skills (eye contact, volume, etc.)

The link for the audience survey can be found here.

Turn in a paper describing your work that meets the following guidelines:

  • Is well-written and professionally presented as if you were going to submit it for publication. Consider the following points about good academic writing (not an exhaustive list):
    • Whenever possible, use present tense
    • Write the paper in the first person plural, even if you're a single author
    • Avoid contractions, excessive use of nondescript pronouns (e.g., "it", "this", "those", "others"), excess or insufficient commas
  • Use the ICCC style (templates available here) and stick to ICCC conference page limits.
  • A descriptive title (see this site for some good guidelines)
  • A link just below the abstract to where the source code for your project can be found online
  • Contains a section for each of the following:
    • An abstract of roughly 200 words that summarizes the paper (look to write 1-2 sentences for each of the following sections)
    • An introduction/background section that tells a compelling story and place your work in the context of the (applicable) field(s) (i.e., should see related works with citations; best to tell it as a story) (~1 page)
    • A methods section that succinctly and accurately explains your approach (~2-3 pages)
    • A results section that provides results and analysis (~2-3 pages)
    • A discussion/conclusion section that discusses implications, contributions and future work (~1 page)
    • A bibliography with citations from the body of the paper (at least 5)

It is very possible that you will find it challenging to accomplish all of this in the page limit; however, that is what you must do (and the act of doing so will likely result in a better presentation of your work). You should use figures and tables to effectively communicate the methods, results, etc. You should upload one PDF submission per group via Canvas.

Your team will all receive the same base grade for the project presentation and report. To augment this, each team member will e-mail me a thoughtful and honest evaluation of the contributions of their team members, including themselves. For each individual, this evaluation should include a score from 1 to 10 indicating your evaluation of their work (10 meaning they were a valuable member of the team that made significant contributions to the project and were good to work with, 1 meaning they contributed nothing and were difficult to work with). If you would like, you may also include any clarifying comments, etc. (especially for low scores). If a person receives consistently low evaluations from peers, then their project scores will be proportionally decreased.