Link Search Menu Expand Document
CSE 143

Programming with Data Structures

Computer Programming II, Autumn 2020

Kevin Lin he/him

kevinl@cs.uw.edu

Schedule a meeting

Computer science is the study of how our ideas can be automated and amplified with computers. Computation is distinctly sociological: computation is defined by humans for humans, so in turn computation defines how we experience life.

In CSE 143, we will learn how to write apps that use data to support everyday life, to answer questions about the world around us, and to make decisions that affect (and oftentimes reinforce) social hierarchies and power structures. By the end of the course, you will be able to:

  1. Define externally correct and internally correct programs within larger software systems.
  2. Select and apply abstract data types to solve specified problems by managing program state.
  3. Compare tradeoffs to select the appropriate implementation for a program or abstract data type.
  4. Design and modify data structures capable of insertion, deletion, search, and related operations.
  5. Trace through and predict the behavior of programs involving reference data types and recursion.
  6. Apply functional decomposition and recursion to break down problems into subproblems.

CSE 143 is organized around 7 applications of computing, a group project of your own choosing that applies programming with data structures, and a video problem solving portfolio where you teach these programming skills to others.

Read more…

Autocomplete

Sep 30
Welcome to CSE 143
BJP 8
Oct 1
SectionObjects
Oct 2
Comparable
BJP 9.5, 10.2
  1. Describe the relationships between client vs. implementer and interface vs. class.
  2. Define methods that accept instances of the same class as parameters.
  3. Define classes that implement public interfaces such as Comparable.

Letter Inventory

Oct 5
ArrayIntList
BJP 10.1, 15.1, 15.2
  1. Define classes with an array (storing primitive data types or strings) as a field.
  2. Define methods that reassign field values while maintaining class invariants.
  3. Document pre/post conditions and throw exceptions to report problems to clients.
Oct 6
SectionArrayIntList
Oct 7
Stacks and Queues
BJP 14
  1. Define static methods that accept multiple objects as parameters.
  2. Loop over each item in a queue using the add, remove, and size methods.
  3. Loop over each item in a stack, storing popped items in another queue or stack.
Oct 8
SectionStacks and Queues
Oct 9
Algorithm Analysis
BJP 13.2
  1. Apply the runtime analysis process to formally describe an algorithm’s runtime.
  2. Describe an example where a queue or stack would be preferred over a list.
  3. Explain why ArrayList does not implement the Queue interface.

Search Engine

Oct 12
Sets and Maps
BJP 11.2, 11.3
  1. Describe an example where a set would be preferred over a list, and vice versa.
  2. Loop over each item in a collection (or an array) with a for-each loop.
  3. Apply the if-missing-then-put pattern to provide default map values.
Oct 13
SectionSets and Maps
Oct 14
Nested Collections
  1. Trace the execution of programs with reference data types.
  2. Define methods that use collections containing other collection types.
  3. Describe the relationship between object reference equality vs. value equality.
Oct 15
SectionNested Collections
Oct 16
Linked Nodes
BJP 16.1
  1. Evaluate and reassign variable references to deeply linked nodes.
  2. Trace the execution of programs with references to deeply linked nodes.
  3. Identify and apply additive changes before destructive linked node changes.

DNA Strand

Oct 19
LinkedIntList
BJP 16.2
  1. Designate private visibility to encapsulate nested classes.
  2. Trace the execution of programs with nested object references.
  3. Apply the standard traversal pattern to loop over each item stored in linked nodes.
Oct 20
SectionLinkedIntList
Oct 21
Verification
BJP 16.3
  1. Define methods that handle the empty, front, middle, and end linked node cases.
  2. Explain why LinkedList (unlike ArrayList) implements the Queue interface.
Oct 22
SectionVerification
Oct 23
Recursive Tracing
BJP 12.1, 12.2
  1. Trace the execution of programs with method calls by transferring control.
  2. Trace the execution of programs using stack frames each with their own variables.
  3. Trace the execution of programs with a single recursive call.

Language Generator

Oct 26
Recursive Programming
BJP 12.3, 12.4
  1. Apply the three-step outline to define programs with a single recursive call.
  2. Define recursive programs by passing parameters to a private helper method.
Oct 27
SectionRecursive Programming
Oct 28
Structural Recursion
  1. Define public/private paired recursive programs to traverse linked nodes.
  2. Apply the x = change(x) pattern to recursively change linked node references.
Oct 29
SectionStructural Recursion
Oct 30
Generative Recursion
  1. Trace the execution of programs with more than one recursive call.
  2. Define generative recursive programs that create new data on each recursive call.

Election Simulator

Nov 2
Recursive Enumeration
BJP 12.5
  1. Trace the execution of programs that recursively build-up solutions.
  2. Define public/private paired recursive enumeration programs.
Nov 3
SectionRecursive Enumeration
Nov 4
Recursive Optimization
  1. Apply the choose-explore-unchoose pattern to recursively build solutions.
  2. Define public/private paired recursive optimization programs.
Nov 5
SectionRecursive Optimization
Nov 6
Notional Machine
BJP 9.1, 9.2, 9.3, 9.4
  1. Determine the compile-time method signature for a given code snippet.
  2. Determine the method ultimately called at runtime for a given code snippet.

Text Classifier

Nov 9
Binary Trees
BJP 17.1, 17.2
  1. Run pre-order, in-order, and post-order traversals on a binary tree.
  2. Define methods that recursively traverse binary trees.
  3. Define methods that recursively modify binary tree node data values.
Nov 10
SectionBinary Trees
Nov 11
Holiday
Nov 12
SectionMore Binary Trees
Nov 13
Binary Search Trees
BJP 17.3, 17.4
  1. Apply the binary search tree invariant to search for values and add new values.
  2. Apply the x = change(x) pattern to recursively change binary tree references.
  3. Explain why binary search trees would be preferred over binary search on arrays.

Project

Nov 16
Specifications
Nov 18
Teams
Nov 20
Users
Video

Information

Nov 23
Programming a Better Future
Video
Nov 25
Beyond Code
Video
Nov 27
Holiday

Project Sprint

Nov 30
Work
Dec 2
Work
Dec 4
Work

Beyond

Dec 7
Work
Dec 9
Career Panel
Video, Slides
Dec 11
Project Fair