CSCI 1933 Spring 2026

Documents

Module 00

The goal of this module is to provide an overview of the course.

For this module we will focus first-and-foremost on getting the class started. We’ll be seeing the basic class design, learning what are the parts of the class, and how they will help us learn.

By the end of the week you should be able to:

  • Decide whether CSCI 1933 is a course for you (if you fit the audience)
  • Prepare for what we will do to learn, and why

Slides

Lecture Recording

Module 01

Introduction to Java, Java data, Java Program Structure

By the end of this module, you will be able to:

  • Write, compile, and execute simple Java programs, demonstrating understanding of basic Java syntax and the program development workflow
  • Identify and explain the essential components of a basic Java program structure, including the class declaration, main method signature, and statement syntax.
  • Recognize and correct common syntax errors in simple Java programs using compiler error messages as guidance.

Slides

Lecture Recording

Module 02

Java primitive vs. Object types, object instantiation and methods, classes

By the end of this module, you will be able to:

  • Distinguish between primitive and object types in Java by identifying their key characteristics, including how they store data, their default values, and how they are store in memory
  • Create and initialize objects using constructors, including the use of multiple constructor overloads and explain the role of the new keyword in object instantiation.
  • Compare value equality versus reference equality by appropriately using == for primitives and .equals() for objects, and explain why this distinction matters.
  • Identify and write the different types of methods including setters, helpers, and operators
  • Identify when to use private and public for attributes and methods

Slides

Attendance

Lecture Recording

Module 03

By the end of this module, you will be able to:

  • Differentiate between static and non-static attributes, identify the appropriate uses of the static keyword
  • Apply principles of inheritance (every class in Java inherits from Object class) by writing .equals() and .toString() methods (overriding)
  • Import and instantiate the Scanner class to enable user input functionality in Java programs, and use appropriate Scanner methods (nextInt(), nextDouble(), nextLine(), next(), etc.) to read different data types from the console.
  • Implement input validation techniques to ensure user-provided data meets program requirements before processing.

Slides

Video Recordings

Gradescope exercises

Module 04

By the end of this module you will be able to:

  • Explain the difference between recursive and iterative approaches to problem-solving
  • Describe how the call stack operates during recursive function execution
  • Identify the base case and recursive case in a recursive algorithm
  • Recognize problems that are naturally suited to recursive solutions versus iterative solutions
  • Solve problems involving mathematical sequences, string manipulation, and array processing
  • Implement helper methods to facilitate recursive solutions when additional parameters are needed

Slides

Gradescope exercises

Lecture Recordings

Module 05

By the end of this module you will be able to:

  • Declare and initialize arrays in Java using the syntax type[] arrayName = new type[size]; and type[] arrayName = new type[]{1, 2, 3, 2};
  • Explain how arrays in Java differ from Python list creation in terms of type specification and fixed size requirements.
  • Compare and contrast Java arrays with Python lists, identifying key differences including fixed length, homogeneous typing, and memory allocation, as well as similarities in zero-based indexing notation (square brackets – arrayName[0]).
  • Pass arrays as parameters to methods and predict the behavior of array modifications within methods, demonstrating understanding of reference semantics (that arrays are objects passed by reference).
  • Analyze the limitations of fixed-length arrays by explaining what happens when an array reaches capacity and why additional elements cannot simply be added as they can be in Python lists.
  • Implement array resizing techniques by creating a new, larger array and copying elements from the old array, recognizing this as a manual process unlike Python’s automatic list growth.
  • Choose appropriate array sizes based on problem requirements while understanding the trade-offs between allocating too much memory (wasted space) and allocating too little (requiring expensive resizing operations).
  • Access and modify elements in arrays of arrays using correct row-column indexing notation, demonstrating understanding that Java implements arrays of arrays as arrays of references.
  • Distinguish between shallow and deep copying of arrays of arrays, explaining why shallow copying only duplicates references to inner arrays rather than creating new array objects.
  • Write nested loops to traverse arrays of arrays in both row-major and column-major order, selecting appropriate iteration patterns for different algorithmic tasks.

Slides

Gradescope exercises

Lecture Recordings

Module 06

By the end of this module you will be able to:

  • Implement selection sort, insertion sort, and bubble sort correctly in code and trace their execution on small datasets.
  • Analyze and compare the time complexity of selection sort, insertion sort, and bubble sort in their best, average, and worst cases.
  • Explain the underlying mechanism of each sorting algorithm including how elements are compared, swapped, and positioned during execution.

Slides

Module 07

By the end of this module you will be able to:

  • Explain Big-O notation as an upper bound (worst case) measure of time complexity
  • Articulate why Big-O is used for algorithm analysis and predict how algorithm performance scales with increasing input sizes
  • Determine which operations in an algorithm contribute to time complexity
  • Apply the principle of dominant terms by identifying the highest order component in a complexity expression * Simplify complexity expressions by dropping constants and lower-order terms and justify why lower-order terms become negligible as input size grows
  • Analyze iterative algorithms to determine their Big-O complexity
  • Analyze nested loops and identify their combined complexity
  • Classify common algorithmic patterns by their Big-O complexity (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ))

Slides

In-class exercise

Module 08

  • Explain what an interface is and describe its role as a behavioral contract that a class must fulfill.
  • Distinguish between a concrete class, an abstract class, and an interface, identifying what can and cannot be instantiated.
  • Describe why a method might be declared without an implementation (abstract methods and interface method signatures).
  • Declare a Java interface with appropriate method signatures.
  • Implement an interface in a concrete class using the implements keyword, providing a body for every required method.
  • Declare an abstract class that includes a mix of abstract methods and fully implemented methods.
  • Write a concrete class that extends an abstract class and provides implementations for all abstract methods.
  • Predict which methods a concrete subclass must implement given an abstract class definition.
  • Justify when to use an interface versus an abstract class for a given design scenario.
  • Recognize common Java library interfaces (e.g., Comparable, Iterable) and explain what a class must provide to implement them.
  • Explain the purpose of the Comparable interface and why Java uses it to define a natural
    ordering for objects.

Slides

In-class exercises

Lecture Recordings

Module 09

By the end of this module you will be able to:

  • Explain the structure of a singly linked list, including the role of nodes, data fields, and next pointers
  • Compare and contrast linked lists with arrays, identifying trade-offs in terms of memory allocation, access time, and insertion/deletion efficiency
  • Implement a Node class in Java with appropriate instance variables and a constructor
  • Implement a LinkedList class in Java that maintains a reference to the head node
  • Write a method to add a node to a linked list (at the front, back, or at a given index)
  • Write a method to remove a node from a linked list by value or by index, correctly re-linking surrounding nodes
  • Write a method to search a linked list for a target value, returning its index or a boolean
  • Write a toString method that traverses the linked list and returns a human-readable string representation
  • Identify and handle edge cases such as an empty list, a single-node list, and operations at the head or tail
  • Define a stack and a queue and describe the core principle governing each:
    • Stack: Last In First Out (LIFO)
    • Queue: First In First Out (FIFO)
  • Identify real-world examples that model stack and queue behavior
  • Distinguish between a stack and a queue and determine which is appropriate for a given problem
  • Define and explain the purpose of each core stack operation: push, pop, peek, and isEmpty
  • Implement a stack in Java using either an array or a linked list as the underlying data structure
  • Explain the time complexity of each stack operation and justify why they are \(O(1)\)
  • Identify and handle edge cases such as popping from an empty stack (stack underflow)
  • Define and explain the purpose of each core queue operation: enqueue, dequeue, peek, and isEmpty
  • Implement a queue in Java using either an array or a linked list as the underlying data structure
  • Explain the time complexity of each queue operation and justify why they are \(O(1)\)
  • Identify and handle edge cases such as dequeuing from an empty queue (queue underflow)
  • Compare the implementation of stacks and queues using arrays versus linked lists, identifying trade-offs in each approach
  • Explain how the choice of underlying data structure affects the efficiency and complexity of stack and queue operations
  • Recognize that stacks and queues are abstract data types (ADTs) whose behavior is independent of their underlying implementation
  • Determine the time complexity of stack and queue operations for both array-based and linked-list-based implementations
  • Select the appropriate data structure (stack, queue, array, or linked list) for a given problem and justify the choice

Slides

In-class exercises

Module 10

By the end of this module you will be able to:

  • Define a binary search tree (BST) and describe the properties that distinguish it from a general binary tree
  • Explain the relationship between a node’s value and the values in its left and right subtrees
  • Trace the structure of a BST after a sequence of insertions and deletions by drawing diagrams
  • Identify whether a given binary tree satisfies the BST property
  • Implement in Java a Node class with a data field and left and right child references
  • Implement a BST class in Java that maintains a reference to the root node
  • Identify and handle edge cases such as an empty tree, a single-node tree, and deleting the root node
  • Write a recursive method in Java to insert a new value into a BST while maintaining the BST property
  • Write a recursive method in Java to search a BST for a target value, returning a boolean or the node
  • Define and distinguish between the following tree traversals and predict the output of each for a given BST: In-order, Pre-order, Post-order
  • Write a toString method that returns the elements of the BST in a meaningful order using traversal
  • Write a recursive method to delete a node from a BST, correctly handling all three cases: Node has no children (leaf), Node has one child, Node has two children (replace with in-order successor or predecessor)
  • Explain why the efficiency of BST operations depends on the height of the tree
    • Compare the best case (\(O(\log N)\)) and worst case (\(O(N)\)) time complexity for search, insert, and delete
    • Describe what a degenerate (unbalanced) BST looks like and explain how it arises from sorted input

Slides