CSE 143, Winter 2021: Calendar
This is a rough sketch of the quarter that is likely to change. We can accurately predict the past, but predicting the future is hard! In particular, all future assignment dates should be considered tentative and subject to change.
Welcome; Course policies; ArrayList
Ed lesson
Class recording (A)
BJP 10.1
Slides (pptx)
Slides (pdf)
ArrayIntList
- explain the difference between client and implementer
- implement a simple array-based list of integers
[Supp] More ArrayIntList; Pre/post conditions; Exceptions
- write overloaded methods
- write effective comments for instance methods
- identify and document pre- and post-conditions
- throw exceptions from methods when appropriate
Lists; Sets; for each loops
- Explain the benefits of using an interface type instead of a class type
- Identify considerations when choosing an appropriate data structure
- List the key operations of the List and Set ADTs
Stacks; Queues
- Use a for-each loop to iterate over a collection
- Use an
Iteratorto iterate over aSet - List and use the basic operations of stacks and queues
Linked list nodes
- explain the difference between a reference and an object
- define a class with a field of the same class and explain why this works
- write code to manipulate nodes of a linked list
No class - Martin Luther King Jr. Day
LinkedIntList
- traverse a sequence of linked list nodes
- implement a linked list class to store integers
- write code to add a new element to the end of a linked list
Advanced LinkedIntList
- efficiently construct a linked list from a collection of values
- insert values into a linked list
Complexity; Binary search
- define efficiency and describe different possible ways to measure it
- find the big-O complexity of simple algorithms
- compare algorithms to determine which is more efficient
- describe the binary search algorithm
Maps
- describe the Map ADT and list its main operations
- create and use a simple Map using the Java
Mapinterface - create and use a Map with a nested collection
More maps
Recursion
- define recursion
- trace the execution of recursive methods
More recusion; Public/private pairs
- write recursive methods
- define and explain public/private recursive pairs
Regular expressions; Grammars
- implement public/private recursive pairs
- explain and recognize Backus-Naur Form
- split strings using the Java
splitmethod and simple regular expressions
Recursive backtracking; Exhaustive search
More recursive backtracking
- implement exhaustive search using recursive backtracking
Sorting
- describe the approach of several sorting algorithms
- list the considerations in designing and choosing sorting algorithms
No class - Presidents' Day
Section cancelled
Binary trees
- describe and identify trees and binary trees
- implement a simple binary tree
- describe and implement pre-, in-, and post-order traversals of binary trees
Binary search trees
- describe the binary search tree property
- implement search on a binary search tree
- add values to a binary search tree
Generic binary search trees; Comparable
Inheritance
Implementing Comparable
- implement the
Comparableinterface
Two-dimensional arrays; Image manipulation
Priority queues; Huffman encoding
Hashing
Basic cryptography
EncryptionClient.java
Intro. to graphs
TA Choice
Victory lap; Closing thoughts