**
Authors
**

- Yashas Ravi, yr271@scarletmail.rutgers.edu.
- Ana Paula Centeno, anapaula@cs.rutgers.edu.

**
Abstract
**

The Infinity War assignment tests the comprehension of the graph data structure in a context based on *Avengers: Infinity War.*
The assignment has various tasks, where each task focuses on a specific aspect of a graph, and makes connections to the movie as well as other fields such as Physics, Neuroscience, and Philosophy in a creative manner.
The assignment tests graph manipulation, connectedness, search, recursion, cycles, and other topics, where each task focuses on one of these topics.
Furthermore, the assignment is meant for CS2 students, takes around 1-2 weeks to complete, and has a mix of easier and harder tasks.
The student handout and starter code are provided.

**What is the Infinity War assignment?**

The Infinity War assignment provides students an oppurtunity to practice implementations and manipulations of graphs in a fun movie-based context.
**Students are not required to watch Avengers: Infinity War to understand the assignment.**
The assignment contains various files that the students have to edit.

**What makes the Infinity War assignment great?**

Usually, assignments given to students are based in a real-world or a hypothetical context.
However, the Infinity War assignment provides movie scenes as context for each
of the problems. **Specifically, the task described in each problem directly intertwines with a specific scene
in Avengers: Infinity War.**
Furthermore, since the order of the tasks given correspond to the order of the movie scenes
they correspond to, the assignment makes it such that the student is reading a story
while they implement the solutions to each task. As such, since every problem has a rich
movie-based context, students would be more likely to enjoy solving each task as they progress
through the assignment.

**How are the Infinity War assignment files structured?**

The assignment consists of the following files:

- Files the students have to edit and implement methods in: ForgeStormBreaker.java, LocateTitan.java, MindStoneNeighborNeurons.java, UseTimeStone.java, and PredictThanosSnap.java.
- Files that the students can utilize to implement their solutions: StdRandom.java, StdOut.java, and StdIn.java.
- These files are described in great detail in the student handout.

- The assignment encourages the use of text files as inputs and outputs for each task.
- An
*example*structure of the input and output files (and corresponding preconditions) are described in the student handout. - Each input test case is a text file containing a representation of a graph.
- The handout describes what problem must be solved for each editable file.
- In the editable file, students must read the input test case, construct a graph using the input, implement a solution for the problem described in the handout using the created graph, and finally write their result into a new output file.
- Instructors are encouraged to provide students with a variety of input test cases for each task.
- Instructors are also encouraged to create output test cases corresponding to the input test cases, and solution code that uses various concepts taught in the course ciriculum.

**MLA Citations for Marvel resources and external code are provided in the student handout.**

**The Infinity War assignment focuses on the following topics:**

- Graph construction using Adjacency Matrices and Adjacency Lists.
- The distinction between graph nodes, edges, and edge weights.
- Implementing graph algorithms by understanding pseudocode.
- Graph search algorithms and connectedness.
- Graph search and optimization algorithms (such as Dijkstra's Algorithm)
- Acyclic graphs, directed graphs, and their properties.
- Counting algorithms using graphs.

The prime audience for the Infinity War assignment would be students who are currently being
introduced to the Graph data structure and learning about Graph manipulation and algorithms.
**As such, this assignment would be ideal for a CS2 student.**
Furthermore, students with a keen interest in stories, especially superhero story arcs and
movie franchises might find this assignment particularly enjoyable.

**How challenging is the Infinity War assignment?**

The Infinity War assignment contains a mix of easier and more nuanced problems.

*ForgeStormBreaker*requires students to sum the elements in an array. This problem is more of a warmup and helps students get accustomed to the code testing environment.*LocateTitan*requires students to manipulate an unweighted graphs and implement Dijkstra's Algorithm. This task may take long, and is of medium difficulty.*MindStoneNeighborNeurons*requires students to locate a node in a tree-like graph. This task is not as complex as most of the other tasks, and as such is on the easier side.*UseTimeStone*requires students to keep a counter while traversing a graph. This task could be the hardest task since it may require a strong knowledge of recursion and backtracking.*PredictThanosSnap*requires students to randomly delete some of the nodes and determine if the following graph is connected. This task may take long and is of medium difficulty.

**How long does the Infinity War assignment take to complete?**

The Infinity War assignment should take **1-2 weeks** to fully complete.
This includes implementing all of the methods, running the code
against any given test cases, utilizing custom test cases that the student could is
encouraged to create, and debugging to resolve any issues.

**Some of the strengths of the Infinity War assignment include:**

- The connection of each task to an important scene in
*Avengers: Infinity War*gives rich context to every problem presented, which the students may enjoy. - The chronological order of the tasks follow the order of the scenes in the movie, so students may feel that they are reading a story as they solve each task.
- Each task also makes connections to concepts in other fields such as Physics (flux), Neuroscience (nerves), Philosophy (expected utility), and Social Science (social networks).
- The use of an adjacency matrix as a Graph representation may make it easier for students to construct the graph, encouraging them to focus more on solving the task using the created graph.
- The first task is relatively easier to implement, meaning that it can help students get used to a File I/O environment, which can make the subsequent tasks easier.
- The assignment encourages students to read and understand pseudocode, while learning about relatively advanced topics (such as Dijkstra's Algorithm), which are important skills in the industry as well as research.
- The assignment tests various concepts related to Graphs, as well as applying previous Data Structures concepts such as arrays, recursion, trees, and hashing (if efficiency is proritized).
- In general, the Infinity War assignment may encourage students to relate the concepts they learn in academia to the external world, as well as their personal hobbies, passions, and interests.

**Some of the weaknesses of the Infinity War assignment include:**

- The connection to the movie could seem like a distractor for some students, especially if they have limited interest in superheros or stories.
- The connections to external fields (such as Biology, Neuroscience, etc) may add a layer of complexity and thus confuse some students.
- The testing environment may be intimidating to students who have never worked with File I/O in Java.
- The creation of custom test cases may be challenging if edge cases are being tested for complex graph algorithms.
- The code currenly only supports Java, so students who are familiar with other languages may struggle to implement their solutions.

**How can these weaknesses be addressed?**

- The description could exclude extraneous plot details and only mention details relevant to the plot, if the student prefers.
- The description could provide more resources and links to help students understand concepts from external fields.
- The description could provide a Driver class to avoid File I/O if the students do not prefer it.
- The description could provide an external class that randomly generates test-cases.
- The code could be translated to different languages, especially Python, C++, and Javascript.

**Some of the pre-requisite skills and topics that can be helpful while completing the Infinity War assignment include:**

- Basic control structures, loops, and Java syntax.
- Testing and debugging code, especially with print statements.
- Array creation, access, and manipulation.
- Creation, access, and manipulation of node-based Data Structures such as Trees and Linked Lists.
- Recursive algorithms and backtracking.
- Stacks and Queues (if the student chooses to use these).
- The usage of random number generators.
- File creation and File I/O in Java.
- Graph-related concepts such as nodes, edges, connectedness, searching, counting, and cycles.

**The files in the Infinity War assignment that the other files depend on include:**

- StdRandom.java, which generates a random number based on a seed parameter.
- StdIn.java, which allows students to parse input text files.
- StdOut.java, which allows students to create and write into an output text file.

**What are some variants of the Infinity War asssignment?**

As of now, there are no known variants, but the assignment can be redone using different languages.
The assignment has been released twice to over 1500+ students, and we have not recieved any negative reactions or feedback to it from the students.

Furthermore, one of the tasks (UseTimeStone) was given as extra credit, which several students also completed.
Some of the variants I can expect in the future include additional tasks for other scenes in *Avengers: Infinity War*,
similar assignments for different movies, and assignments that have different versions of the tasks given in this assignment.

**What general lessons can be learned from the structure of the Infinity War assignment?**

- Relating the given task to something the students can relate to would be very important.
- Because
*Avengers: Infinity War*is a mainstream film, it was chosen as a medium that students can relate to. - Varying each task and diversifying the assignment can also make the assignment more intriguing.
- Branching out each task to other topics in Computer Science (ex: OOP, ML, memory, etc) as well as topics in other fields can help enrich the context of the task.

**The Starter Code given to students contains a couple files with methods that the students can use, as well as files the users with methods that students have to implement.**

- The StdRandom, StdIn, and StdOut files, used for random number generation, input text file parsing, and output text file generation respectively.
- Empty files for ForgeStormBreaker, LocateTitan, MindStoneNeighborNeurons, UseTimeStone, and PredictThanosSnap. Students will implement the methods in these files.
- Further descriptions of these files are given in the student handout for the assignment.