CompSci Notes FINAL APRIL 29tj

Final Exam Logistics and Format

• Date and Time: The final exam is scheduled for this coming Friday during the university-mandated final exam slot.
      * Time Window: $8:00\,AM$ to $10:30\,AM$.
      * Duration: Two hours and thirty minutes ($2.5$ hours). This is approximately $40$ minutes longer than the regular midterms.

• Location and Submission:
      * The exam must be taken in person.
      * The format is paper-based.

• Exam Structure:
      * The size of the exam will be approximately the same as the previous midterms to accommodate the limited extra time available.
      * Sections include Multiple Choice and Short Answer.

• Permitted Materials:
      * Cheat Sheets: Students are allowed two ($2$) cheat sheets of normal size ($8.5 \times 11$ inches), front and back. These can be the same sheets used for previous exams if desired.
      * Scrap Paper: Students may bring their own, though the instructor will also provide some.
      * Calculators: A standalone calculator is permitted; cell phone calculators are strictly prohibited.

• Scope and Content:
      * The exam is cumulative, covering all material discussed throughout the semester.
      * Higher emphasis (percentage-weighting) will be placed on the most recent material (stacks, queues, sorting).
      * Exclusion: GUI (Graphical User Interfaces) material will not be on the final exam.
      * Exclusion: Quick Sort will not be on the exam as it was not reached in the lectures.

Arrays and Data Structure Comparisons

• Skills Required:
      * Looping through two-dimensional ($2D$) arrays using nested for-loops.
      * Manipulating arrays, such as implementing a "roll left" method.
      * Building new arrays based on the data within existing arrays.

• Analysis of Arrays:
      * Pro: Constant Time Access: Arrays provide immediate access to any element at a given index in $O(1)$ time. This is possible because arrays are stored sequentially in memory, allowing for direct calculation of memory addresses.
      * Con: Fixed Size: The physical size of an array cannot be changed once initialized. To simulate a size change, a new array must be created and all data from the old array must be copied over, which is a linear operation ($O(n)$).
      * Con: Shifting Requirements: If elements are removed or inserted in a way that maintains a specific order (like a partially filled array), other elements must be shifted. Shifting takes linear time ($O(n)$).

• Partially Filled Arrays:
      * Requires a separate piece of data (usually an integer variable like manyItems) to track how many slots are actually in use.

Big O and Computational Complexity

• Conceptual Goal: Determining the efficiency of algorithms to avoid slow runtimes (e.g., avoiding $O(n^2)$ for large datasets).

• Rules of Thumb for Analysis:
      1. Constant Time ($O(1)$): Assignments, basic math ($x + y$), comparisons (x < y), and return statements.
      2. Method Calls: A method call is not automatically constant. The complexity of the specific method must be analyzed. For example, a sequential search method call on a list is $O(n)$.
      3. Consecutive Blocks: Sum the complexities of each block. In Big O notation, only the highest order term is kept (e.g., $1 + 1 + n$ simplifies to $O(n)$).
      4. Conditional Statements (If-Else): Take the runtime of the condition check plus the runtime of the most expensive branch. If a condition is a method call like list.search(), that must be factored in.
      5. Loops: Multiply the number of iterations by the runtime of the code inside the loop.

• Nested Loop Example:
      * An outer loop running $n$ times containing an inner loop running $n$ times results in $n \times n = O(n^2)$.
      * If the code inside the innermost loop is $O(n^2)$, and it is inside two nested loops each running $n$ times, the total complexity is $n \times n \times n^2 = O(n^4)$.

Exceptions and Error Handling

• Structure: Using try-catch blocks and the optional finally block.

• Checked vs. Unchecked Exceptions:
      * Understand the inheritance tree involving Throwable, Exception, and RuntimeException.
      * Checked Exceptions: Must be caught or declared (e.g., IOException). These inherit from Exception but not RuntimeException.
      * Unchecked Exceptions: Do not require explicit handling (e.g., NullPointerException). these inherit from RuntimeException.

The Object Class and Memory Management

• Clone Method: A very specific implementation is required to ensure usability. It involves the Cloneable interface.

• Shallow vs. Deep Copy:
      * Shallow Copy: The default super.clone() behavior; it copies primitive values but only copies references for object fields.
      * Deep Copy: Requires manual intervention to clone the objects referred to by fields so that the original and the clone do not share sub-objects.

• Memory Questions: Tracking the number of objects stored in memory during a sequence of operations.

Inheritance and Polymorphism

• Casting:
      * Widening Conversion: Converting a subclass to a superclass (implicit).
      * Narrowing Conversion: Converting a superclass to a subclass (requires explicit cast).

• Static vs. Dynamic Type:
      * Static Type: The type assigned to the reference variable at compile-time (what the compiler thinks the object is).
      * Dynamic Type: The actual type of the object in memory at run-time (what follows the new keyword).
      * Example: Student s = new GradStudent();. The Static Type of s is Student, and the Dynamic Type is GradStudent.
      * The compiler checks methods against the Static Type. Calling s.getThesis() fails if getThesis() is only in GradStudent and not in Student, requiring an explicit cast: ((GradStudent)s).getThesis();.

• The super Keyword:
      * Used to call the superclass constructor.
      * It must be the first line in the subclass constructor.
      * Example:
          public GradStudent(String name, String degree) {
        super(name);
        this.degree = degree;
        }

Linked Lists

• Manipulation: Difference between assignment (head = node2) which changes what the reference points to, and method calls (head.setLink(node2)) which changes the link field inside the node.

• Pros of Linked Lists:
      * Dynamic Size: Easily expandable.
      * Constant Time Size Changes: Inserting or removing elements at a known position is $O(1)$.
      * No Shifting: Maintaining the order of elements after removal only requires changing a reference, unlike arrays which require shifting the remaining elements.

• Cons of Linked Lists:
      * Linear Access Time: To reach the $i^{th}$ element, you must traverse from the head, resulting in $O(n)$ access time.

Sequences: DoubleArraySeq and DoubleLinkedSeq

• DoubleArraySeq: Uses an underlying array; efficient for random access but requires resizing and shifting.

• DoubleLinkedSeq: Uses an underlying linked list. It is more efficient for sequences because it uses a cursor pointer. Since sequences don't typically require random access to arbitrary indices, the linear access time of the linked list is negated, while the constant time insertion/removal becomes a significant benefit.

• Invariants: Understand how fields like head, cursor, precursor, and manyNodes maintain the state of the data structure.

Generics and Iterators

• Generics: Convert classes and methods using a type parameter (e.g., <T> or <E>). Static methods inside generic classes must be individually parameterized.

• Iterators:
      * Iterable (Interface): Requires the method iterator(), which returns an Iterator object.
      * Iterator (Interface): Requires methods like hasNext() and next().
      * Usually implemented as a unique inner class for a specific container.

Stacks and Queues

• Stacks (LIFO: Last-In, First-Out):
      * Tracing operations: push, pop, peek.
      * Applications: Infix to Postfix conversion and evaluating Postfix expressions using a stack.

• Queues (FIFO: First-In, First-Out):
      * Tracing operations: add (enqueue), remove (dequeue).
      * Circular Array Implementation:
          * Purpose: To avoid the linear $O(n)$ shifting cost of a regular partially filled array when the front element is removed.
          * Memory Efficiency Myth: A circular array of size $10$ is not more memory-efficient than a standard array of size $10$; they store the same number of elements. The efficiency gain is purely in Time Complexity (shifting avoidance).

• Radix Sort: An application of queues. It sorts data one column at a time from right to left (least significant digit to most significant digit).

Recursion

• Concept: A method that calls itself.

• Components:
      * Base Case: The condition that stops the recursion.
      * Recursive Call: The statement where the method calls itself with a reduced problem.

• Example Tasks: Extracting or printing one digit of a number at a time (using / 10 and % 10). Students should be prepared to trace recursive calls and identify base cases.

Searching and Sorting Algorithms

• Searching:
      * Sequential Search: $O(n)$. Works on unsorted data.
      * Binary Search: $O(\log(n))$. Requires sorted data.

• Sorting:
      * Selection Sort: Finds the smallest element and swaps it into the current position. Best case is $O(n^2)$ because it always searches the entire unsorted portion.
      * Insertion Sort: Picks the next element and inserts it into its correct place among previously sorted elements. Best case is $O(n)$ if the array is already sorted.
      * Bubble Sort: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
      * Merge Sort: A divide-and-conquer algorithm with a guaranteed runtime of $O(n \log(n))$.