COMPSCI Notes WED 4/22

Class Meeting Times: 8AM on Monday, Wednesday, and Friday
Exam Schedule: Final exam on Friday, May 1 at the same time, in the same room
Date of Last Class: Wednesday, April 28 (one week prior to the final exam)
Reading Day: Thursday, May 29 (class is completely off)

Lab Final Exam: Takes place on the day before the final lecture exam.
Important Instructions for Lab Final: - Students will be provided a data structure they have not covered this semester. - Data Structure Implementation: Use linked lists or arrays (similar to discussed structures like stacks and queues) - Practice tasks suggested: Implement stacks using linked lists and arrays. - Lab exam time limit: Must be finished by the end of the lab session.
Grading for Lab Final: - Structure points can be gained even if you do not obtain a specific grade on the lab final. - For passing: Students must achieve at least a 60% to pass the lab component of the course.

Definition: Start at the beginning of an unsorted array until the target element is found or all options are exhausted.
Time Complexity: $O(n)$ (linear growth)
Use Case: Primarily suitable for unsorted arrays.

Definition: A search algorithm that works on sorted arrays by checking the middle element of the array: - If the middle element is the target, the search finishes. - If the target is smaller, search the left half; if larger, search the right half.
Time Complexity: $O( ext{log}_2(n))$ active in binary splits.
Example: Searching through 8 billion elements results in 33 iterations.
Necessary Conditions for Use: The data must be sorted, and elements must be comparable.

Focus will be on five sorting algorithms categorized into two sections: - Quadratic Sorting Algorithms - Divide and Conquer Sorting Algorithms

General Definition: These algorithms exhibit a time complexity of $O(n^2)$ , which generally makes them slower.

Mechanism: For every index in the array, find the smallest remaining element and put it in the correct spot: - Start from the beginning of the array, find the smallest element, and place it at the first index. - Repeat until the array is sorted, with one less unsorted element each iteration.
Complexity Analysis: - Time Complexity: $O(n^2)$ - Comparisons: Need to compare all unsorted elements for every sorted index.

Mechanism: Build a sorted portion of the array by taking one element from the unsorted portion and placing it in the correct position: - Start with the first element as sorted; take the next element, and shift it leftward until it finds its correct position.
Complexity Analysis: - Worst Case: Reverse sorted input — $O(n^2)$ - Best Case: Already sorted array — $O(n)$ (only one comparison per element)

Comparison between Selection Sort vs Insertion Sort: - Selection Sort is always quadratic, regardless of input (best, average, worst), whereas Insertion Sort can be linear on sorted inputs, proving to be potentially faster in practice, especially when a list is partially sorted.
Future Discussions will cover additional sorting algorithms, including Bubble Sort and Divide and Conquer methods (like Merge Sort, Quick Sort).

Lab Final Reminder: Ensure all last-minute questions are addressed before the lab final exam.
Next Class: Review of covered algorithms and introduction to additional sorting algorithms (Bubble Sort).