COMP SCI 300 Review

CS300 Speed Run any%

  • Date: 8 December 2025

Today's Topics

  • Java Basics

  • Object-Oriented Programming

  • Analysis

  • Linear Data Structures

  • Hierarchical Data Structures

Unit 1: Java Basics

Module 1: Procedural Programming

  • Oversize and Perfect Size Arrays

    • Explanation of arrays used in Java, focusing on their sizes.

    • Introduction to the ArrayList class, which is a resizable array implementation of the List interface.

  • Passing Arrays (Objects) to Methods

    • Shallow Copies:

      • This refers to copying the reference of the array rather than the complete array itself.

    • Deep Copies:

      • In contrast, a deep copy involves creating a new array and copying the elements, not just the reference.

Module 2: Using Objects

  • Wrapper Classes and Auto(un)-boxing

    • Wrapper Classes:

      • These are classes in Java that encapsulate primitive types (e.g., Integer for int, Double for double).

      • They provide methods to convert between types.

    • Auto-boxing:

      • The automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes.

    • Unboxing:

      • The reverse process of auto-boxing where the wrapper class object is converted back to its corresponding primitive type.

  • Stack vs Heap Storage

    • Primitives: Stored in the stack memory, which is faster and has a limited library size.

    • References + Objects: Stored in heap memory, which is larger and more flexible but slower to access.

  • Garbage Collection

    • The process by which Java programs perform automatic memory management.

    • Unused objects are identified and removed from memory to free up space.

Module 3: Exceptions

  • Why/When Exceptions Occur

    • Exceptions are events that disrupt the normal flow of a program's instructions.

  • Using throw to Make an Exception Happen on Purpose

    • Java enables programmers to deliberately throw an exception using the throw keyword.

  • Checked vs Unchecked Exceptions

    • Checked Exceptions:

      • Exceptions that must be either caught or declared in the method signature (e.g., IOException).

    • Unchecked Exceptions:

      • Do not need to be declared or handled (e.g., NullPointerException) and typically occur due to programming errors.

  • try/catch and throws

    • try: A block where you write code that may throw an exception.

    • catch: A block that handles the exception thrown by the try block.

    • throws: A clause that specifies that a method may throw certain exceptions, letting the caller decide how to respond.

  • Catching Multiple Kinds of Exceptions

    • Allows programmers to handle different exception types within a single catch block using multi-catch syntax.

Unit 2: Object-Oriented Programming

Module 4: Creating Classes

  • Classes vs Objects

    • Class: A blueprint for creating objects, sharing attributes and methods.

    • Object: An instance of a class that contains state (attributes) and behavior (methods).

  • Accessor Methods, Mutator Methods, and Constructors

    • Accessor Methods: Methods that retrieve data (getters).

    • Mutator Methods: Methods that set or update data (setters).

    • Constructors: Special method called when an object is instantiated to initialize variables.

    • Overloading Methods: Ability to define multiple methods with the same name but different parameters.

  • The this Keyword

    • Refers to the current object, allowing access to instance variables and methods.

  • Mixing and Matching Static and Instance Methods

    • Static methods belong to the class rather than instances.

    • Instance methods require creating an object of the class.

  • Encapsulation and Abstraction

    • Encapsulation: Bundling of data (attributes) and methods (functions) that operate on the data, restricting direct access.

    • Abstraction: Hiding complex implementation details and showing only essential features to the user.

Module 5: Inheritance and Casting

  • Parent vs Child Classes

    • Parent Class: Also known as a superclass from which properties are inherited.

    • Child Class: A subclass that inherits properties from a parent class.

  • Polymorphism

    • The ability for different classes to be treated as instances of the same class through inheritance.

    • Reference/Object Type Mismatching: When a child object is referenced by a parent class type.

    • When Can You Call a Method and Which Implementation Runs?

      • The object’s actual type determines which implementation of an overridden method gets invoked at runtime.

Module 6: Interfaces and Generics

  • Interfaces: Why?

    • Provide a way to achieve abstraction and multiple inheritance in Java. Interfaces define methods that must be implemented by classes.

  • Using Interfaces as Reference Types

    • Allows for writing code that works on the interface type rather than the specific class type, enhancing flexibility.

  • Generics: Why?

    • Enables types (classes and interfaces) to be a parameter to methods, classes, and interfaces, increasing code reusability.

  • Writing Generic Methods, Classes, and Interfaces

    • Syntax includes specifying a type parameter in angle brackets (e.g., <T>).

  • Using Generic Classes and Interfaces

    • Classes and interfaces can be defined to operate on a specified type parameter, leading to type safety.

Unit 3: Analysis

Module 7: Algorithm Analysis

  • Problem Size and Number of Operations

    • The performance of an algorithm is measured based on how execution time or space requirement grows as the problem size grows.

  • Big-O Notation

    • A mathematical notation that describes the limiting behavior of a function when the argument tends toward a particular value or infinity.

    • Common notations include:

      • $O(1)$: Constant time complexity, independent of input size.

      • $O( ext{log } N)$: Logarithmic time complexity, often seen in divide-and-conquer algorithms.

      • $O(N)$: Linear time complexity, where performance grows linearly with input size.

      • $O(N^2)$: Quadratic time complexity, where performance is proportional to the square of the input size.

Module 8: Recursion

  • Recursive Thinking

    • Solving a problem by having a function call itself to break the problem into smaller subproblems.

  • Base Case vs Recursive Case

    • Base Case: The condition under which the recursion stops.

    • Recursive Case: The condition that does not meet the base case, leading to further function calls.

  • Complexity Analysis for Recursive Methods

    • Involves determining time complexity based on the number of recursive calls and the complexity of operations done at each call.

    • Code Complexity: The overall time complexity of the recursive function.

    • Number of Recursive Calls Made: Essential for establishing how deep the recursion goes and potential for stack overflow.

Module 9: Sorting and Search

  • Search Algorithms

    • Linear Search:

      • A straightforward searching method that checks each element one by one.

      • It is easy to implement but inefficient for large datasets.

    • Binary Search:

      • An efficient algorithm that requires sorted data, repeatedly dividing the search interval in half.

  • Sorting Algorithms

    • Selection Sort:

      • Continuously selecting the next best value for sorting.

    • Insertion Sort:

      • Inserting the next value into the already sorted portion of the list.

    • Merge Sort:

      • Divides the array into halves, sorts, and then merges the sorted halves.

    • Quicksort:

      • A highly efficient sorting algorithm that sorts by partitioning the array based on a pivot element.

    • Heapsort:

      • Involves creating a max-heap or min-heap from the array, then extracting elements in sorted order.

Unit 4: Linear Data Structures

Module 10: Lists

  • ListADT

    • An abstract data type defining a collection of elements with certain operations.

  • Singly- vs Doubly-Linked Lists

    • Singly Linked Lists: Each node has a reference to the next node only.

    • Doubly Linked Lists: Each node has references to both the next and previous nodes.

  • ListNodes

    • Basic building blocks of linked lists containing data and references to adjacent nodes.

  • Head and Tail References

    • Head: The first node in a linked list.

    • Tail: The last node in a linked list.

  • Iterating Through a List Using a Temporary Node Reference

    • A temporary node reference is used to traverse the list without losing the original head reference.

  • Complexity Analysis of Linked Lists vs ArrayLists

    • Comparison of the efficiency in time complexity for insertion, deletion, and access operations.

    • Insert at Front of List: $O(1)$ for linked list; $O(N)$ for array list due to shifting elements.

    • Access Element by Index: $O(N)$ for linked list traversing nodes; $O(1)$ for array list due to direct indexing.

Module 11: Stacks, Queues, and Iterators

  • LIFO vs FIFO

    • LIFO (Last In First Out): Structure of stacks where the last element added is the first to be removed.

    • FIFO (First In First Out): Structure of queues in which the first element added is the first to be removed.

  • Complexity Analysis of Stack and Queue Operations

    • Operation complexities for both singly linked list implementations and array-based implementations.

  • Iterators

    • Enable sequential access of elements in a collection without exposing the underlying structure.

  • Why?

    • Promote flexibility in the handling of collections and allow for easier traversal.

  • Iterator vs Iterable Interfaces

    • Iterator: Contains methods like next() to get the next element and hasNext() to check if more elements exist.

    • Iterable: An interface with a method iterator() for obtaining an instance of an iterator.

Unit 5: Hierarchical Data Structures

Module 12: Binary Search Trees

  • [Binary] Trees and Terminology

    • Root Nodes: The topmost node in a tree.

    • Leaf Nodes: Nodes without children.

    • Height of a Tree: Defined as the longest path from root to leaf, can be counted by nodes or edges.

  • Inserting and Searching in a BST

    • Rules for placing nodes based on comparisons.
      Example illustrating insertion or searching process in a binary search tree.

  • Removing from a BST

    • Ensuring the properties of a binary search tree are maintained after deletion.

  • Traversals

    • Different methods to visit all nodes in a tree:

      • Pre-order Traversal: Visit root node, then left child, then right child.

      • In-order Traversal: Visit left child, root node, then right child (results in sorted order for BST).

      • Post-order Traversal: Visit left child, then right child, and finally the root node.

Module 14: Priority Queues and Heaps

  • PriorityQueueADT

    • Abstract data type for managing a collection of elements, where each has a priority. Elements are served based on priority rather than the order they were added.

  • Heap Conditions and Structure

    • Min Heap: A complete binary tree where the value of each node is less than or equal to the values of its children.

    • Max Heap: A complete binary tree where the value of each node is greater than or equal to the values of its children.

  • Inserting and Removing with Heaps

    • Methods for maintaining the heap structure during insertion and removal operations.

  • Heapsort and Heapify

    • Heapify: The process of converting an array into a heap structure.

    • Heapsort: A comparison-based sorting algorithm that leverages the heap data structure to sort elements.

Course Evaluation and Feedback

  • Students are encouraged to provide feedback about the course experience through the provided link.

  • Evaluation details:

    • COMP SCI 300 - Programming II

    • Final CS Fall 2025 Course Evaluation (Student Course Evaluation)

    • Sections: COMP SCI 300-001 and COMP SCI 300-002

    • End Date: 2025-12-10 (3 days period)

    • Results Available: 2025-12-25

    • Participation Rates: 43 of 142 responses (30%) for Section 001 and 37 of 142 responses (26%) for Section 002.