Share
Explore

Indiana Jones and the Temple of Infinite Recursions: A Data Structures Adventure

I've created an engaging and educational Java programming lab that combines data structures with an Indiana Jones-themed adventure. This lab, titled "Indiana Jones and the Temple of Infinite Recursions: A Data Structures Adventure," guides students through implementing and using various data structures while following a narrative.
Here's an overview of the lab structure:
Introduction and Setup
Chapter 1: The Array Abyss (Linear and Binary Search)
Chapter 2: The Linked List Labyrinth (Singly Linked List)
Chapter 3: The Stack Cliffs (Stack implementation and usage)
Chapter 4: The Queue Quicksand (Queue and Circular Queue)
Chapter 5: The Binary Tree of Truth (Binary Tree and traversals)
Chapter 6: The Hashtable Hideout (Hashtable implementation)
Final Boss: The Heap of Destiny (Min Heap implementation)
Each chapter introduces a new data structure or algorithm, provides a narrative context, and assigns coding tasks related to that structure. The lab covers:
Arrays and searching algorithms
Linked Lists
Stacks
Queues
Binary Trees
Hashtables
Heaps
The lab is designed to be both entertaining and educational, encouraging students to engage with the material through a story-driven approach. It provides code snippets and class structures to guide students, but leaves the core implementations for them to complete as exercises.
This approach allows students to:
Learn about various data structures and their operations
Practice implementing these structures in Java
Understand the applications and importance of each structure
Enjoy a narrative that makes learning more engaging


Indiana Jones and the Template of Infinite Recursions:

A Data Structures Adventure

Introduction

Welcome, brave programmer! You are about to embark on a perilous journey as the legendary Programmer Indiana Jones. Your mission is to recover the Crystal Memory Key containing the chronicles of Early Earth Humans' formative encounters with Aliens. To succeed, you must battle various data structures using their core weaknesses. Are you ready for the challenge?

Setup

Create a new Java project and copy the following base code into your main class:
import java.util.*;

public class TempleOfInfiniteRecursions {
public static void main(String[] args) {
IndianaJones indy = new IndianaJones();
indy.startAdventure();
}
}

class IndianaJones {
private int health = 100;
private List<String> inventory = new ArrayList<>();

public void startAdventure() {
System.out.println("Indiana Jones enters the Temple of Infinite Recursions...");
// The adventure begins here!
}

// Add more methods here as you progress through the lab
}

Chapter 1: The Array Abyss

Indiana Jones enters a long corridor filled with ancient arrays. To proceed, he must navigate through them efficiently.

Task 1: Implement Linear Search

Create a method linearSearch that searches for a specific element in an array. Use this to find the exit!
public static int linearSearch(int[] arr, int target) {
// Implement linear search here
}

Task 2: Optimize with Binary Search

The arrays are now sorted. Implement a more efficient binarySearch method to quickly find the Crystal Memory Key fragment.
java
Copy
public static int binarySearch(int[] arr, int target) {
// Implement binary search here
}

Chapter 2: The Linked List Labyrinth

Indy encounters a maze-like structure representing a linked list. He must traverse it to proceed.

Task 3: Implement a Singly Linked List

Create a LinkedList class with methods to add nodes, delete nodes, and detect cycles (the labyrinth's traps!).

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

void add(int data) {
// Implement add method
}

void delete(int data) {
// Implement delete method
}

boolean hasCycle() {
// Implement cycle detection (Floyd's cycle-finding algorithm)
}
}

Chapter 3: The Stack Cliffs

Indiana Jones must climb the Stack Cliffs by pushing and popping his way to the top.

Task 4: Implement a Stack

Create a Stack class using an array or linked list. Implement push, pop, and peek operations.
java
Copy
class Stack {
private List<Integer> data;

Stack() {
data = new ArrayList<>();
}

void push(int item) {
// Implement push
}

int pop() {
// Implement pop
}

int peek() {
// Implement peek
}

boolean isEmpty() {
// Implement isEmpty
}
}

Task 5: Balance the Parentheses

Use your Stack to check if a string of parentheses is balanced. This will unlock the door to the next chamber!
public static boolean isBalanced(String s) {
// Implement parentheses balancing using a stack
}

Chapter 4: The Queue Quicksand

Indy must navigate through quicksand by efficiently managing a queue of stepping stones.

Task 6: Implement a Queue

Create a Queue class with enqueue, dequeue, and peek operations.
java
Copy
class Queue {
private List<Integer> data;

Queue() {
data = new ArrayList<>();
}

void enqueue(int item) {
// Implement enqueue
}

int dequeue() {
// Implement dequeue
}

int peek() {
// Implement peek
}

boolean isEmpty() {
// Implement isEmpty
}
}

Task 7: Implement a Circular Queue

Optimize your queue to work circularly, allowing Indy to reuse stepping stones!
java
Copy
class CircularQueue {
private int[] data;
private int front, rear, size;

CircularQueue(int capacity) {
data = new int[capacity];
front = rear = -1;
size = 0;
}

void enqueue(int item) {
// Implement circular enqueue
}

int dequeue() {
// Implement circular dequeue
}

boolean isFull() {
// Implement isFull
}

boolean isEmpty() {
// Implement isEmpty
}
}

Chapter 5: The Binary Tree of Truth

Indiana Jones faces the Binary Tree of Truth, where he must traverse different paths to uncover the location of the Crystal Memory Key.

Task 8: Implement a Binary Tree

Create a BinaryTree class with methods for insertion and different types of traversals.
java
Copy
class TreeNode {
int data;
TreeNode left, right;

TreeNode(int data) {
this.data = data;
left = right = null;
}
}

class BinaryTree {
TreeNode root;

void insert(int data) {
// Implement insertion
}

void inorderTraversal(TreeNode node) {
// Implement inorder traversal
}

void preorderTraversal(TreeNode node) {
// Implement preorder traversal
}

void postorderTraversal(TreeNode node) {
// Implement postorder traversal
}
}

Chapter 6: The Hashtable Hideout

Indy discovers the alien artifacts are hidden in a complex Hashtable structure. He must master hashing to retrieve them.

Task 9: Implement a Simple Hashtable

Create a Hashtable class with methods to insert, retrieve, and delete items.
java
Copy
class Hashtable {
private static final int SIZE = 10;
private List<List<Pair<String, String>>> table;

Hashtable() {
table = new ArrayList<>(SIZE);
for (int i = 0; i < SIZE; i++) {
table.add(new LinkedList<>());
}
}

private int hash(String key) {
return Math.abs(key.hashCode() % SIZE);
}

void put(String key, String value) {
// Implement put
}

String get(String key) {
// Implement get
}

void remove(String key) {
// Implement remove
}
}

Final Boss: The Heap of Destiny

Indiana Jones faces his final challenge: the Heap of Destiny, where he must efficiently manage priorities to claim the Crystal Memory Key.

Task 10: Implement a Min Heap

Create a MinHeap class that Indy can use to always grab the smallest (highest priority) item.
java
Copy
class MinHeap {
private List<Integer> heap;

MinHeap() {
heap = new ArrayList<>();
}

void insert(int value) {
// Implement insertion
}

int extractMin() {
// Implement extract minimum
}

private void heapifyUp(int index) {
// Implement heapify up
}

private void heapifyDown(int index) {
// Implement heapify down
}
}

Conclusion

Congratulations, intrepid programmer! You've guided Indiana Jones through the Temple of Infinite Recursions, battling each data structure with wit and code. By implementing these data structures and algorithms, you've not only recovered the Crystal Memory Key but also mastered the fundamental tools of computer science.
Your next mission, should you choose to accept it, is to optimize these implementations and explore their real-world applications. The adventures in code never end!
Remember, programmer: "It's not the years, it's the mileage." Keep coding, and may your algorithms always be efficient!
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.