You are probably being recorded (and transcribed) (if the technology is working correctly).
Start of class instructions
Approximate overview
I don’t know what your prior experience with tokens is. I give them for academic/scholarly events, cultural events, peer events, wellness events, and a few other things. Only those I record in the daily eboards are available. Please log them within three days.
If you’d like to suggest token events, please let me know in advance of class.
Academic/Scholarly
Cultural
Multicultural
Peer
Wellness
Misc
I historically give a “Friday PSA” (public service announcement). Students have encouraged me to continue doing so. Unfortunately, our class does not meet on Fridays, so I will pretend that we’re a state school, and give you a Thursday PSA. If you find these annoying, let your class mentor know and they’ll tell me to stop.
Why don’t the students have questions?
They are too nervous to ask questions. Sam is too intimidating.
What IDE will we be using?
Visual Studio Code from Microsoft
What compiler will we be using?
In MathLAN, we use OpenJDK 17 or so.
You can use newer versions if you’d like.
Can we run it on our personal computers?
If you trust Microsoft products.
VSCode is a PITA to configure, so it may take some work. Sam can help you with Linux and macOS, but refuses to try to figure out Windows.
Why is Sam intimidating?
Have you gotten your reading response graded yet? “Wow, this is crap.”
Large white-presenting male syndrome
Sarcastic
Makes JJ act as model for the class
What’s your least favorite color?
The dark green that I can’t distinguish from black.
How do you set up JUnit 5?
Stay tuned. We’ll talk about it when we do unit testing. (Or use Maven, and it should get installed automatically.)
Why is teams transcription working well? Isn’t it a Microsoft product?
I have no idea.
How do I get as good with the terminal as you are?
Practice. Not the 10,000 hour crap, but practice.
How do I get an A in the class?
Take notes. Do the work. Ask questions when you get stuck. Take advantage of redos. Go to mentor sessions. Don’t cheat.
What’s your favorite part of teaching at Grinnell?
Awesome students (especially those who I maintain connections with over the years).
What’s Maven?
A build tool (like Make, except specific to Java and somewhat on steroids)
Was there a reading?
Yes. It was on the schedule. I thought it was also in the email. Did you not get the email?
Could you explain the relationship between traits, mixins, and Java’s forms of polymorphism?
Perhaps after we’ve discussed Java’s forms of polymorphism.
Maybe explain the concept of Polymorphism and Inheritance, because I remember learning it from CSC 161, but have forgotten some things that I don’t remember specifically.
We’ll do those in depth in a week or two.
How should we know what strategy to choose for SAM to be efficient? It feels like we can choose anything but I don’t understand the differences until I start writing the methods.
Our goal in ADT design is not efficiency; it’s to think through how we want to use the data. What do we want to be able to do? It’s only once we look at implementations that we start thinking about costs.
How does the Layout of LIA (AAA) affect the outcome? Is there anything specific to look out for when choosing the layout for ADT?
Different layouts will lead to different costs. We should see that when we explore different implementations of stacks.
You may remember this from getting, say, the 100th element of a vector (quick) vs the 100th element of a stack (slow).
I felt sloppy answering these questions. I mostly used what I knew from C, and I had trouble envisioning how this would work in an OO environment. If you could go into more detail about these data structures are implemented in Java that would be splendid.
We haven’t done any Java or OOP yet. I wouldn’t think that you’d approach them that way. We’ll look at them as C structures or functions for the time being. We’ll return to stacks and such in an OO model in a few weeks.
How would the basic data structures we learned in 161 (stacks and queues) be implemented within Java/OOP without using pseudo-code?
We’ll cover those in a few weeks, once we’ve learned about objects (and perhaps even generics).
For the arrangement question, what were you thinking about as “other data”?
For context, that question reads “Describe a way you might arrange a stack in memory. (You might represent the stack as a linked structure or an array; what other data would you store in each case?)”
If I were storing the stack as an array in C, in addition to the array, I would also store the size of the array (I might call that the “capacity” of the stack) and the number of elements in the stack.
struct StackOfStrings {
char **elements;
int capacity;
int size;
};
Although a linked implementation of stacks might only require one pointer, a linked implementation of queues often requires two (one for the front of the queue and one for the back of the queue).
I’ve read that there are 4 principles: Abstraction, Polymorphism, Encapsulation, Inheritance. The way the reading laid it out is a bit different: Encapsulation, Inheritance, Polymorphism, Composition. Especially in the Encapsulation part, it seems a bit difficult to differentiate between that and Abstraction. Can you go deeper into these 2?
Great question! Let’s wait until we’ve played with them a bit more.
If there is time maybe an example of a minimalist design ADT?
Yup, we’ll do that for stacks today.
If possible just re-explain how ADT and data structures work together
The ADT is the what. That is, what you want to do with your data. The data structure is the how. That is, how we achieve those goals.
In reality, the border can be a bit fuzzy.
Alternately, the ADT is the
.hfile and the data structure is the.cfile. At least that holds if we’re thinking about collections of values.
How many tokens do we start with?
Three.
Is there a limit to how many tokens we can earn?
Time. Sanity.
Get started learning how to be a computer scientist / software developer.
Don’t forget to ask me when I use a TLA that you don’t understand.
ADTs: Abstract data types. In effect, a set of operations that you want to do on a collection of data. (E.g., push, pop, peek).
Data structures: How we organize those data in memory to achieve the operations.
ADTs are more abstract, data structures are more concrete.
We will use the Think-Pair-Share (TPS) process. You’ve already thought to yourself (or should have, since it was an assignment). Now it’s time to pair with another person and discuss your answers. Then we will share with each other.
ADT: Use the SAM approach for ADTs.
Note: This used to be the PUM approach. I thought SAM was easier to remember. (Philosophy Uses Methods)
We will assume that it’s a stack of strings. We will also assume that we’re implementing it in C.
Please make sure you consider parameters, return types, preconditions, potential questions the client of your stack might have, etc.
I’ll divide your answers into “core methods” (the ones we probably can’t do without) and “optional methods” (the ones we could implement with the core methods if we wanted to).
void push(struct Stack *stack, char *elt) - adds an element to the stack
char *pop(struct Stack *stack) - returns and removes the top value in
the stack. Requires that the stack is nonempty.
int is_empty(struct Stack *stack) - determines whether the stack is empty.
Returns 1 if it is and 0 otherwise.int is_full(struct Stack *stack) - determines whether it is safe to push.
Returns 0 if it is and 1 otherwise.struct Stack *new_stack(); - allocate and initialize a new stack.
Returns null if it is unable to do so.void delete(struct Stack *stack) - remove everthing from the stack
and deallocate memory associated with the stack.Why we need to know about what we’re copying.
char *str = (char *) malloc(10*sizeof(char));
strcpy(str, "hello");
struct Stack *stack = new_stack();
push(stack, str);
strcpy(str, "agh!");
printf("%s\n", pop(stack)); // This should print "hello"
Observations
Either decision is fine. But you should know what you’re doing. (Note: In Java, we won’t have to worry, because strings are immutable.)
char *peek(struct Stack *stack) - returns but does not remove the top value
in the stack. Requires that the stack is nonempty. (Could be implemented
with pop and push.)int size(struct Stack *stack) - probably can’t be implemented separately,
but may not be necessary.void clear(struct Stack *stack) - remove everything.while (! is_empty(stack))
{
pop(stack);
} // while
char *concatenate(struct Stack *stack) - build a string consisting
of everything on the stack.void for_each(struct Stack *stack, char *fun(char *str)) - do something
with each string in the stack.void remove(struct Stack *stack, char *str) - remove all copies of the
str from the stack.We’ll use the AAA approach (which used to be the LIA approach and may get renamed again).
One of the skills I hope you’ll develop in the course is the ability to design new things (most often, ADTs and data structures). Hence, in addition to labs, we’ll spend a reasonable amount of class time on design problems. You had a lot of time to think about stacks. You’ll have less time for this.
I’ll ask you to take a full minute to think to yourself before you pair and then share.
I want things that I can use like arrays, but I don’t want to have to specify their capacity in advance. They should always be big enough for how I’m using them.
I’d also prefer not to have a different syntax for arrays than for the structures I build myself.
If we’re lucky, we’ll have the time to talk through some of these.
Probably not this one.