The schedule below shows the tentative dates for all class topics, readings, and assignments. You should complete all assigned reading before class on the day it is listed. Labs will be available shortly before the assigned lab day. There may be some revisions to the schedule during the semester, but I will make sure to announce these changes in class.
We begin the course by exploring some key ideas.
Topics: Course goals. Course structure. Academic honesty. ADTs and data structures. Designing a stack ADT (an exercise). 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 Eclipse integrated development environment (IDE) and the Git version control system.
Topics: IDEs. Eclipse 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.
Topics: Object basics. Modeling objects with classes. An exercise.
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 Eclipse.
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: 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: Subtype polymorphism, revisited. Parametric polymorphism. Java generics. Generic classes. Generic interfaces. Generic methods. Generics and arrays.
We consider lists and ways to think about them. We practice ADT design.
Topics: The design of ADTs, revisited. Scheme lists. Java lists. Quick notes on implementation.
We consider linear structures, such as queues and stacks. We explore ways in which arrays and simple linked objects can be used to implement linear structures.
Topics: Linear structures. Stacks. 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. We explore the use of Java’s anonymous inner classes to build iterators.
Topics: Iterators. Iterating array-based structures. Iterating linked linear structures. Named iterators. Anonymous inner classes.
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.
We continue our exploration of the analysis of algorithms.
Topics: Practice with Big-O. Comparing Big-O and empirical approaches.
We consider the problem of searching a collection and techniques for searching various kinds of collections.
Topics: Modeling the problem of searching. Sequential search. Predicates. Binary search. Comparators. Testing binary search.
We consider loop invariants, an important technique for designing iterative algorithms.
Topics: Reasoning about iterative algorithms. The state of a program. Loop invariants. Loop termination. An exercise: Binary search.
We pause to discuss the first examination and to explore current complexities and confusions
Topics: Testing. Linked structures and iterators. Additional issues.
We continue to discuss the first examination and to explore current complexities and confusions
Topics: Array-based queues. More testing.
We return to the list ADT and explore how to implement lists using arrays.
Topics: A simple list interface. The java.util.List interface. The java.util.ListIterator interace.
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 introduce the Map (a.k.a. Dictionary) abstract data type and some simple implementations.
Topics: Maps and dictionaries. Associative arrays. Association lists.
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 continue our exploration of binary search trees.
Topics: Deletion in BSTs.
We consider hash tables, one of the most powerful 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 one of the two primary collision-resolution mechansims in hash tables.
Topics: Collisions. Linear probing. Quadratic probing.
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 the 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. Looking ahead. Course evaluation.