The schedule below shows the tentative dates for all class topics, readings, and major assignments (MPs and SoLAs). You should complete all assigned readings by 10 p.m. on the night before the class in which they are listed. You should complete all lab writeups before the next class session. You can find the full list of due dates on Gradescope.
Due dates for major assignments will not change. However, the particular topics we cover each day may change as we discover that we need more (or less) time on each topic.
If the title of a class session is blue, you should be able to click on it to view the eboard for that class session.
If you view this page with JavaScript enabled you can jump to the current week on the schedule, and you should see the next day of class highlighted in the schedule below.
We begin the course by exploring some key ideas. We also practice ADT and data structure design.
Topics: Course goals. Course structure. Academic honesty. ADTs and data structures. Designing a fraction ADT. A bit about OOP.
We consider some basic issues of Java programming.
Topics: From C to Java. The structure of a Java program. Compiling and running Java programs. Strings in Java. Numeric types in Java. Arrays in Java. Basic output in Java. Basic input in Java.
We consider tools for developing programs in Java, particularly the Microsoft VSCode integrated development environment (IDE) and the Git version control system.
Topics: IDEs. VSCode basics. Version control. Git basics.
We consider Java’s approach to objects, the primary building block of object-oriented programming. We also explore Java’s classes and how one might model them.
Topics: Object basics. Modeling objects with classes.
We return to concepts of unit testing and habits of debugging that you first learned in CSC 151. We also introduce the concept of test-driven development, common among agile developers.
Topics: A few thoughts on testing. An example. Test-driven development. Why use debuggers. Debugging vs. print statements. Debugging in VSCode.
We consider interfaces, which serve as specifications of expected behavior for classes. We also explore how interfaces support one form of polymorphism, a key aspect of object-oriented programming.
Topics: Detour: Pair Programming, Revisited. Interfaces. The building blocks of OOP. Subtype polymorphism.
We continue our explortation of polymorphism by considering a second type of polymorphism, parametric polymorphism, and its realization in Java’s generics.
Topics: Parametric polymorphism. Java generics. Generic classes. Generic interfaces. Generic methods. Generics and arrays.
We introduce exceptions and consider their use.
Topics: Exceptions. Object-oriented design.
We practice some design in preparation for MP4.
Topics: ADT design, revisited. Data structure design, revisited. Dictionaries. Associative arrays.
We consider inheritance, other core aspects of object-oriented design. We also consider some underlying issues in the design and implementation of objects in Java and how we might represent objects visually.
Topics: Inheritance basics. Inheritance and polymorphism. Composition. Compile time vs. run time. References. Representing objects.
We consider a few basic structures, such as queues and stacks, and generalize them to linear structures. We explore ways in which arrays and simple linked objects can be used to implement linear structures. We practice building linked linear structures.
Topics: The design of ADTs, revisited. A list ADT. Linear structures. Stacks. Queues. Priority queues. Other linear structures. Implementing linear structures with arrays. Implementing linear structures as linked structures.
We explore ways in which arrays can be used to implement linear structures.
Topics: Detour: Wrappers. Implementing linear structures with arrays. Array-based queues. Priority queues and their implementation.
We consider iterators, a standard mechanism for accessing the elements of a collection, and explore the use of Java’s anonymous inner classes to build iterators. We consider comparators, a standard mechanism for comparing values, and explore the use of Java’s lambdas to implement comparators.
Topics: Iterators. Iterating array-based structures. Iterating linked linear structures. Named iterators. Anonymous inner classes. Anonymous functions reviewed. Anonymous functions in Java. Functional interfaces.
We consider ways to analyze the resource use of algorithms, including formal notation for describing that use.
Topics: Comparing algorithms. Empirical analysis. Asymptotic analysis. Counting steps. Big-O, formalized. Implications of Big-O. Practice with Big-O. Comparing Big-O and empirical approaches.
We consider techniques for analyzing recursive algorithms.
Topics: Iterative analysis, revisited. Recurrence relations. Approaches to recurrence relations.
We consider the problem of searching a collection and techniques for searching various kinds of collections. We also consider loop invariants, a technique for helping ensure the correctness of programs.
Topics: Modeling the problem of searching. Sequential search. Predicates. Binary search. Comparators. Testing binary search. Reasoning about iterative algorithms. The state of a program. Loop invariants.
We return to the problem of sorting a list or array.
Topics: The problem of sorting. Testing sorting algorithms. Insertion sort. Selection sort. Generic sorts.
We consider the classic merge sort and Quicksort algorithm.
Topics: Lower bounds on sorting. Divide-and-conquer algorithms. An introduction to merge sort. Analyzing merge sort. A quick introduction to Quicksort. Partitioning. Partitioning with invariants. Key ideas from Quicksort.
We explore more sophisticated versions of the linked-list data structure
Topics: Linked lists, reviewed. Doubly-linked lists. Circularly-linked lists. Other list issues.
We consider our responsibilities as programming professionals. We also compare sorting algorithms from the latest mini-project.
Topics: Professional ethics.. Sorting competition.
We introduce the tree structure and mechanisms for iterating trees.
Topics: Representing hierarchical information. Tree terminology. Depth-first and breadth-first traversal. Recursive depth-first traversal. Iterative breadth-first traversal. Iterative depth-first traversal. Pre-order, in-order, and post-order traversals.
We introduce the Dictionary (a.k.a. Map) abstract data type and some simple implementations.
Topics: Maps and dictionaries. Designing a Dictionary ADT. Associative arrays. Association lists.
We consider hash tables, one of the most efficient implementations of the Map abstract data type. We also explore the issue of hash functions.
Topics: Integer maps. From objects to integers. Handling collisions. Rebuilding hash tables. Hash functions.
We explore the two primary collision-resolution mechansims in hash tables.
Topics: Collisions. Linear probing. Quadratic probing. Buckets and chaining.
We return to the subject of priority queues and consider heaps, one of the more efficient ways to represent priority queues.
Topics: Priority queues, revisited. The heap structure. Adding elements to heaps. Removing elements from heaps. Storing trees in arrays.
We consider a graph abstract data type and some common implementations of graphs.
Topics: Modeling problems with graphs. Graph terminology. Weighted graphs. Directed graphs. Implementing graphs with adjacency matrices. Implementing graphs with adjacency lists. Implementing graphs with edge tables.
We consider how to build minimum spanning trees in graphs
Topics: Minimum spanning trees. Strategies for building minimum spanning trees. Kruskal’s algorithm. Prim’s algorithm. Greed as an approach to algorithm design.
We conclude the course.
Topics: The subject matter(s) of the course. Debrief. Course evaluation.
All work for the class is due on Friday of finals week.