Lecture 1: Welcome!

CSE 373: Data Structures and

Algorithms

CSE 373 19 SU - ROBBIE WEBER 1

Agenda
-Introductions
-Syllabus
-Dust off cob webs
-Meet the ADT

CSE 373 19 SU - ROBBIE WEBER 2

Course Staff
Instructor: Ph.D. student in CSE
Robbie Weber Research in algorithm design
[email protected]
Office: CSE 330 2nd time as instructor
Office Hours:
M,W 2:20-3:30 and by
TAed 15 times
appointment (3 times for this course)

Amazing Teaching Assistants:

Brian Chan Oscar Sprumont Blarry Wang
Zach Chun Matthew Taing Xin Yang
Kevin Son Howard Xiao Velocity Yu

CSE 373 19 SU - ROBBIE WEBER 3

Class Style
Please come to lecture (yes, there will be panoptos)
- Warm Ups -> Extra Credit
- Discuss with other students
- Ask questions! Point out mistakes!

Sections
- TAs = heroes
- Practice problems
- Different Explanations
- Sections start this week

CSE 373 19 SU - ROBBIE WEBER 4

Class Style
Summer Quarter is weird.
We have fewer class meetings
But they’re all 60 minutes, not 50 minutes.

We’ve rearranged (and cut) things to account for the schedule

But things are more cramped.

Please start on assignments early and ask for help early

TAs are amazing – we can help A LOT 3 days before an assignment is due.
There’s only so much we can do 3 hours before it’s due.

CSE 373 SU 19 – ROBBIE WEBER 5

Course Administration
Course Page cs.washington.edu/373
- Course content posted here
- Pay attention for updates!

Canvas
- Grades will be posted to Canvas at end of quarter

Office Hours
- Will be posted on Course Page
- Will start next week (at the latest)

Piazza
- If you were signed up for the course before this morning, you were added already.
- If not, you can find an add code on Canvas (or ask a member of staff)
- Announcements made via Piazza
- Great place to discuss questions with other students
- Will be monitored by course staff
- No posting of project code!

Textbook
- Optional
- Data Structures and Algorithm Analysis in Java by Mark Allen Weiss

CSE 373 19 SU - ROBBIE WEBER 6

Grade Break Down
Homework (55%)
- Programming Projects (35%)
- 1 Individual Project (review of 14X)
- 4 Partner Projects
- Partners GREATLY encouraged
- Graded automatically
- Regrades available on some parts
- Some projects are two connected one-week assignments; others are just one week.
- Written Assignments (20%)
- Written assignments graded by TAs

Exams (45%)
- Midterm Exam – Friday July 26th in class (15%)
- Final Exam (30%)
- Two one-hour parts:
- In place of final section Thursday August 22
- In place of final lecture Friday August 23

If you have a conflict with any of those dates, email Robbie as soon as possible.

CSE 373 19 SU - ROBBIE WEBER 7

Syllabus
Homework Policies Academic Integrity
- 4 late days - Discussing concepts and high-level ideas for problems is
strongly encouraged, but submitted work must be your
- Both partners must use one for pair projects own.
- When you run out you will forfeit 20% each 24 hour period - Read policy on the webpage.
an assignment is late
- No posting code on discussion board or ANYWHERE
- No assignment will be accepted more than 2 days late online
- We do run MOSS
Regrades - No directly sharing code with one another (except for
- For assignments with two parts: automatically get back partners)
half missed points for part 1 when you turn in part 2
- If you think we made a mistake grading (or the autograder
did something unreasonable):
Extra Credit
- Available for attending lecture, by filling out
- Fill out a regrade request on gradescope for written work PollEverywhere questions
- Fill out the google form for programming projects - Based on completion not correctness.
- Worth up to 0.05 GPA bump

CSE 373 19 SU - ROBBIE WEBER 8

 Questions?
Clarification on syllabus, General complaining/moaning

CSE 373 19 SU - ROBBIE WEBER 9

What is this class about?
DATA STRUCTURES ALGORITHMS

How do we organize our data most Some classic, fundamental algorithms

effectively? How they work
And how do we justify those decisions How do we get them use them to
Actually implement data structures solve problems
Not just use them

TOOLS TO MAKE AND ANALYZE DS&ALGS

Basic Software Engineering Practices Basic Theoretical Computer Science

Debugging Modelling Code/Big-O
Testing Analyzing Recurrences
Version Control

CSE 373 19 SU - ROBBIE WEBER 10

Data Structures and Algorithms
What are they anyway?

CSE 373 19 SU - ROBBIE WEBER 11

Basic Definitions
Data Structure
- A way of organizing, storing, accessing, and updating a set of data
- Examples from CSE 14X: arrays, linked lists, binary search trees

Algorithm
- A series of precise instructions guaranteed to produce a certain answer
- Examples from CSE 14X: binary search, merge sort

CSE 373 19 SU - ROBBIE WEBER 12

Abstract Data Types (ADT)
Abstract Data Types
- A definition for expected operations and behavior

Start with the operations you want to do then define how those operations will play out on
whatever data is being stored

Review: List - a collection storing an ordered sequence of elements

- each element is accessible by a 0-based index

- a list has a size (number of elements that have been added)
- elements can be added to the front, back, or elsewhere
- in Java, a list can be represented as an ArrayList object

CSE 143 WI 18 – STUART REGES 13

Review: Interfaces
interface: A list of methods that a class promises to Example
implement. // Describes features common to
- Interfaces give you an is-a relationship without code sharing. all // shapes.
- A Rectangle object can be treated as a Shape but inherits no code. public interface Shape {
public double area();
- Analogous to non-programming idea of roles or certifications: public double perimeter();
- "I'm certified as a CPA accountant. }
This assures you I know how to do taxes, audits, and consulting."
- "I'm 'certified' as a Shape, because I implement the Shape interface.
This assures you I know how to compute my area and perimeter."

public interface name {

public type name(type name, ..., type name);
public type name(type name, ..., type name);
...
public type name(type name, ..., type name);
}

CSE 143 SP 17 – ZORAH FUNG 14

Review: Java Collections
Java provides some implementations of ADTs for you!
You used:
Lists List<Integer> a = new ArrayList<Integer>();
Stacks Stack<Character> c = new Stack<Character>();
Queues Queue<String> b = new LinkedList<String>();
Maps Map<String, String> d = new TreeMap<String, String>();

CSE 373 19 SU - ROBBIE WEBER 15

Full Definitions
Abstract Data Type (ADT)
- A definition for expected operations and behavior
- A mathematical description of a collection with a set of supported operations and how they
should behave when called upon
- Describes what a collection does, not how it does it
- Can be expressed as an interface
- Examples: List, Map, Set
Data Structure
- A way of organizing and storing related data points
- An object that implements the functionality of a specified ADT
- Describes exactly how the collection will perform the required operations
- Examples: LinkedIntList, ArrayIntList

CSE 373 19 SU - ROBBIE WEBER 16

ADTs we’ll discuss this quarter
-List
-Set
-Map
-Stack
-Queue
-Priority Queue
-Graph
-Disjoint Set

CSE 373 19 SU - ROBBIE WEBER 17

Case Study: The List ADT
list: stores an ordered sequence of information.
- Each item is accessible by an index.
- Lists have a variable size as items can be added and removed

List ADT supported operations:

- get(index): returns the item at the given index
state
Set of ordered items - set(value, index): sets the item at the given index to the given value
Count of items
behavior - append(value): adds the given item to the end of the list
get(index) return item at index - insert(value, index): insert the given item at the given index maintaining order
set(item, index) replace item at index
append(item) add item to end of list - delete(index): removes the item at the given index maintaining order
insert(item, index) add item at index
delete(index) delete item at index - size(): returns the number of elements in the list
size() count of items

CSE 373 19 SU - ROBBIE WEBER 18

Case Study: List Implementations
ArrayList LinkedList
uses an Array as underlying storage uses nodes as underlying storage
List ADT
ArrayList<E> LinkedList<E>
state
Set of ordered items state state
Count of items data[] Node front
size size
behavior
get(index) return item at index behavior behavior
set(item, index) replace item at index get return data[index] get loop until index,
append(item) add item to end of list set data[index] = value return node’s value
insert(item, index) add item at index append data[size] = set loop until index,
delete(index) delete item at index value, if out of space update node’s value
size() count of items grow data append create new node,
insert shift values to update next of last node
make hole at index, insert create new node,
data[index] = value, if loop until index, update
out of space grow data next fields
delete shift following delete loop until index,
values forward skip node
size return size size return size

0 1 2 3 4
88.6 26.1 94.4
88.6 26.1 94.4 0 0

list free space

CSE 373 19 SU - ROBBIE WEBER 19
Implementing ArrayList

insert(element, index) with shifting

ArrayList<E> 0 1 2 3
state insert(10, 0) 3
10 4 5
data[]
size
behavior numberOfItems = 4
3
get return data[index]
set data[index] = value
append data[size] =
value, if out of space
grow data
insert shift values to delete(index) with shifting
make hole at index,
data[index] = value, if 0 1 2 3
out of space grow data
delete shift following delete(0) 10 3 4 5
values forward
size return numberOfItems
numberOfItems = 4
3
Take 2 Minutes
Should we overwrite index 3 with null?
CSE 373 19 SU - ROBBIE WEBER 20
Implementing ArrayList
append(element) with growth
ArrayList<E> 0 1 2 3
state append(2) 10 3 4 5
data[]
size
behavior
get return data[index] numberOfItems = 5
4
set data[index] = value
append data[size] =
value, if out of space
grow data
insert shift values to 0 1 2 3 4 5 6 7
make hole at index,
data[index] = value, if 2
out of space grow data
delete shift following
values forward
size return size

CSE 373 19 SU - ROBBIE WEBER 21

Design Decisions
For every ADT there are lots of different ways to implement them
Based on your situation you should consider:
- Memory vs Speed
- Generic/Reusability vs Specific/Specialized
- One Function vs Another
- Robustness vs Performance

This class is all about implementing ADTs based on making the right design tradeoffs!
> A common topic in interview questions

CSE 373 19 SU - ROBBIE WEBER 22

 Case Study: List Implementations
ArrayList LinkedList
uses an Array as underlying storage uses nodes as underlying storage
List ADT
ArrayList<E> LinkedList<E>
state
Set of ordered items state state
Count of items data[] Node front
size size
behavior
get(index) return item at index behavior behavior
set(item, index) replace item at index get return data[index] get loop until index,
append(item) add item to end of list set data[index] = value return node’s value
insert(item, index) add item at index append data[size] = set loop until index,
delete(index) delete item at index value, if out of space update node’s value
size() count of items grow data append create new node,
insert shift values to update next of last node
make hole at index, insert create new node,
data[index] = value, if loop until index, update
out of space grow data
Take 2 Minutes delete shift following
next fields
delete loop until index,
values forward
What method will be much faster size return size
skip node
size return size
for LinkedList than for ArrayList?
0 1 2 3 4
88.6 26.1 94.4
88.6 26.1 94.4 0 0

list free space

CSE 373 19 SU - ROBBIE WEBER 23
Design Decisions
Take 2 Minutes

Dub Street Burgers is implementing a new system for ticket (i.e. food order) management.
When a new ticket comes in, it is placed at the end of the set of tickets.
Food is prepared in approximately the same order it was requested, but sometimes tickets are
fulfilled out of order.

Let’s represent tickets as a list. Which of our ADT implementations should we use?
Why?

CSE 373 SU 19 - ROBBIE WEBER 24

Design Decisions
Let’s represent tickets as a list. Which of our ADT implementations should we use?
Why?

ArrayList
Creating a new ticket is very fast (as long as we don’t resize), and I want the cooks to be able to
see all the orders right away.

LinkedList
We’ll mostly be removing from the front of the list, which is much faster for the linkedlist (no
shifting), and I want finished orders to be removed fast so they aren’t distracting.

CSE 373 SU 19 - ROBBIE WEBER 25

Design Decisions
Both ArrayList and LinkedList implementations have pros and cons.
Neither is strictly better than the other.

Some major objectives of this course:

Evaluating pros and cons
Deciding on a design
Defending that design decision

Especially when there’s more than one possible answer.

CSE 373 SU 19 - ROBBIE WEBER 26