Abstract Data Type (ADT)

Stack (abstract data type)

Queue (abstract data type)

Map (higher-order function)

Algorithmic Analysis

Case Analysis

Algorithm Analysis

Asymptotic Analysis

Recursive Algorithm Analysis

Binary Search Tree (BST)

Hashing

AVL Trees

Tree (data structure)

Graphs

Breadth-first search (BFS)

Depth-first search (DFS)

Topological sorting

Graph traversal

Minimum Spanning Tree (MST)

Disjoint Sets

Dynamic programming

Graph Modelling

Sorting algorithm

P/NP

Computer memory

Shortest paths

Heap (data structure)

CSE 373 Data Structures and Algorithms University of Washington Summer 2022 This course focuses on common data structures and algorithms. It integrates theoretical understanding with practical exercises, preparing students for software-related roles and industry technical interviews. Programming projects, unit testing, and source control techniques are emphasized.  In this course, you will gain a strong theoretical and conceptual understanding of common data structures and algorithms, as well as how to apply them within larger programming projects.

Specific topics we will cover include:

- **Data structures and ADTs**: lists, stacks, queues, sets, dictionaries, linked lists, arrays, trees, balanced trees, AVL trees, hash tables, priority queues, binary heaps, and disjoint sets.
- **Graphs and graph algorithms**: graph search, shortest path, and minimum spanning trees.
- **Algorithm analysis**: asymptotic analysis, and P and NP complexity classes.
- **Sorting** and divide-and-conquer.

This course is designed to have a practical component to help you gain basic familiarity with techniques used within industry. In particular, you’ll be asked to:

- Work on **programming projects** and integrate your work in an existing codebase.
- Learn how to use an **industrial-strength IDE**.
- Learn techniques for **checking correctness**: writing unit tests with JUnit, designing and checking invariants, etc.
- Learn how to collaborate on a single code base using **source control** repositories.

Finally, this course emphasizes the importance of making and justifying design decisions. Taken together, all of the above skills are chosen to set you up for success in a software-related role. In fact, this course is typically regarded as useful preparation for industry and technical interviews. [CSE 143](https://courses.cs.washington.edu/courses/cse143/), or similar Java programming experience. 

CSE 373 Data Structures and Algorithms

Data Structures and Algorithms

Reasoning

Data Abstraction

Representation Invariants (RIs)

Exception handling

Generics

HTTP Servers

JSON

Loops

Software testing

Equality

Module Design & Style

User interface

React

Web Clients

Debugging

Specifications

Abstraction Functions (AFs)

Identity (object-oriented programming)

Assertion (software development)

Subtypes

Event-Driven Programming

TypeScript

Software design pattern

JavaScript

CSE 331 Software Design & Implementation University of Washington Spring 2022 This course aims to improve students' software development skills, focusing on building correct, scalable, and easy-to-understand software. It relies on a solid understanding of Java and the concepts covered in CSE 143. Students will learn about software design principles, modern programming languages, and software tools. It covers software testing, type systems, design patterns, and more. The aim of this course is to help students write programs of higher quality and increased complexity. This requires creating software that is correct, easy to change, easy to understand, and easy to scale. The course covers principled approaches to achieving each of these. The aim of this course is to help students write programs of higher quality and increased complexity. This requires creating software that is (1) correct, (2) easy to change, (3) easy to understand, and (4) easy to scale. We will study principled approaches to achieving these four goals.

After completing this course successfully students should be able to:

- Successfully build medium-scale software projects in principled ways
- Understand the role of specifications and abstractions and how to verify that an implementation is correct, including effective testing and verification strategies and the use of formal reasoning
- Analyze a software development problem and be able to design effective program structures to solve it, including appropriate modularity, separation of abstraction and implementation concerns, use of standard design patterns to solve recurring design problems, and use of standard libraries
- Use modern programming languages effectively, including understanding type systems, objects and classes, modularity, notions of identity and equality, and proper use of exceptions and assertions
- Use and learn new contemporary software tools, including integrated development environments, test frameworks, debuggers, version control, and documentation processing tools

In this class, we will use Java and associated tools like IntelliJ, JUnit, JavaDoc, and git, but the goal is to understand the underlying ideas and concepts that are generally applicable to software construction. The only formal prerequisite is CSE 143. We will very much rely on a thorough understanding of the concepts from CSE 143 as well as Java programming skills. We will go much further and you will be challenged to approach software development much differently than you have in CSE 143 or other courses. ### Texts

The required text for the course is the following:

- Effective Java by Joshua Bloch, 3rd ed., Addison-Wesley, 2018.

Contains a great deal of distilled wisdom about Java best practices, technical details, and style issues.

There will be assigned readings from this book during the quarter, and there will be questions on the exams about those readings.

Besides the required text, the following books may be helpful to you:

- The Pragmatic Programmer by Andrew Hunt and David Thomas, 20th anniversary (2nd) edition, Addison-Wesley, 2020.

Contains a great deal of distilled wisdom about software construction and the craft of programming, including many things that those who read the book later in their careers wish they had learned early on.

- Program Development in Java by Barbara Liskov and John Guttag, 1st ed, Addison Wesley, 2000.

The content of this well-written book closely mirrors much of the content of the course. The only downside is that it was written 17 years ago, so it is out-of-date with regard to some of key parts of the Java language and libraries. Nonetheless, it is a good place to look for another presentation of the material covered in class, if you can ignore those parts.

- Core Java Vol. I - Fundamentals by Cay Horstmann, 10th ed, Prentice-Hall, 2016; 11th ed, 2018.

This is a good general reference for the Java language and basic libraries. While technical documentation for these things is available on the web, the discussions in a book like this one are usually easier to follow and typically include advice not found in the formal documentation. Either recent edition will cover what we need for CSE 331.

CSE 331 Software Design & Implementation

Software Engineering

Java (programming language)

Class (computer programming)

References

Recursion (computer science)

List (abstract data type)

SLLists

Nested Classes

Array (data structure)

Array Resizing

Inheritance (object-oriented programming)

Extends

Higher-order function (HOF)

Object Methods

Set (abstract data type)

Red Black Trees

Tree traversal

Multi-Dimensional Data

Prefix Operations and Tries

Reductions and Decomposition

Quick Sort

Algorithmic Bounds

Data structure

Scope

Linked list

Kolmogorov complexity

Sentinel Nodes

DLLists

ALists

SLists

Implements

Casting

Subtype Polymorphism

Iterators

Asymptotics

B-tree

Priority queue (PQ)

Range Searching

Radix Sorts

Compression

P=NP

Static

CS 61B: Data Structures UC Berkeley Fall 2022 CS 61B focuses on software efficiency from design and runtime perspectives. It covers object-oriented programming with Java, teaching data structures and various programming concepts. The course promotes hands-on learning with optional assignments. The CS 61 series is an introduction to Computer Science, with particular emphasis on software and machines from a programmer’s point of view. CS 61A covered high-level approaches to problem-solving, providing you with a variety of ways to organize solutions to programming problems as compositions of functions, collections of objects, or sets of rules. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming by focusing particularly on the efficiency of writing programs (design) and running programs (runtime).  This class assumes you have taken CS 61A, CS 88, or E 7, or have equivalent background to a student who has taken one of these courses. The course is largely built upon the assumption that you have taken CS 61A. CS 88 and E7 students may find the beginning of the course to be a bit scarier, particularly when it comes to object oriented programming. We assume you are coming in with zero Java experience, but we will move through basic Java syntax very quickly.

We recommend all students to complete the [optional introductory assignment](https://fa22.datastructur.es/materials/hw/hw0/) by the beginning of the semester to get comfortable with Java and practice some of the programming skills expected by this class.

If you already have Java experience, great! We hope that you’ll help out your fellow students in discussion, lab, and on our class forum, particularly in the opening weeks when everyone is catching up on Java. **There is no required textbook for the class.**

There is an online textbook written by myself and a large team of former TAs. It can be found at https://joshhug.gitbooks.io/hug61b. If you find these notes insufficient, you might consider consulting [Paul Hilfinger’s (free) Java Reference](http://www-inst.eecs.berkeley.edu/~cs61b/fa14/book1/java.pdf) or [Head First Java, 2nd Edition by Sierra and Bates (O’Reilly, 2005)](https://www.google.com/search?q=head+first+java). These are not required for the course. The **optional** textbook for the weeks 5-14 of the course is Algorithms, 4th Edition by Wayne and Sedgewick.

The official description of the Java core language is available online in [The Java Language Specification](https://docs.oracle.com/javase/specs/jls/se17/html/index.html) (Java SE 17 Edition) by James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, Daniel Smith, and Gavin Bierman. It’s extremely thorough and precise, at the expense of being quite dense and technical. You will find the official [Java 17 documentation](ttps://docs.oracle.com/en/java/javase/17/docs/api/index.html) to be useful as well

CS 61B: Data Structures

Abstraction (computer science)

For Loop

Environment Diagrams

Dictionaries

Object-Oriented Programming (OOP)

Mutable Data

Generators

Databases

Function (computer programming)

Lambda

Tree Recursion

Efficiency

Programming Paradigms

CS 88: Computational Structures in Data Science UC Berkeley Fall 2022 This course provides an introduction to computer science with an emphasis on functional programming, data abstraction, object-oriented programming, and program complexity. The course teaches foundational programming concepts primarily in Python. CS 88 is a "connector" for Data 8 that is designed for students who would like a more complete introduction to Computer Science. We will cover a variety of topics such as functional programming, data abstraction, object-oriented programming, and program complexity. This course will be taught primarily in Python. However, we are interested in teaching you foundational programming ideas, not just how to use one particular programming language. Once you have learned the essence of programming and the concepts that appear in various forms in programming languages, you will be able to pick up other languages and other programming concepts rapidly.

The material for this course has significant overlap with CS 61A. We do not cover the interpretation section of CS61A. If you are certain that you want to major or minor in Computer Science, CS 61A is the right introductory course. You can take CS 61A for credit after having taken CS 88. However, you cannot take CS 88 for credit after having taken CS 61A. Data 8 and CS 88 together satisfy the knowledge prerequisite for CS 61B.  It is recommended, but not required, that you are currently enrolled in or have taken Data 8. There is no formal programming-related prerequisite for CS 88. You do not need to be familiar with any particular programming language. The online textbook for the course is [Composing Programs](http://composingprograms.com/), which was created specifically for CS61A but is also the best basis for this course. Readings for each lecture appear in the course schedule. We will be jumping around a little due to the data-centric orientation of the course. You should complete the readings before attending lecture.

In addition, the course website and Piazza will contain additional links to guides, handouts, and practice materials available for the course.

CS 88: Computational Structures in Data Science

Computer Programming

Interface

Encapsulation

`ArrayIntList`

pre/post conditions

Reference Semantics

List Nodes

`LinkedIntList`

Recursive Tracing

Grammars

Binary Search

Recursive Backtracking

Binary tree

Comparable

Priority Queues

Huffman

Resizing

Abstract Classes

Computational complexity

CSE 143 Computer Programming II University of Washington Summer 2022 This course is a continuation of CSE 142, focusing on manipulating data, implementing data structures, and learning about algorithms in Java. It delves into abstract data types, recursion, inheritance, and more.  This course is a continuation of CSE 142. While CSE 142 focused on topics of program control (loops, conditionals, methods, parameter passing, etc.), CSE 143 focuses on topics ofb manipulating data. Topics include: abstract data types (ADTs), lists, stacks, queues, linked lists, binary trees, recursion, interfaces, inheritance, and encapsulation. Students will also learn about the notion of complexity and how to evaluate performance trade-offs of classic algorithms (such as sorting and searching) and classic data structures (such as lists, sets, and maps). The course will include a mixture of implementing data structures and using components from the Java Collections Framework.  ## Textbook

Our optional textbook for CSE 143 this quarter will be the following:

Reges/Stepp. Building Java Programs: A Back to Basics Approach, 5th edition. ISBN 978-0135471944

- [Building Java Programs: A Back to Basics Approach (authors' web site)](http://www.buildingjavaprograms.com/)

This book was written specifically for this course and makes a valuable supplement to the lecture presentations.

## Code Files

The textbook includes many sample programs. You can access a full set of [code files](http://www.buildingjavaprograms.com/code_files/) that is organized chapter by chapter. This will allow you to download any of the programs and run them on your own computer.

## Video Notes

New copies of the textbook come with an access code to watch "Video Notes." These videos supplement the lecture and book material by walking through more examples in detail. You can access the video notes at the Pearson [VideoNotes](http://www.pearsonhighered.com/regesstepp/) web site.

CSE 143 Computer Programming II