CSA Blog

Ian Wu

EC Writeup

j avi *JJJ ;}|88as, v7&`k~ jvj!! c;::::!:!::!:!:::!!!! ! !:::

“you have to be in tech or else your toes will fall off” “you have to be ethical or else you will be in jail”

presenters: mercer: business side tomasz: fbi agent, catching people, ethical side nzeata: usd professor, curriculum side, military background in cybersecurity

question to panelists:

  1. what is a real world case you’ve worked on or studied?
    • FBI: checking out and finding mistake that professional made
    • powershell data scraper to find data left on systems
  2. what are the biggest cybersecurity threats today?
    • ransomware, foreign adversary threats
    • ai created zero days
    • phishing
  3. how do ethical hackers help organizations strengthen their security
    • emulate real attacks, ethical hackers are actually trying to hack in to emulate real attackers
    • penetration testing
  4. what to do
    • cybersecurity is securing IT, learn IT
    • soft skills
  5. what are challenges you faced?
    • explaining to people with no knowledge
    • stressful environment, working with little resources
  6. what trends do you see in cybersecurity?
    • specialization, specific device security rather than general
    • penetration testing with AI
    • entities now prioritizing cybersecurity
  7. how do cybersecurity professionals prepare for constrantly evolving threats?
    • network
    • stay informed and be curious
    • stay aware of existing environment

image

Merge Sort HW

Merge sort is a sorting algorithm. It works by dividing the array repeatedly into half until all pieces are groups of 1 or 2. It then sorts all of these blocks, before merging arrays back up and sorting them together. It is different from selection and bubble sort which have a sorted block that they sort elements one by one into.

Time complexity can be divided into two sections, the splitting and the merging. The splitting takes n - 1 operations, since by the end each element ends up individually, so each element except one had to be split. Then, for each level, n operations must be done to compares objects to the ones beside them. This must be done for each of log2(n) splits, giving us O(n*log2n) for the merging. For large values of n, however, n-1 is negligible and therefore the time complexity is O(nlog2(n))

public class MergeSortInversions {
    public static int mergeSortAndCount(int[] arr) {
        int[] temp = new int[arr.length];
        return mergeSortAndCountHelper(arr, temp, 0, arr.length - 1);
    }

    private static int mergeSortAndCountHelper(int[] arr, int[] temp, int left, int right) {
        int inversionCount = 0;
        if (left < right) {
            int mid = (left + right) / 2;
            
            inversionCount += mergeSortAndCountHelper(arr, temp, left, mid);
            inversionCount += mergeSortAndCountHelper(arr, temp, mid + 1, right);
            inversionCount += mergeAndCount(arr, temp, left, mid, right);
        }
        return inversionCount;
    }

    private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left, j = mid + 1, k = left;
        int inversionCount = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                inversionCount += (mid - i + 1);
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= right) {
            temp[k++] = arr[j++];
        }

        System.arraycopy(temp, left, arr, left, right - left + 1);

        return inversionCount;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 8, 6, 1};
        System.out.println("Number of inversions: " + mergeSortAndCount(arr));
    }
}

MergeSortInversions.main(new String[]{})
Number of inversions: 5
float a = 1;
int b = 3;

System.out.println(a * b);
System.out.println(a / b);
3.0
0.33333334

Selection, Insert, & Big O

Big O

Big O is a mathematical notation to show the limiting behavior of a function when the argument is going toward a value or infinity.

In CS, we use it to describe the performance of an algorithm in terms of time and space.

Big O notation will give us an upper bound on the growth rate of a function, allowing us to compare the efficiency of different algorithms.

Selection Sort

Sorts arrays by repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

Step 1: Array arr with N size

int[] arr = {10, 30, 15, 5};

Step 2: Initialise i = 0

Step 3: If(i < N-1), Check for any element arr[j] where j > i and arr[j] < arr[i], then Swap arr[i] and arr[j]

  • i = 0, assume arr[0] = 10 is the minimum
    • 10 < 30, 10 remains the minimum
    • 10 < 15, 10 remains the minimum
    • 10 > 5, so 5 is the new minimum
      Swap 10 and 5 -> {5, 30, 15, 10}
      {5} is considered sorted
  • i = 1, assume arr[1] = 30 is the minimum
    • 30 > 15, minimum value = 15
    • 15 > 10, minimum value = 10, no more values
      Swap arr[1] with arr[3]
      New array is {5, 10, 15, 30}
      {5, 10} is considered sorted
      {15, 30} is unsorted
  • i = 2, assume arr[2] = 15 is the minimum
    • 15 < 30, so the array is sorted
      Fully sorted array = {5, 10, 15, 30}

Step 4: i = i + 1 and Goto Step 3

Step 5: Exit

Fully sorted array = {5, 10, 15, 30}

Selection Sort Big O

Let N be the number of integers in an array

Each iteration in an algorithm leads to a new comparison made. For example, the first iteration will be (n-1) comparisions, 2nd will be (n-2), and on till the last iteration which will be 1.

number of comparisions = (n-1) + (n-2) + (n-3) + … + 1 = n(n-1)/2 = n^2

Time complexity for selection sort will be O(n^2)

Time complexity cases for selection sort:

Best case: when array is already sorted (algorithm does not need to make any changes, low time)

Avg-case: elements are randomized (takes a bit of time for algorithm to sort)

Worst-case: elements are in descending order but algorithm is trying to sort into ascending order (algorithm will go one by one to compare values resulting in the highest possible time for the algorithm to sort)

Code Example

import java.util.Arrays;

class GfG {

    static void selectionSort(int[] arr){
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
          
            // Assume the current position holds
            // the minimum element
            int min_idx = i;

            // Iterate through the unsorted portion
            // to find the actual minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                  
                    // Update min_idx if a smaller element
                    // is found
                    min_idx = j;
                }
            }

            // Move minimum element to its
            // correct position
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
            printArray(arr);           
        }
    }

    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
  
    public static void main(String[] args){
        int[] arr = { 64, 25, 12, 22, 11 };

        System.out.print("Original array: ");
        printArray(arr);

        selectionSort(arr);

        System.out.print("Sorted array: ");
        printArray(arr);
    }
}

GfG.main(new String[]{});
Original array: 64 25 12 22 11 
11 25 12 22 64 
11 12 25 22 64 
11 12 22 25 64 
11 12 22 25 64 
Sorted array: 11 12 22 25 64 

Insertion Sort

Sorts arrays by repeatedly taking an element from the unsorted part and inserting it into the correct position in the sorted part.

Step 1: Array arr with N size

int[] arr = {10, 30, 15, 5};

Step 2: Initialise i = 1

Step 3: If(i < N), Check for the position to insert arr[i] in the sorted part (arr[0] to arr[i-1])

  • i = 1, assume arr[1] = 30 is the element to be inserted.
    • Compare arr[1] with arr[0] (10): 30 > 10, no shift needed.
      Sorted array: {10, 30}
  • i = 2, assume arr[2] = 15 is the element to be inserted.
    • Compare arr[2] with arr[1] (30): 15 < 30, so shift arr[1] to the right (arr[1] = 30).
    • Now compare arr[2] with arr[0] (10): 15 > 10, insert 15 after 10.
      New array: {10, 15, 30, 5}
      {10, 15} is considered sorted.
  • i = 3, assume arr[3] = 5 is the element to be inserted.
    • Compare arr[3] with arr[2] (30): 5 < 30, so shift arr[2] to the right (arr[2] = 30).
    • Now compare arr[3] with arr[1] (15): 5 < 15, shift arr[1] to the right (arr[1] = 15).
    • Now compare arr[3] with arr[0] (10): 5 < 10, shift arr[0] to the right (arr[0] = 10).
      Insert 5 at arr[0].
      New array: {5, 10, 15, 30}
      {5, 10, 15} is considered sorted.

Step 4: i = i + 1 and Goto Step 3

Step 5: Exit

Fully sorted array = {5, 10, 15, 30}

Insertion Sort Big O

Let N be the number of integers in an array

Each iteration in an algorithm leads to a new comparison made. For example, the first iteration will be (n-1) comparisions, 2nd will be (n-2), and on till the last iteration which will be 1.

number of comparisions = (n-1) + (n-2) + (n-3) + … + 1 = n(n-1)/2 = n^2

Time complexity for selection sort will be O(n^2)

Time complexity cases for selection sort:

Best case: when array is already sorted (algorithm does not need to make any changes, low time)

Avg-case: elements are randomized (takes a bit of time for algorithm to sort)

Worst-case: elements are in reversed order (each element needs to be compared and swapped with every preceding element, maximum possible time for algorithm to work)

Code Example (GfG)

public class InsertionSort {
    /* Function to sort array using insertion sort */
    void sort(int arr[])
    {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
            printArray(arr);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");

        System.out.println();
    }

    // Driver method
    public static void main(String args[])
    {
        int arr[] = { 12, 11, 13, 5, 6 };

        InsertionSort ob = new InsertionSort();
        ob.sort(arr);

        printArray(arr);
    }
}
InsertionSort.main(new String[]{});
11 12 13 5 6 
11 12 13 5 6 
5 11 12 13 6 
5 6 11 12 13 
5 6 11 12 13 

Homework:

Part 1: Write your own

a. Selection sort, and sort an array in descending order
b. Insertion sort, and sort an array in ascending order

Submissions that directly copy examples given in the lesson material will not be accepted.

class SelectionSort {
    public static void sort(int[] arr) {
        selectionSort(arr, 0);
    }

    private static void selectionSort(int[] arr, int index) {
        if (index >= arr.length - 1) return;

        int maxIdx = index;
        for (int i = index + 1; i < arr.length; i++) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }

        if (maxIdx != index) {
            arr[index] = arr[index] + arr[maxIdx];
            arr[maxIdx] = arr[index] - arr[maxIdx];
            arr[index] = arr[index] - arr[maxIdx];
        }

        printArray(arr);
        selectionSort(arr, index + 1);
    }

    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");

        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 8, 101, 3, 5, 23, 78, 1, 91};
        sort(arr);
        System.out.println("Selection Sort (Descending): " + java.util.Arrays.toString(arr));
    }
}

SelectionSort.main(new String[]{})
101 2 8 4 3 5 23 78 1 91 
101 91 8 4 3 5 23 78 1 2 
101 91 78 4 3 5 23 8 1 2 
101 91 78 23 3 5 4 8 1 2 
101 91 78 23 8 5 4 3 1 2 
101 91 78 23 8 5 4 3 1 2 
101 91 78 23 8 5 4 3 1 2 
101 91 78 23 8 5 4 3 1 2 
101 91 78 23 8 5 4 3 2 1 
Selection Sort (Descending): [101, 91, 78, 23, 8, 5, 4, 3, 2, 1]
public class InsertionSort {

    public static void InsertionSort(int[] arr, int n) {
        if (n <= 1) {
            return;
        }

        InsertionSort(arr, n - 1);
        printArray(arr);

        int last = arr[n - 1];
        int j = n - 2;

        while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = last;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 8, 101, 3, 5, 23, 78, 1, 91};

        InsertionSort(arr, arr.length);

        printArray(arr);
    }
}

InsertionSort.main(new String[]{})
4 2 8 101 3 5 23 78 1 91 
2 4 8 101 3 5 23 78 1 91 
2 4 8 101 3 5 23 78 1 91 
2 4 8 101 3 5 23 78 1 91 
2 3 4 8 101 5 23 78 1 91 
2 3 4 5 8 101 23 78 1 91 
2 3 4 5 8 23 101 78 1 91 
2 3 4 5 8 23 78 101 1 91 
1 2 3 4 5 8 23 78 101 91 
1 2 3 4 5 8 23 78 91 101 

Part 2: Time Complexity Exercise

  1. Write Java functions for Selection and Insertion Sort (You may use your code or modified parts of your code from part 1)
  2. Ensure that each function records the time taken to sort the arrays (will be given below)
  3. Record time taken to sort each array with each sorting algorithm
  4. Answer the following questions
    • Which algorithm performed better for Array A? Why?
    • Which sorting algorithm beformed better for Array B? Why?
    • When is it best to use each sorting algorthim? (think about how sorted a dataset is, the size of a data set, etc.)

      Arrays

    • int[] arrayA = {29, 10, 14, 37, 13};
    • int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};

The following version have print statements removed to better measure time.

import java.util.*;

class SelectionSort {
    public static void sort(int[] arr) {
        selectionSort(arr, 0);
    }

    private static void selectionSort(int[] arr, int index) {
        if (index >= arr.length - 1) return;

        int maxIdx = index;
        for (int i = index + 1; i < arr.length; i++) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }

        if (maxIdx != index) {
            arr[index] = arr[index] + arr[maxIdx];
            arr[maxIdx] = arr[index] - arr[maxIdx];
            arr[index] = arr[index] - arr[maxIdx];
        }

        selectionSort(arr, index + 1);
    }

    public static void main(String[] args) {
        int[] arrayA = {29, 10, 14, 37, 13};
        int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};

        long startTime = System.nanoTime();
        sort(arrayA);
        long endTime = System.nanoTime();

        System.out.println("Selection Sort (Descending): " + java.util.Arrays.toString(arrayA));
        System.out.println("Time taken: " + (endTime - startTime) + " nanoseconds");

        startTime = System.nanoTime();
        sort(arrayB);
        endTime = System.nanoTime();

        System.out.println("Selection Sort (Descending): " + java.util.Arrays.toString(arrayB));
        System.out.println("Time taken: " + (endTime - startTime) + " nanoseconds");
    }
}

SelectionSort.main(new String[]{});

public class InsertionSort {

    public static void InsertionSort(int[] arr, int n) {
        if (n <= 1) {
            return;
        }

        InsertionSort(arr, n - 1);

        int last = arr[n - 1];
        int j = n - 2;

        while (j >= 0 && arr[j] > last) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = last;
    }

    public static void main(String[] args) {
        int[] arrayA = {29, 10, 14, 37, 13};
        int[] arrayB = {1, 2, 5, 4, 3, 6, 7, 8, 9, 10};

        long startTime = System.nanoTime();
        InsertionSort(arrayA, arrayA.length);
        long endTime = System.nanoTime();

        System.out.println("Insertion Sort (Ascending): " + java.util.Arrays.toString(arrayA));
        System.out.println("Time taken: " + (endTime - startTime) + " nanoseconds");

        startTime = System.nanoTime();
        InsertionSort(arrayB, arrayB.length);
        endTime = System.nanoTime();

        System.out.println("Insertion Sort (Ascending): " + java.util.Arrays.toString(arrayB));
        System.out.println("Time taken: " + (endTime - startTime) + " nanoseconds");
    }
}

InsertionSort.main(new String[]{});
Selection Sort (Descending): [37, 29, 14, 13, 10]
Time taken: 2299 nanoseconds
Selection Sort (Descending): [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Time taken: 3351 nanoseconds
Insertion Sort (Ascending): [10, 13, 14, 29, 37]
Time taken: 3322 nanoseconds
Insertion Sort (Ascending): [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Time taken: 1836 nanoseconds

Answer the following questions Selection sort uses more comparisons, while Insertion sort uses more swaps. In the worse case scenario, both are O(n^2), but partially sorted arrays can reduce this greatly for Insertion sort. Selection sort is the same time complexity in all cases

  • Which algorithm performed better for Array A? Why?
    • Selection Sort, see above paragraph
  • Which sorting algorithm beformed better for Array B? Why?
    • Insertion Sort, the array was already mostly sorted, again see above paragraph.
  • When is it best to use each sorting algorthim? (think about how sorted a dataset is, the size of a data set, etc.)
    • Selection sort is better for non sorted arrays because of this, while Insertion sort utilizes less swaps as it does not need to swap already sorted elements, making it better for already sorted arrays. This also makes insertion sort impractical with its O(n^2) scaling for large datasets, as insertion sort will most definitely skip over some already sorted elements.

Queue Writeup

This is a writeup of the Queue feature.

Purpose

Too often, in class we line up to go up to present. This results in long lines of unproductivity. To solve this, the Queue feature can be used.
This feature is designed to

  • Allow people to stay at their seats while they are waiting to go up and continue working.
  • Organize what order so people do not rush and fight to present
  • Allow the teacher to keep track of who has and has not gone

Usage

Teacher

  1. Navigate to the following link for the teacher management site: LINK
  2. A modal will pop up. Choose an assignment to connect to Image 1
  3. At the top bar, select the same assignment, a presentation time, and a presentation group. The presentation time is in seconds. The presentation group determines which groups students will come present in Image 2
  4. Use the buttons to view gitHub profiles of students and statistics Image 3

Student

  1. Login to toolkit
  2. Make sure your name in your profile settings is set appropriately (NOT your gitHub ID)
  3. Navigate to the following link for student queue site: LINK
  4. When you are ready to present, click the add to waiting button. This will move your entire team over. Image 4
  5. When you are first in line, move to where you want to present. When you are ready, click the start timer button. This will begin your timer. Image 5
  6. When you are done, you will automatically be moved over to the completed column.

Documentation

Backend

TBA - Under Construction

Frontend

TBA - Under Construction