Introduction
Table of contents
Overview
Data structures and algorithms are the foundational abstractions underlying all computer systems. Just as programming languages affect the way we compose programs, the design of abstractions affect the resulting values encoded within applications. In CSE 373, we will learn to design, analyze, and critique data structures and algorithms (and applications thereof).
- Design data structures and algorithms by implementing and maintaining invariants.
- Analyze the runtime and design values of data structures and algorithms.
- Critique the application of data structures and algorithms towards complex problems.
CSE 373 is organized around 3 motivating projects, weekly learning checkpoints, a video portfolio, and an open-ended research project.
Values
This course is more than ideas and learning objectives. We are a community of learners, defined by how we conduct ourselves, how we communicate with each other, and how we care about each other. I believe everyone can succeed and grow as a whole human being together in this course. But to realize this vision, we’ll need to work together to act compassionately and treat all others as we wish to be treated ourselves: to think first of others, their benefit, their well-being, and their learning. We are only as good as we are to each other.
In western scientific inquiry, learning and the acquisition of knowledge operates in a frame of Cartesian Dualism where learning is for individual gain. Science is expected to be value-neutral, objective, and unemotional. This framing has operated to empower certain, dominant ways of knowing and thinking about the world. But in order to engage with the critical questions that we raise in this course, we will need a framing that values a more holistic approach to learning for collective benefit. Here, I will name Inlak’esh as one particular framing arising from Mayan and Mexican American studies, but these values are shared across many different cultures and traditions across the world.1
| Inlak’esh | Cartesian Dualism |
|---|---|
| I am you and you are me | I think, therefore I am |
| Body/mind/spirit = integrated | Mind/body separation |
| Collaborative | Competitive |
| Learning for collective benefit | Learning for individual gain |
| Values multiple ways of knowing | Measures intelligence against a single norm |
The following behaviors serve as first steps towards creating a compassionate community.
- Listen with intention to understand first and forming an opinion only after you fully understand.
- Take responsibility for the intended and unintended effects of your words and actions on others.
- Mindfully respond to others’ ideas by acknowledging the unique value of each contribution.
We welcome students of all backgrounds. The computer science and computer engineering industries have significant lack of diversity. This is due to a lack of sufficient past efforts by the field toward even greater diversity, equity, and inclusion. The Allen School seeks to create a more diverse, inclusive, and equitable environment for our community and our field. You should expect and demand to be treated by your classmates and the course staff with respect. If any incident occurs that challenges this commitment to a supportive, diverse, inclusive, and equitable environment, please let the instructor know so the issue can be addressed. Should you feel uncomfortable bringing up an issue with the instructor directly, submit anonymous feedback, or contact the Office of the Ombud.
We recognize that students come from varied backgrounds and can have widely-varying circumstances affect them during their time in the course. Please do not hesitate to contact the instructors by appointment or via private discussion post. The sooner we are made aware, the more easily these situations can be resolved. Extenuating circumstances include work-school balance, familial responsibilities, religious observations, military duties, unexpected travel, or anything else beyond your control that may negatively impact your performance in the class.
It is the policy and practice of the University of Washington to create inclusive and accessible learning environments consistent with federal and state law. If you have already established accommodations with Disability Resources for Students (DRS), activate your accommodations via myDRS so we can discuss how they will be implemented in this course. If you have a temporary health condition or permanent disability that requires accommodations, contact DRS directly to set up an Access Plan.
Washington state law requires that UW develop a policy for accommodation of student absences or significant hardship due to reasons of faith or conscience, or for organized religious activities. The UW’s policy, including more information about how to request an accommodation, is available at Religious Accommodations Policy. Accommodations must be requested within the first two weeks of this course using the Religious Accommodations Request form.
Jess Cleeves. 2020. Can Learning be Fair?: Explicit Acknowledgment of Structural Oppression as a Teaching Tool. ↩
Deliberate practice
Learning computer science requires deliberate practice.
- Sustained motivation.
- Tasks that build on prior knowledge.
- Immediate, personalized feedback on tasks.
- Repetition of all of the above.
Deliberate practice is about taking on the right challenge with the right support. We’ll learn new concepts each week in the following manner.
- Prepare for learning before class by completing the pre-class preparation.
- Collaborate and learn from each others through in-class guided practice.
- At the end of the week, complete the individual checkpoint.
Every two week period in the course is organized around a group project, where you’ll work in teams to design and implement a real-world application of the technology. While these projects include a programming component, programming is not the only focus of the project. For each project, your team will submit a video analyzing and critiquing several dimensions of the technology, which will involve developing arguments using evidence and reasoning.
Learning cooperatively
Collaboration improves the effectiveness of deliberate practice. With the exception of checkpoints, we encourage you to discuss course activities with your friends and classmates as you are working on them. You will definitely learn more if you work with others than if you do not. If you are helping another student, don’t just tell them the answer; they will learn very little and run into trouble on checkpoints. Instead, guide them to the concepts and ideas that helped you make progress. Practice is most effective when it builds on what we already know; feedback is most helpful when it addresses specific areas for improvement.
In addition to collaborating with other students, the course staff are here to personalized feedback. Your teaching assistant (TA) is your mentor and guide to the course. It’s their job to help you get the most out of this course.
Teaching assistants
Amanda Park she/her
Hi there! My name is Amanda Park. I enjoy going to cute cafes with friends and watercolor drawings. I also like cute cartoon characters like Doraemon and Shin-chan. I hope you enjoy the course and look forward to working together with you this quarter!
Diana Dai she/her
Hi, I’m Diana! I enjoy watching movies and exploring new types of food 🍜. I am a huge fan of Iron Man and Marvel comics 🦸. I am super excited to part of your CSE 373 journey this quarter. Looking forward to getting to know everyone!
Sam Long he/him
Howdy everyone! I’m a senior from Spokane WA. I’m an officer for UW’s Game Development Club, and I like to program and make pixel art for games. I’m currently working on a gameboy pirate game! Talk to me if you’re interested in learning more about game development or joining GDC!
Aerin Malana she/her
Hey! ✨I’m Aerin, a third-year from Kent, WA studying CS + Diversity, focused in centering a decolonized, justice-oriented approach to CS. When I’m not bingeing my favorite shows, organizing in my communities, or drinking obscene amounts of coffee, I’m napping, on TikTok, or both.
Hang Do she/her
I grew in a small city in Vietnam and came to Seattle four years ago. I first learned about computer science through the introductory courses here at the UW and loved it ever since. This is my first time TAing for CSE 373 and I’m super excited :D
Megan Shi she/her
Hello! My name is Megan and I’m a junior studying cs and minoring in nutrition, but I was intended BioE coming into UW. Outside of school, I enjoy baking (macarons especially) and trying new types of foods. I also like watching movies and playing video games!
Shumaila Ahmad she/her
I graduated from a STEM focused high school but I never really appreciated coding until I took this class! In my free time, I like to read, bike, and take photos. Over the summer, the most I biked was 20 miles from Redmond to Bothell!
Melissa Lin she/her
Hi! I’m Melissa and I was born and raised in Redmond, WA. I’m in my second year of studying computer science, and I’m super excited to TA for 373 this quarter. In my free time, I love drinking boba and listening to the Hamilton soundtrack on repeat :)
Yan Zhe Ong he/him
I am from Singapore, and it is always 95 degrees there so I much rather the cool breeze of Seattle. Fun fact: I served two years in the military and got to march 45 miles consecutively and parachute out of a plane! In my free time, I love Sports and YouTube!
Eric Fan he/him
Hey there! I’m Eric, a junior studying Computer Engineering! I enjoy playing badminton (I used to compete nationally) and playing tag with my dog (her name’s Nemo—she’d love to meet you!). I’m thrilled to support you in discovering the societal relevance of the code you write!
Paul Karmel he/him
Some fun facts: I have a pet bearded dragon named Alfalfa, take photos of wildlife in my free time (instagram shameless plug @birdboozled), and am hoping to publish a board game on animal trivia by February 2021! https://www.triviavore.com/
Aman Mohammed he/him
Hello! My name is Aman and I am super excited to be a part of your CSE 373 experience. A few things about me – I was born and raised here in Seattle and my love for coffee reflects it :) Oh, and crunchy peanut butter is better than creamy, change my mind.
Kristen Hewson she/her
Greetings! It’s Kristen here. I am in my forth year studying Business: Information Systems. A few of my loves: maple syrup, theater, laughing with friends/family. I’ll be working as a tech consultant post grad and am excited to learn with y’all this quarter. Let’s do this thing!!
Jeter Arellano he/him
In Federal Way, WA born and raised. JetBrains IDEs was where I spent most of my days. Codin’ out barely’ relaxin’ all cool. And not able to do anythin’ outside of school. Come chat with me via email or my office hours! & Fun fact: big fried rice consumer.
Julia Wang she/her
Hey there! I’m Julia, a current sophomore. Recently, I’ve been trying to get my license before my permit expires. Check in with me to see if I made it! I’m taking the academic quarter off for an internship, but I can’t wait to tackle some runtime efficiencies with y’all in 373 :)
Amy Xu she/her
Hello! I’m a senior studying CS and History, and excited to TA for you all this quarter. I grew up in Kenmore, WA and enjoy skiing, tennis, and trying new restaurants!
Kenny Le he/him
Hey everyone! My name is Kenny and I’m a junior studying Human Centered Design & Engineering (HCDE). Most of the time you can find me staying up till 3 am and snacking on some Cliff bars. Can’t wait to meet y’all and learn more about data structures & algorithms!
Batina Shikhalieva she/her
Hi! I have been TA in the CSE department for 7 quarters already (yee-haw)! I’m very excited to be part of your CSE 373 experience this quarter. The reason I teach is to make sure you succeed and enjoy the class. Please feel free to reach out to me with any questions or concerns!
Nalu Zou he/him
Hi, I’m Nalu and this is my second year at UW. I enjoy developing games on the side (checkout “MiniState” on Steam), reading about world history, and learning about yogurt engineering.
Hannah Cheung she/her
Hello! I’m a senior pursuing a 5th year BS/MS in Computer Science. I originally was a Bioengineering and Statistics major before entering the Allen School. I enjoy figure skating, listening to K-pop music, and working towards my goal of becoming trilingual. Nice to meet you all!
Joyce Elauria she/her
Formerly a biochemist, now an aspiring cybersecurity professional! I transferred to UW from Olympic College in 2018, and understand the transfer struggle (my double major was an accident). I also have a high affinity for Dungeons and Dragons, competitive swimming, and coffee <3
Lea Quan she/her
Hello! I’m from Bellevue, WA and this is my third time teaching this course. I did two virtual internships this year and I’d love to share some tips on finding your passion! Some of my quarantine hobbies include trading, painting, and trying takeout from different restaurants :3
Samek Mulepati he/him
Hey everyone! I’m from Shoreline, Washington, and I am in my second year at UW. Besides Ta’ing, I enjoy hiking, drawing, and everything mechanical keyboards. Excited to interact with you all this quarter!
Joy Dang she/her
Hi, I’m Joy! I was born and raised in Pullman, Washington. Some of my hobbies are painting, playing tennis, and reading. I recently started doing digital art and am really enjoying it so far! I also like to watch a lot of shows; some of my favorites are The Office and New Girl!
Sonia Fereidooni she/her
Hi all, I’m Über excited to be your TA this quarter! Some things I like doing outside of CS is playing ‘Yu-Gi-Oh!’, domesticating street cats with my roommate, or watching my favorite show, ‘The Parkers’ on Netflix🤓! Also, I’m from Canada eh 🇨🇦🍁☝🏽😌 Let’s talk about syrup!
Markus Schiffer he/him
Hi everyone! I’m Markus, and I’m a junior from Bellevue. Outside of computer science, I enjoy skiing, flying model airplanes, and hanging out with friends (pre-pandemic). I’m excited to TA this quarter and I’m looking forward to meeting you!
Sherdil Niyaz he/him
I’m a fourth-year PhD student who caught the teaching bug while I was in undergrad. It’s become a huge passion of mine since then, and I hope to become a teaching professor once I complete my degree!
Grading
All submitted work in this course is graded on a Satisfactory (S) or Not yet (N) grading scale. Your final grade in the course is determined by the quantity of work submitted. All criteria for a grade must be met in order to earn that grade.
- 4.0
- S on all 3 projects.
- S on all 6 checkpoints.
- S on all 6 portfolio videos.
- E (exemplary) on the research project.
- S on all 6 checkpoints.
- 3.0
- S on all 3 projects.
- S on 4 checkpoints.
- S on 3 portfolio videos.
- No research project required.
- S on 4 checkpoints.
- 2.0
- S on 2 projects.
- S on 4 checkpoints.
- No portfolio required.
- No research project required.
- S on 4 checkpoints.
- 0.7
- S on 1 project.
- S on 1 checkpoint.
- No portfolio required.
- No research project required.
- S on 1 checkpoint.
These grade criteria capture the learning objectives in the course, so falling short in any area may result in a lower grade determined at the instructor’s discretion.
Learning habits
We want everyone to succeed in this class and learn as much as we can, not only about “course content” but also about ourselves and how we can help the world around us. We’ve already introduced several meta-learning concepts highlighting the importance of deliberate practice, learning cooperatively, and atomic habits. These concepts have very practical tips that we can apply to help us in any course.1
- Create a study schedule
- Like eating breakfast or working out at the same time, students who create a study routine and have the discipline to stick to it are able to study information over a longer amount of time instead of staying up late the night before.
- Connect with other focused students
- No matter the facet of life, focused and successful people inspire those they’re around. Find a study buddy whose work ethic you admire and set up an online review session with them.
- Design your study space
- While it may seem counterintuitive to take extra time to clean your room or office before settling down to study, a study by Princeton University found that people who keep their spaces clean are able to process information and focus better.
- Ask for help
- If you’re studying and realize you don’t understand a concept or theory, reach out as soon as possible for clarification rather than trying to go it on your own.
- Stay mentally and physically healthy
- Online students are likely to spend more time at their computers than traditional learners, so it’s important to take breaks, go on walks, get good sleep, and eat healthy food.
Communication is a key part of our lives now more so than ever, so we ask that you follow these guidelines to ensure everyone has the best experience. Small actions can go a really long way when everyone brings their full engagement.
- Be especially kind and intentional
- In the online world, feelings are hard to convey over text and prioritizing efficiency can make communication exhausting. Take an extra moment to turn on your camera before you speak, personalize your discussion messages, and state your intentions out loud.
- Take space, make space
- Some of us might feel more comfortable sharing our experiences than others. Recognize when we’ve been taking space in the conversation and turn the stage over to someone who hasn’t had a chance to shine yet.
- Different situations require different communication
- How we engage in an environment depends on the situation. In group meetings, attention should be paid to the speaker. In brainstorming or collaboration, we can be more flexible in how we communicate.
Data types
In computer science (CS), a data type (or simply type) defines possible values and operations. For example, the result of adding together two integers 37 + 3 is the integer 40, whereas the result of adding together two strings "37" + "3" is the string "373". The choice of data type determines the result of the operation.
An abstract data type (ADT) defines expected operations and behavior without specifying a particular implementation for the behavior. For example, the list ADT is a collection representing an indexed sequence of elements. In Java, the list ADT is typically represented with the List interface.
A data structure defines algorithms for organizing data to implement a particular abstract data type. For example, resizing arrays and linked nodes are two data structures that can implement the list ADT. In Java, these are represented with the ArrayList and LinkedList classes, which implement the List interface. Data structure implementers maintain invariants (programming assumptions) to ensure the data structure’s correct behavior.
ArrayListclass invariant- The
i-th item in the list is always stored atelementData[i].
Give an example of an operation that is very slow on ArrayList.
Adding or removing from index 0 of the list will be slow because the implementation needs to maintain the class invariant. Likewise, the contains or indexOf operations may need to perform a linear search through the entire array to find the index of a given element.
In this course, we’ll learn how to design, analyze, and critique data structures and algorithms (and applications thereof). Throughout the course, we’ll often revisit ArrayList and linear search as examples of a naive approach: a simple or straightforward way of solving a problem. We’ll go beyond computer programming by turning our attention towards complicating questions, such as:
- Design data structures and algorithms by implementing and maintaining invariants.
- How might we use this class invariant to implement a different ADT? What modifications (if any) are necessary?
- Analyze the running time and design values of data structures and algorithms.
- What are the runtime trade-offs? What assumptions are encoded by the choice of abstractions for the problem?
- Critique the application of data structures and algorithms towards complex problems.
- What assumptions are encoded by representing machine-flagged content as data points in a priority-based queue?