Link

Computer Programming II

University of Washington, Spring 2022

This is CSE 143 Spring 2022 at the University of Washington. Looking for Summer 2022?

Computer science is the study of how our ideas and values can be automated and reproduced by computers. In CSE 142, you learned how to define programs that captured structure and minimized redundancy using methods, conditions, and loops. CSE 143 continues by asking: How do we define programs that model the world as data and make decisions using this data abstraction?

By the end of the course, students will be able to:

  1. Model concepts by selecting and applying appropriate data abstractions to manage program state.
  2. Define data structures that implement data abstractions using object composition and recursion.
  3. Design high-quality programs that combine data abstraction with computational decision-making.

CSE 143 is organized around 7 applications of data abstraction and decision-making divided into 2 modules and a final assessment.

Schedule

Data Structures

Objects

3/28
Welcome
3/29
SecObjects
3/30
Comparable
3/31
SecComparable
4/1
Lists

Linear Collections

4/4
Array Lists
4/5
SecArray Lists
ChkArray Lists
4/6
Stacks and Queues (Code Quality)
4/7
SecStacks and Queues
A1Letter Inventory
4/8
Reference Semantics

Linked Data Structures

4/11
Linked Nodes
4/12
SecLinked Nodes
ChkLinked Nodes
4/13
Linked Lists
4/14
SecLinked Lists
A2Music Playlist
4/15
Efficiency

Associative Collections

4/18
Sets and Maps
4/19
SecSets and Maps
ChkSets and Maps
4/20
Applications
4/21
SecNested Collections
A3Absurdle
4/22
Guest: Leilani Battle

Recursion

Recursive Programs

4/25
Recursion
4/26
SecRecursion
ChkRecursion
4/27
Structural Recursion
4/28
SecStructural Recursion
A4Grammar Solver
4/29
Generative Recursion

Midterm Portfolio

5/2
Portfolio
5/3
SecPortfolio
5/4
Portfolio
5/5
SecPortfolio
5/6
Portfolio

Combinatorial Programs

5/9
Recursive Enumeration
5/10
SecRecursive Enumeration
ChkRecursive Enumeration
5/11
Recursive Backtracking
5/12
SecRecursive Backtracking
A5Anagram Solver
5/13
Programming the World

Tree Data Structures

5/16
Binary Trees
5/17
SecBinary Trees 1
ChkBinary Trees
5/18
Binary Search Trees
5/19
SecBinary Trees 2
A620 Questions
5/20
Implementation Inheritance

Final Assessment

Data Compression

5/23
Huffman Coding
5/24
SecTA Choice
5/25
Next Steps
5/26
SecTA Choice
AXHuffman Coding
5/27
Portfolio

Final Portfolio

5/30
Holiday
5/31
SecPortfolio
6/1
Portfolio
6/2
SecPortfolio
6/3
Portfolio

Values and policies

The education you receive in this course can help prepare you for programming jobs, but this isn’t the only purpose for learning computer science.1 Education is not only about yourself and your personal gain, but also about all of us and our capacity to live together as a community.

The University of Washington acknowledges the Coast Salish peoples of this land, the land which touches the shared waters of all tribes and bands within the Duwamish, Puyallup, Suquamish, Tulalip and Muckleshoot nations. Among the traditions of the Coast Salish peoples is a value for the connectedness between all living things and a recognition of the unique ways that each of us comes to know something.2

Modern education has the idea that we all need to know the same thing. At the end of the lesson, everyone will know the same thing. That’s why we have tests, that’s why we have quizzes, that’s why we have homework: to ensure we all know the same thing. And that’s powerful—that’s important—within a certain context.

But for native culture, the idea that each listener divines or finds their own answer, their own meaning, their own teaching from the story is equally powerful—that each person needs to be able to look at the world and define it for themselves within their culture and then also find a way to live in that world according to the teachings of their people in their culture.

Our course emphasizes the following values and policies.

We are responsible for each others’ success
Everyone has a right to feel like they belong in this course. We’ll need to act with compassion and caring to collaborate with each other. Although we will need more than just unexamined commitments to collaboration, listening, empathy, mindfulness, and caring,3 the following guidelines offer a starting point for ensuring compassion toward each other.4
  • Listen with intention to understand first and form 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.

You should expect and demand to be treated by your classmates and teachers 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, meet our advisors during quick questions or contact the College of Engineering.

We recognize everyone has unique circumstances
Do not hesitate to contact the instructor by private discussion post or appointment. The sooner we are made aware of your circumstances, the more we can help. 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.
We believe everyone wants to learn
Education is about shaping your identity as much as it is about content knowledge. In school, the consequences of making mistakes are relatively small. But the habits you form now—repeated over days, weeks, months, or years—determine who you will be in the future. Now is the best time to practice honest habits. We ask that you do not claim to be responsible for work that is not yours. Don’t request a copy of someone else’s work, don’t provide your work to another student, and don’t post your solutions publicly. When you receive substantial help from someone else, include a citation.
The following types of collaboration are encouraged:
  • Asking the course staff.
  • Discussing and collaborating on lessons, sections, or questions from other students on the discussion board (without providing assessment code).
  • Communicating your approach to an assessment at a high-level in such a way that the recipient cannot reliably reproduce your exact work (without providing assessment code).
The following types of collaboration are prohibited:
  • Submitting work that contains code copied from another resource, even with edits or changes, except for resources directly provided by the course staff.
  • Giving or receiving any assessment code (or substantially similar code) not written by you at any point, in any form, for any reason, for any amount of time. This includes code written by classmates, former students, family or friends, and online resources, among other sources.
  • Giving or receiving a walkthrough for an assessment such that the work produced can be entirely and reliably reconstructed. This includes classmates, former students, family or friends, and online resources, among other sources.
We want to create trusting relationships in this course, but we know our systems are far from perfect. If you submit work in violation of these policies but bring it to the attention of the instructor within 72 hours, you may resubmit your own work without further consequence. Rather than blame students, we want to fix or replace broken systems that compel students to lose trust.

Deliberate practice

In a traditional classroom, you attend class while a teacher lectures until time is up. Then, you go home and do the important work of applying concepts toward practice problems or assignments on your own. Finally, you take an exam to show what you know.

Today, we know that there are more effective ways to learn science, engineering, and mathematics.5 Think of learning computer science as learning how to ride a bike. Quite a few people know how to ride a bike. But how many of them learned to ride a bike through 50 minutes of lecture three times a week? Probably no one—learning to ride a bike requires riding an actual bike! Furthermore, in the context of learning programming:6

A key finding is the importance of code-reading skills to underpin other aspects of code literacy. Linguists hypothesise that we acquire writing style by reading, and there is evidence that this applies to programming as well as to natural language.

In this course, we will learn through deliberate practice: a learning cycle that starts with sustained motivation, then presents tasks that build on prior knowledge, and concludes with immediate, personalized feedback. Each week will scaffold your learning to make the most of our class time.

  1. Before MWF class, learn about the programming concepts in the pre-class preparation.
  2. During MWF class, practice applying the concepts with code reading and planning activities.
  3. During TuTh quiz section, practice appyling the concepts with code writing activities.
  4. After Tu quiz section, complete a brief code writing check to see what you need to review.
  5. After Th quiz section, work on the weekly code writing assessment to apply what you learned.

Expect to spend 5 hours in class and at most 10 hours outside of class working on this course. Some weeks may be more or less time than other weeks. If you find the workload is significantly exceeding this expectation, talk to your TA.

Grading in this course encourages learning through deliberate practice by emphasizing revision and resubmission of work. All coursework is designed around feedback loops where you try something, get feedback, then try again. Grades are based on what you eventually learn through this process. Only the requirements listed under a Canvas module count toward your final grade.

2.0 or greater
Completion of all requirements in the Data Structures module.
Completion of the Lessons requirement in the Recursion module.
3.0 or greater
Completion of all requirements in the Data Structures module.
Completion of all requirements in the Recursion module.
4.0
Completion of all requirements in the Data Structures module.
Completion of all requirements in the Recursion module.
Highest marks across all parts of the Final Assessment.

References

  1. Mark Guzdial. 2021. Computer science was always supposed to be taught to everyone, and it wasn’t about getting a job

  2. Roger Fernandes. 2012. Roger Fernandes: Artist/Storyteller/Educator

  3. Brian Arao and Kristi Clemens. 2013. “From Safe Spaces to Brave Spaces: A New Way to Frame Dialogue Around Diversity and Social Justice” in The Art of Effective Facilitation

  4. Asao B. Inoue. 2019. “Sample Charter for Compassion” in Labor-Based Grading Contracts: Building Equity and Inclusion in the Compassionate Writing Classroom

  5. Scott Freeman, Sarah L. Eddy, Miles McDonough, Michelle K. Smith, Nnadozie Okoroafor, Hannah Jordt, and Mary Pat Wenderoth. 2014. Active learning increases student performance in science, engineering, and mathematics

  6. Andrew Luxton-Reilly, Simon, Ibrahim Albluwi, Brett A. Becker, Michail Giannakos, Amruth N. Kumar, Linda Ott, James Paterson, Michael James Scott, Judy Sheard, and Claudia Szabo. 2018. Introductory programming: a systematic literature review


Table of contents