<h1
style="
display: flex;
align-items: center;
justify-content: center;"
>
DSaA Lab 0 - Introduction
</h1>

<h4 style="text-align: center;">
The Islamic University of Gaza<br>
Engineering Faculty<br>
Department of Computer Engineering
</h4>

<font color="#ec53c4">
Prepared by:
Eng. Ahmad Albarasy
</font>
<br>
<font color="#ec53c4">
Under the supervision of:
Prof. Ahmad Mahdi
</font>

---

Welcome one and all to the Data Structures and Algorithms lab! This lab is one of the most important ones in your life journey of becoming a distinguished computer engineer, and the reason behind that is that it lays the foundation for efficient problem-solving and critical thinking by teaching you how to design and leverage various data structures to solve problems effectively. It also teaches you how to design, analyze, and implement algorithms that make programs more efficient and reliable.

## What are Data Structures and Algorithms?

**Data Structures** are systematic ways of organizing and storing data so that it can be accessed and modified efficiently in order to solve a variety of problems that we encounter in software engineering. They define how data is arranged in memory and how operations such as insertion, deletion, searching, and traversal are performed.

**Algorithms** are step-by-step procedures or sets of instructions designed to solve a specific problem or perform a particular task.

Algorithms are not just a computer science field of study, but rather a universal idea that we use almost in every aspect of our life! For instance, When you open your phone to send a message to someone, you are basically following an algorithm that consists of a sequence of steps, starting by unlocking your phone, going through your apps list, all the way to writing the message and pressing "send".

## Why do we learn Data Structures?

Lets give an analogy to better understand why do we bother learning about data structures and how to use them effectively. Imagine that someone asked you to dig a hole 3-meter-deep in the sand.

To do this, you could use your own hands and get them dirty but that would take forever!

Or, you could use a spoon, which would make you look completely dumb to anyone watching 🫤

>[!Note] Speaking of dumb people
>If you have 5 minutes to waste, enjoy this video fo a guy who actually dug a 12 feet bunker using only spoons 🙂
>https://www.youtube.com/watch?v=BKpJRzFq2SQ

Another solution would be to use a shovel, which sure, takes less time and more optimal to get the job done, but still, we can do better..

The optimal solution would be using a bulldozer, which would takes less than a minute to finish!

The same analogy applies to choosing the right data structure to solve a problem. Take the example of sorting an array of numbers using two algorithms: **Bubble Sort** and **Heap Sort**:

import java.util.Random;

public class SortPerformance {
  public static void main(String[] args) {
    int n = 1000;              // default size
    boolean printArrays = false;

    // Parse command-line arguments
    for (String arg : args) {
      if (arg.equalsIgnoreCase("--print")) {
        printArrays = true;
      } else {
        try {
          n = Integer.parseInt(arg);
        } catch (NumberFormatException e) {
          System.out.println("Invalid input '" + arg + "'. Using default n = 1000");
        }
      }
    }

    int[] numbers = new int[n];
    Random rand = new Random();
    for (int i = 0; i < n; i++) {
      numbers[i] = rand.nextInt(10000);
    }

    if (printArrays) {
      System.out.println("Array before sorting:");
      printArray(numbers);
      System.out.println();
    }

    // -------------------- Bubble Sort --------------------
    int[] bubbleArr = numbers.clone(); // preserve original array

    Runtime runtime = Runtime.getRuntime();
    runtime.gc();
    long memoryBefore = runtime.totalMemory() - runtime.freeMemory();
    long startCpuTime = System.nanoTime();
    bubbleSort(bubbleArr);
    long endCpuTime = System.nanoTime();
    long memoryAfter = runtime.totalMemory() - runtime.freeMemory();
    long memoryUsed = memoryAfter - memoryBefore;
    double timeTakenMs = (endCpuTime - startCpuTime) / 1_000_000.0;

    System.out.println("Bubble Sort Results:");
    if (printArrays) {
      printArray(bubbleArr);
    }
    System.out.println("Number of elements sorted: " + n);
    System.out.println("Time taken: " + timeTakenMs + " ms");
    System.out.println("Memory used: " + memoryUsed + " bytes");
    System.out.println("----------------------------------");

    // -------------------- Heap Sort --------------------
    int[] heapArr = numbers.clone();

    runtime.gc();
    memoryBefore = runtime.totalMemory() - runtime.freeMemory();
    startCpuTime = System.nanoTime();
    heapSort(heapArr);
    endCpuTime = System.nanoTime();
    memoryAfter = runtime.totalMemory() - runtime.freeMemory();
    memoryUsed = memoryAfter - memoryBefore;
    timeTakenMs = (endCpuTime - startCpuTime) / 1_000_000.0;

    System.out.println("Heap Sort Results:");
    if (printArrays) {
      printArray(heapArr);
    }
    System.out.println("Number of elements sorted: " + n);
    System.out.println("Time taken: " + timeTakenMs + " ms");
    System.out.println("Memory used: " + memoryUsed + " bytes");
    System.out.println("----------------------------------");
  }

  // -------------------- Bubble Sort --------------------
  public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
      swapped = false;
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          swapped = true;
        }
      }
      if (!swapped) break;
    }
  }

  // -------------------- Heap Sort --------------------
  public static void heapSort(int[] arr) {
    int n = arr.length;

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    // One by one extract elements from heap
    for (int i = n - 1; i >= 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // call max heapify on the reduced heap
      heapify(arr, i, 0);
    }
  }

  private static void heapify(int[] arr, int n, int i) {
    int largest = i;    // Initialize largest as root
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) largest = right;

    // If largest is not root
    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      // Recursively heapify the affected sub-tree
      heapify(arr, n, largest);
    }
  }

  public static void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + (i < arr.length - 1 ? ", " : ""));
      if ((i + 1) % 20 == 0) System.out.println();
    }
    System.out.println();
  }
}

Copy this code and run it using different input lengths as an argument and see the significant differnce in runtime and memory!

## Final thoughts

Learning data structures and algorithms is not just about finishing a course or ticking a box. It’s about thinking in a smarter way, learning how to organize data, solve problems step by step, and make your programs efficient. These skills take time to develop, but once you do, they will help you stand out as an engineer. Understanding data structures and algorithms is not just something you learn for a grade, but rather a mindset that will stay with you throughout your career.