Welcome to CSE 143; ArrayList
Table of contents
- Course context
- Class values
- How learning works
- Learning online
- Academic honesty
- Parting thought
Welcome to CSE 143!
While CSE 142 focused on control issues, CSE 143 focuses on data issues.
- CSE 142
- Control: loops, if/else, methods, parameters, returns.
- I/O: scanners, user input, files.
- Data: primitive types (
double, etc.), arrays, classes.
We’ll start by reviewing arrays and classes from CSE 142 before moving on to the CSE 143 curriculum.
- CSE 143
- Control: recursion.
- Data structures: array lists, linked lists, binary trees.
- Java collections: lists, sets, maps.
By the end of the course, students should be able to:
- Select appropriate abstract data types for use in a given application.
- Design and modify data structures capable of insertion, deletion, search, and related operations.
- Trace through and predict the behavior of algorithms (including code) designed to implement data structure operations.
- Identify and remedy flaws in a data structure implementation that may cause its behavior to differ from the intended design.
CSE 143 focuses on algorithm design through programming. However, this approach may not be best for every student. CSE offers a number of complementary courses that provide alternative views on computation.
In CSE 143:
- Algorithms are more important than data. (Compare to CSE 163.)
- Technical problems are more important than creative problems. (Compare to CSE 154.)
- Programming solutions are more important than the problems they solve. (Compare to CSE 180.)
While this course is designed with certain learning objectives in mind, the class (and your experience in the course) will be shaped by the values that we collectively define. In many classes, these values are unwritten. In CSE 143, we want to define a starting point for our class values.
- We believe that learning is about caring.
- “Courses” contain material for students to learn. But our class is less about the “course” and more about all of us: the people sharing and engaging in this learning experience.
- We believe that learning is about community.
- Community, however, is complicated. Intentions don’t always match outcomes. This class is defined by all of us, so we have a responsibility to be our best selves to everyone.
- We believe that learning is about improving ourselves and the world around us.
- Learning is a process of self-discovery and change. All of us will face setbacks along the way. This class is about improving ourselves and the world around us in spite of challenges.
Learning is a process that requires deliberate practice. There are four components to deliberate practice.
- Sustained motivation.
- Tasks that build on prior knowledge.
- Immediate, personalized feedback on tasks.
- Repetition of all of the above.
Each week in the course will introduce 2 or 3 lessons. Each lesson is designed around deliberate practice. You can expect each week in the course to roughly follow this schedule (time distribution in parentheses).
- Before-class introduction (3 hours)
- Prepare your brain to maximize in-class learning by completing the lesson introduction before class. Optionally, watch the lecture video for additional context.
- Lecture meetings (3 hours)
- Engage with your neighbors and the class on the ideas. Clarify questions from the lesson introduction. Seek help and seek to help others. Go beyond getting the correct answer.
- Quiz section meetings (2 hours)
- Check your understanding applying the ideas in more complex situations. Master the lesson by working with TAs and peers.
All lessons will be completed in ed, our digital learning platform. Lecture videos and lesson content are posted on the course website, but make sure to complete the lesson in ed to receive credit. The course website has a powerful search bar to help you find and review lesson content.
A larger take-home assessment will be released at the end of each week. Assessments are submitted through Grade-It! and reviewed by your quiz section TA.
- Take-home assessment (7 hours)
- Apply all of the ideas learned during the week into one big program. In addition to solving the problem (external correctness), assessments will also emphasize programming style (internal correctness).
To prepare for the work we will do in lecture meetings, instead of reading quizzes, each week you will create an external brain to help guide you to the most important information in each lesson. Each week’s external brain will be different, but they will most often involve highlighting details, synthesizing passages, and coming up with general steps for solving common programming problems.
External brains will be submitted through Gradescope. Submit a PDF document either typed or legibly handwritten. The goal of creating an external brain is to organize information in a way that is the most helpful for your learning, so pick the format that works best for you. There’s no such thing as one right way to make an external brain.
Stop and think: How does creating an external brain help us learn?
Each lesson contains a mix of reading, quiz questions, and coding challenges. Each of these are important opportunities for learning to occur. Make the most of your learning opportunity by reflecting critically on the following meta-questions as you work through the lesson.
- Why are we learning this?
- How does this new concept fit in with everything we know so far?
- Describe this concept in your own words.
- Summarize the code in terms of its purpose (not line-by-line).
- Give a general template or list of steps for solving programming problems of this type.
In addition, there will be stop and think questions like this one embedded within readings. These are good questions to ask and answer in your own words. Collaborate with other students to improve your external brain during each lesson.
We’ve taken special care to design the course such that all of the work can be done on your own time. However, personalized feedback is a key component of deliberate practice, so we’ll still hold online class sessions using UW Zoom Video Conferencing.
Online classes share the same norms as in-person classes. Participate from a quiet space where you can listen and speak. If you participate from a more public space, be sure you won’t be disturbed by others while there. When talking to others, participate with your camera (if you have one) turned on using horizontal (not vertical) video.
The university has a page on Tips for Success at the UW. Here are a few highlights that will be particularly important for online learning.
- Maintain a regular schedule
- Use a weekly planner or calendar to maintain a regular schedule. Set alarms and reminders before class meeting times. Build in routines such as getting out of bed and dressing for the day (even if you’re not going outside).
- Take care of your body, mind, and soul
- Exercise regularly, sleep 6–8 hours every night, and eat well. Studying online can be isolating, so keep up with friends and family as much as possible. Take advantage of opportunities to study with other students using video chat if possible.
- Do not work on your bed
- Humans make spatial associations, so it’s especially beneficial to set up a separate space that is dedicated only to study and work. Get oxygen flowing by maintaining a natural posture and incorporating movement such as walking.
Add to your external brain things that you want to do to improve your learning this quarter, as well as areas where the course staff can help.
Learning cooperatively is different from sharing answers.
You are encouraged to discuss the lessons with other students, as long as you write your own code and submit your own work. Finding a study group is a great idea. The purpose of each lesson is for you to learn the course material, not to prove that you already know it. Therefore, you can expect to receive substantial assistance from the course staff.
Collaboration is not allowed on take-home assessments. You may discuss general ideas of how to approach an assessment, but never specific details about the code to write. Any help you receive from or provide to classmates should be limited and should never involve details of how to code a solution. It should also not be in front of a computer.
- Discuss examples from lessons with others. Each lesson is designed to prepare students for assessments.
- Talk to a TA to learn how to solve specific bugs and improve your understanding of the problem.
- Post questions about problem specifications to the course forum.
- Looking at someone else’s take-home assessment solution in any form for any reason at any time, ever.
- Working in lock-step with others. Your workflow should not involve giving or receiving a walkthrough of a take-home assessment.
- Posting solution code to any assessment in a public place. This applies even after the course is over.
Both parties involved in a cheating case are equally culpable. That is, helping someone else cheat is just as bad as reading someone else’s solution. There are many resources for helping students learn in this course. The right thing to do in this situation is to point them to resources such as their TA. The course staff are here to help you succeed. Contact us in person, over email, or via the course forum.
If you’re not sure if you’re following the policy, ask. If you are retaking the course, you may resubmit a previous solution unless that program was involved in an academic misconduct case. If misconduct was found, you must write a new version of that program.
Grades and penalties aren’t the purpose of this course. We really just want to help you learn as much as you can during this quarter. The entire staff is very excited to be teaching CSE 143 this quarter and we’re looking forward to meeting such a large and enthusiastic group of students. We want all of you to be successful here. Welcome to CSE 143!
A collection is an object that stores data, also known as a data structure. Elements refer to the objects stored in a collection. In this course, we’ll study a variety of common collections that serve as the building blocks of almost any program that deals with data.
All Java collections are in the
java.util package. In order to use Java collections, Java programs include the following line at the top before the class declaration.
The first collection type that we will study is the
Let’s create an empty
ArrayList that can store string data.
ArrayList<String> list = new ArrayList<String>();
jGRASP will visualize the
list as a blank rectangle, representing an empty list.
We can add strings to the end of the
list by calling
list.add with the string element.
list.add("According"); list.add("to"); list.add("some"); list.add("known"); list.add("laws"); list.add("of"); list.add("aviation");
There’s a problem with this quote. It should really read, “According to all known laws of aviation” (2007’s Bee Movie). We can fix this with two statements.
// Remove the element "some" at index 2. list.remove(2);
// Insert the element "all" at index 2. list.add(2, "all");
Note that both removing and adding an element at a particular index shifts all of the elements on and after the index position over by 1 position.
So far, we’ve been studying
ArrayList as a client: someone who uses the list, but isn’t concerned about the details of how the data is stored or how elements are shifted around when removing or adding an element at a particular index. However, in this course, we want to learn both how to use data structures (client) and how to build data structures (implementer).
jGRASP has a handy viewer mode called “Presentation - Structure Identifier”. This way, we can see exactly how the
ArrayList actually works under the hood.
Our list maintains three variables:
int modCount, and an array of strings. It turns out that the array of strings actually has space for 10 elements, not 7. When we first created the empty
ArrayList, it started with a capacity of 10 elements. So when we called
list.add earlier, what really happened was that each element was filled into an empty space in the array.
Why is it necessary to keep track of a separate integer for the size?
size is important to maintaining the client’s view of the list. The client should only see the 7 strings and not the empty spaces after index 6. As the implementer, we’re trying to maintain the illusion of a perfectly-sized list by showing only the elements that the client actually included in the list.