Eboard 14: List ADTs
You are probably being recorded, perhaps even transcribed.
Approximate overview
- Administrivia
- Notes on setting up and running Java projects
- Questions
- Design: Lists
- Maybe some lab time
Preliminaries
- Sam has hearing aids again. He is back to mediocre hearing.
- We have finished most of the Java you need for the semester and are
moving on to more on ADTs/Data Structures and Algorithms.
- Don’t worry, we’ll still learn more Java.
- Today is a (planned) talk day.
- I’ve updated the schedule for the change in MP4. Note that you need one
fewer E for A/B/C.
Upcoming work
- Thursday, 2024-02-23, 11pm, Reading responses
- Friday, 2024-02-23, 1pm: Submit Monday’s Lab
- Friday, 2024-02-23, 11pm, Submit the first set of LAs.
- Sorry, no Gradescope links
- Wednesday, 2024-02-28, 11pm, MP4
Tokens
Academic/Scholarly
- Thursday, 2024-02-22, 11:00-noon, JRC 101.
Scholars’ Convocation: Luis Fabiano De Assis on Human Trafficking.
- Thursday, 2024-02-22, 4:00-5:00pm, Science 2022
CSC Major Declaration Session
- Tuesday, 2024-02-27, noon–1:00pm, Some PDR.
_CS Table: ???.
- Tuesday, 2024-02-27, 8:00–9:00pm, Science 3821.
CSC-207 Mentor Session.
Cultural
- Friday, 2024-02-23, 4:00–5:00pm, HSSC N1170 (Global Living Room).
Middle of Everywhere.
- Friday, 2024-02-23, 7:00–9:00pm, Sebring-Lewis.
Squatters on Red Earth.
Peer
Wellness
- Tuesday, 2024-02-27, noon-1pm, BRAC P103.
HIIT and Strength Fitness Class.
- Tuesday, 2024-02-27, 12:15–12:50, Bucksbaum 131.
Yoga in the Museum. (I think)
- Tuesday, 2024-02-27, 4pm, BRAC P103 (Multipurpose Dance Studio):
Yoga.
Misc
Other good things to do (no tokens)
Setting up Java projects for VSCode
Broadly: You have to be much more careful with directories than you’ve
been in the past.
- Please don’t put one project within another project.
- Projects generally have
src
directory.
- You should open the project from the folder that includes the
src
directory.
New projects
Please do “New Java Project”, select folder, choose name.
When you are using packages, make sure that the package name matches
the folder its in within the src directory.
Existing projects
Questions
Administrative
Please write the self checks tonight!
I’ll do my best. I’ll Teams Announce in the Q&A channel when I do.
MP4
Everything looks broken
Sam is working on it.
What should we submit?
Just your Java code from the structures package. You need not submit
the tests.
Gradescope says you can just submit your GitHub link.
How do we get things from the upstream repo?
I need to check the docs. Ask on Teams. Then ask again.
Set is supposed to throw an exception; the test cases aren’t ready for
that. Can you please fix that?
See “Everything looks broken” above. We need to fix the test cases
to say that they can throw an exception (I think).
Should we fork the testing repo?
Probably not. (It’s good practice, but I wanted you to experience the
horrific joy of multiple people committing to the same repo.)
LAs
If Sam started a project and we added stuff, can we use that?
Certainly.
Do I really have to paste code?
Yes. Whatever you think I might need to read.
Other topics
The design of ADTs, revisited
- Yup, it’s time for PUMishment
- You all remember what it means, right?
- Why use PUM?
- It’s a good way to think about the design of many things, but
particularly abstract data types
- ADTs: Ways to collect information, specified at a high level.
Lists, version 1: Scheme lists
Philosophy
What’s the underlying (overarching) philosophy of Scheme lists?
- A way to store a bunch of values.
- That is easy to recurse over to process all the values.
- That are immutable!
- Getting “all but the first” does not change the list
- Adding to the front of the list builds a new list (and does not
change the old list).
- The only place we can add elements is the front.
Uses
- To force people to use recursion.
- Represent a piece of music as a sequence of sounds.
- Represent an image as a sequence of pixels/colors.
- Represent a structure that maps strings to (association list)
Key methods
These are the ones we couldn’t write ourselves.
(car lst)
- Get the first element in the list.
(cdr lst)
- Get all but the first element in the list.
(cons val lst)
- Add something to the front of a list
(short for “construct”)
null
- Build the empty list. (We need a starting place.)
null?
- Determine if we have an empty list.
Do we really need null?
. Can we just use (eq? lst null)
.
If we don’t know the implementation, or want to support implementations,
we might want both.
Other methods
These are ones we could write ourselves, but would prefer to have a
standard implementation.
(length lst)
- Determine how many values are in the list.
(define length
(lambda (lst)
(if (null? lst)
0
(+ 1 (length (cdr lst))))))
Layout
Implementation
Analysis
Lists, version 2: CSC-161 lists
Philosophy
What’s the underlying (overarching) philosophy of the lists you built
in 161? Don’t think about the implementation. Think about how they are
organizing information.
- Something to store a bunch of values
- Mutable
- We can add values.
- We can remove values.
- The values are stored in a “consecutive” (linear) structure. Each
one except the first has a predecessor; each one except the last has
a successor.
- Users might be able to control placement (e.g., by only adding to the
front or adding to the end); pehraps adding in the middle, perhaps
removing from the middle.
Uses
- Represent an image as a list of lists of pixels (or something like that).
- Paranoia (uses cyclic list)
- Store tickets (uses things that look somewhat like queues)
Key methods
You need these; unless they are provided by the implementer, you probably
can’t get full use out of lists.
List create()
- in Java, it’s the constructor List<T>()
.
void addToFront(T val) throw NoDamnNullsException
boolean contains(T val) throws NoDamnNullException
- In Scheme, we could build this with the five basic things.
- In the lists we design, do we need this as a core operation?
int size()
- returns how many values are in the list.
boolean removeFirst(T val) throws NoDamnNullsException
- removes the
first instance of a value. Returns true if it the value was in the list;
returns false if it was not.
- Sam thinks that
remove
is ambiguous. Why?
(remove 3 '(1 2 3 4 3 2 1))
->
- Is it “remove one” or “remove all”.
int removeAll(T val) throws NoDamnNullsException
- removes all copies
Returns how many values we removed.
- Our decisions end up being based, a bit, on our use cases. If we have
too many use cases, we end up with too many procedures.
- We could have a notion of a current element.
- advance
- retreat
- remove
- addBefore
- addAfter
- You will read a paper called “lists with current considered harmful”
Other methods
You’d like these, but could probably implement them with the key methods.
Layout
Implementation
- Linked structures are presumably more memory effective than array-based
structures.
Analysis
- Reverse in place is O(n) if done right.
Lists, version 3: Sorted list
Philosophy
- A collection of values
- Stored in “sorted order”; each value precedes all larger values.
Lists, version 4: Cyclic lists
Philosophy
Like a list, except that there are no designated first/last elements,
so that every element has a successor and predecessor (and those are
inverse relations).
Lists, version 5: Iterable lists
Philosophy
Uses
Key methods