COMPSCI Notes MON 4/20

Attendance was taken at the beginning of the class.
Last week of classes is next Wednesday, which is two days from today (Thursday is the final Thursday of the semester).
A small lab final exam will occur this Thursday.

The lab final will involve a data structure that students have not encountered before but resembles structures studied in the latter half of the semester.
Examples of previous structures include stacks and queues.
Students will need to show how to implement the given data structure using either an array list or linked list, and this will be provided during the exam.
Suggestion for study: focus on creating stacks using both a linked list and a partially filled array.
The data structure for the final is not a made-up one; it is a known, useful structure.

The next topic in the course is searching and sorting algorithms.
Searching involves locating items within containers, and sorting makes searching easier by organizing data.

Definition: Sequential search refers to the method of searching through items one at a time in sequence when the data is unsorted.
Example: Searching for a specific paper in a shuffled stack, where you examine each item in the order they appear.
How it works: Start at one end (either beginning or end) and inspect each item until the target is found or all items have been checked. - It can also be thought of as looking through other unsorted collections (baseball cards, etc.).
If the item is not present, the search will go through every element to confirm this.
Algorithm Structures: A sequential search can be written with the following method header: java public static int search(Object[] r, Object target)    - Process: Iterate through the array using a for loop from the first index to the length of the array. - If an element at index i matches the target (using equals for object comparison), return the index i. If the target is not found, return -1 after completing the search through the array.
Run Time Complexity: - Worst Case: $O(n)$ if the target is at the last index or not present. - Successful searches take up to $O(n)$ as well.

Finding the smallest or largest element in an unsorted array also requires checking each element, thus the time complexity remains $O(n)$ .
For a sorted array, finding the smallest element takes constant time $O(1)$ , as it is at index 0, while identifying the largest element takes $O(1)$ as well, found at the last index.

Concept: When the data is sorted, a more efficient searching method called binary search can be utilized.
Methodology of Binary Search: You look for the middle item to determine whether to search in the left or right half of the array: - If the target is less than the middle item, continue the search in the left half. - If the target is greater, search in the right half. - This halves the number of elements to check iteratively.
Recursive Implementation: 1. Check if the current search set is empty; if so, return -1. 2. Determine the middle index and compare it to the target. 3. Depending on the comparison, perform the binary search again on either the left or the right half of the array.
Base Cases: Check whether the size is 0 (return -1 if so) or if the middle element matches the target (return the index if it does).
Complexity: - Successful Search: $O(log n)$ - Unsuccessful Search: $O(log n)$

Sequential Search on 8,000,000,000 elements would take up to 8,000,000,000 time units for the worst case.
Binary Search on 8,000,000,000 elements: - Based on the logarithm, it would take $ext{log}_2(8,000,000,000) ext{ which is approximately } 33 ext{ iterations or time units}.$

Binary Search is significantly more efficient for searching in sorted arrays compared to Sequential Search's linear method.
Understanding the underlying data structure and how it impacts the choice of search algorithm is crucial for efficient programming.

Students should review the provided topics and clarify any doubts before the lab final on Thursday.