CSCI 1913 Spring 2026

Documents

Part 1 – Python and the study of Algorithms

Module 00 - Course Overview

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 CSCI1913 is a course for you (if you fit the audience)
  • Prepare for what we will do to learn, and why.

Documents

Slides

Attendance

Module 01 – Intro to Python

In this module we’ll jump right into some practical python programming. By the end of this module you will be able to:

  • Read basic python programs and predict their behavior
  • Write basic python functions

Slides

Lecture Recording

In-class exercise

Module 02 – Python

We will continue working with Python. In this module we will finish discussing basic python features with a few final details of pyhton’s many scopes, in particular how you can import functions from other files – and some unique details about how this works in python.

Then we will begin exploring Python’s advanced data representation tools: data structures. Data structures create a flexible way to represent many common forms of data in an ad-hoc way without creating specific classes, or writing tricky data-management code.

We will be focusing on the List this week, which is python’s answer to the array. Towards the end of the week we will introduce the set and dictionary as well, with the plan to finish them next week.

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

  • Read, write, run, test, and debug simple python programs
  • Identify a list, tuple, and dictionary as represented in python code
  • Create, and loop over python lists

Slides

In-class exercises

Lecture Recordings

Computer Lab 01

Computer Lab 02

Module 03 – Advanced Python

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

  • Explain the concept of mutability and distinguish between mutable and immutable data types in Python, providing examples of each and describing the implications for variable assignment and function parameters.
  • Create and manipulate Python lists using various methods including indexing, slicing, appending, inserting, removing, and sorting elements, while understanding the performance characteristics of these operations.
  • Analyze the behavior of list aliasing and copying, explaining the difference between shallow and deep copies and predicting how changes to one list reference will affect others.
  • Create and manipulate dictionaries to store and retrieve key-value pairs, using appropriate methods for adding, updating, removing, and accessing elements.
  • Iterate over dictionaries using various approaches (keys, values, items) and understand the implications of dictionary ordering in modern Python versions.
  • Apply dictionaries to solve practical problems such as counting occurrences, grouping data, creating lookup tables, and representing structured information.
  • Use sets for membership testing and duplicate elimination, understanding when sets are preferable to lists for specific operations and leveraging their O(1) average-case lookup performance.
  • Perform set operations including union, intersection, difference, and symmetric difference to solve problems involving collections and relationships between groups.
  • Select appropriate data structures (lists, dictionaries, or sets) based on the requirements of a given problem, justifying choices based on performance, functionality, and code clarity.

Slides

In-class exercises

Lecture Recordings

Computer Lab 03

Module 04 – Big O notation, and searching

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

  • Analyze the time complexity of simple algorithms by identifying the relationship between input size and running time.
  • Express algorithm efficiency using Big-O notation and correctly classify common complexity classes including O(1), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ).
  • Compare algorithms based on their asymptotic behavior and determine which algorithm is more efficient for large inputs by analyzing their Big-O classifications.
  • Distinguish between best-case, average-case, and worst-case time complexity and explain when each measure is most relevant.
  • Implement linear search and binary search correctly in code and trace their execution on sample datasets.
  • Analyze the time complexity of linear search as O(n) and binary search as O(log n) and explain why binary search is asymptotically faster.
  • Explain why binary search requires sorted data as a precondition and demonstrate how the algorithm eliminates half of the remaining search space with each comparison.

Slides

In-class exercises

Computer Lab 04

Module 05 – Sorting

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

Computer Lab 05

Module 06 – Recursion

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

  • Define and explain recursion as a problem-solving technique where a function calls itself with modified parameters to solve progressively smaller subproblems.
  • Identify the essential components of a recursive function, including the base case(s) that stop recursion and the recursive case(s) that break down the problem.
  • Convert simple iterative solutions to recursive solutions and vice versa, recognizing when each approach is more appropriate.
  • Apply recursion to solve problems involving naturally recursive data structures or definitions, such as computing powers, reversing strings, or processing nested lists.
  • Debug recursive functions by identifying common errors such as missing base cases, incorrect recursive calls, or infinite recursion.

Slides

Project 1

Midterm 1

Part 2 – Java and the study of Object Oriented Programing

Install Java 23 (JDK23)

Steps to install Java:

For Windows:

  1. Download the file: Java 23 (select JDK 23 and Windows)
  2. Double Click and Install.

For Linux:

  1. Download the file: Java 23 (select JDK 23 and Linux)
  2. Double Click and Install.

PART B: Installing Intellij

Jetbrains provides comprehensive instructions for installing Intellij. If you are still having trouble, ask a TA during lab or office hours for help. Download the community edition (you will have to scroll down to find a community edition option).

Module 07

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

  • Identify the role of each component in a Java program, including class definition, main method, variable declarations, and method signatures
  • Distinguish between primitive types (int, double, boolean, char) and reference types (objects) in a given program
  • Write a complete, compilable Java program with a main method
  • Declare and initialize variables of appropriate types
  • Write conditional statements and loops to control program flow
  • Define and call methods with parameters and return values
  • Instantiate objects from existing classes using constructors
  • Call instance methods on objects and use the returned values
  • Explain the difference between a class and an object
  • Access and interpret the state of an object through its methods
  • Use objects from the Java standard library (e.g., String, Scanner)

Slides

Gradescope Exercises

Lecture Recordings

Computer Lab 06

Module 08

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

  • Explain what inheritance is and why it is useful for organizing and reusing code
  • Identify the relationship between a superclass and a subclass in a class hierarchy
  • Use the extends keyword to create a subclass that inherits fields and methods from a superclass
  • Use the super keyword to call a superclass constructor or to access a super instance variable
  • Determine which fields and methods a subclass inherits, overrides, or adds
  • Override a method in a subclass and explain how Java determines which version of the method to call at runtime
  • Override toString in a subclass to return a meaningful string representation of an object
  • Override equals in a subclass to compare two objects based on their field values rather than reference
  • Distinguish between abstract classes and concrete classes and explain when to use each
  • Define method overloading and distinguish it from method overriding
  • Write multiple versions of a method with the same name but different parameters
  • Identify which overloaded method Java will call given a specific set of arguments
  • Define an abstract class with abstract and concrete methods
  • Implement a concrete subclass that provides implementations for all abstract methods
  • Explain why abstract classes cannot be instantiated directly
  • Design a class hierarchy using abstract and concrete classes to model a real-world problem

Slides

Gradescope

Lecture Recordings

Computer Lab 07

Computer Lab 08

Project 2

Midterm 2

Part 3 – The design and implementation of Data Structures

Module 09

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

  • Define the concept of an abstract data type (ADT) and explain how it separates interface from implementation.
  • Use Java interfaces to specify the contract for a data structure without prescribing its implementation.
  • Explain what parametric polymorphism is and why generics are useful for writing flexible, reusable code
  • Read and interpret generic class and method declarations that use type parameters (e.g., )
  • Instantiate generic classes with specific type arguments (e.g., MyClass)
  • Implement a simple generic class or method that works correctly for multiple data types
  • Explain the benefit of generics over using Object as a universal type, particularly with respect to type safety
  • Design and write a generic List interface in Java that includes core operations (e.g., add, remove, get, size, isEmpty).
  • Implement the List interface using an array-backed structure, managing resizing and index-based access.
  • Describe the structure of a singly linked list, including the role of nodes, data fields, and next pointers.a
  • Trace the state of a linked list (drawing boxes and arrows) after a
    sequence of insertions and deletions.
  • Implement the List interface using a singly linked list, managing node creation, pointer manipulation, and traversal.
  • Compare the array-based and linked-list implementations with respect to time complexity for common operations (e.g., access, insertion, deletion at head/tail/middle).
  • Explain why linked lists have \(O(1)\) insertion/deletion at the head but \(O(n)\) access by index, and contrast this with arrays.
  • Select an appropriate List implementation for a given use case based on its performance trade-offs.

Slides

Gradescope

Computer Lab 09

Computer Lab 10

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

Computer Lab 11

Gradescope

Project 3

Computer Lab 12