Announcements

Moving learning and assessment online

HW 9: Contraction Hierarchies and EX 7: Concurrency were released earlier today. The course will be moving entirely online starting next week. Instead of in-person office hours, office hours will be made available via Zoom. A pre-recorded lecture video has been prepared by Josh Hug for Programming the World. (You’ll enjoy it!) There will also be a video for Computational Complexity at a later date. Quiz section next Thursday will be held online via Zoom.

After consulting with the school and listening to your feedback, we’ve decided to cancel the final exam. No other assignments or assessments will take its place.

Perhaps you have questions about how your final grade will be computed. At this time, the staff is focused on helping everyone achieve the highest possible understanding and grades on the remaining assignments, so we don’t have answers to those questions. Office hours this week will be hosted on Zoom at the regularly-scheduled times, and quiz sections on Thursday will also be converted to additional office hours.

If you’d like to redo one programming homework assignment without lateness penalty, use the end-of-quarter extension provided in the syllabus. Regrade requests for mismarked rubric items are open for written exercises through Saturday night.

A word on the coronavirus situation. It’s okay to feel nervous. It’s also okay to feel anxious about the future. The more people who are concerned about the danger of coronavirus, the less dangerous it becomes. But too much concern can also negatively influence mental health. If you would like to talk with someone, support is available through Let’s Talk and Hall Health.

HW 8: HuskyMaps Server and EX 6: Parallelism

Part of quiz section on Thursday will include live coding practice with fork/join parallelism. Bring your laptop and follow the setup steps below.

1. Make a new IntelliJ project.
2. Download the skeleton zip. Unzip the file.
3. Copy and paste the Java files into your project.

HW 8: HuskyMaps Server is due Fri, Mar 6. EX 6: Parallelism is due Tue, Mar 10.

The parallel programs we’ve been developing so far have followed a standard pattern: divide, solve base cases, and then recombine. This primarily works because each computation can be computed independently. However, we’ll need a new approach (multi-pass parallel algorithms) if the results of later computations depend on the results of earlier computations.

We’ve also been suggesting that parallel algorithms do not necessarily execute in the same order every time. In the examples we’ve seen so far, the order of operations hasn’t affected the outcome of the program. Later next week, we’ll look at concurrency issues that arise when multiple threads attempt to access and modify the same objects or shared resources.

HW 7: Seam Carving and EX 5: Sorting

HW 7: Seam Carving is due Fri, Feb 28. EX 5: Sorting was released earlier today and is due Tue, Mar 3.

In the first half of next week, we’ll see how data structure analogies and ideas inspire three important applications in sorting: the quicksort variant used in modern Java, the theoretical (but unknown!) best-possible comparison sorting algorithm, and a class of sorting algorithms that are even faster than the best-possible comparison sort (with a catch). In the second half, we’ll dive into parallelism: a new programming paradigm that leverages multiple computer processor cores to return a result more quickly. Most of the remaining readings will be excerpted from Dan Grossman’s text: you might find it useful to read the full chapters for additional context and examples.

HW 6: A* Search and EX 4: Society

HW 6: A* Search and EX 4: Society were released earlier today. We’ve also released HW 7: Seam Carving. It is due on Fri, Feb 28.

The midterm exam will be graded over the weekend. For this week’s charrette, complete the Midterm Exam (Solution) in a group, discuss your problem solving process, and submit a completed version to Gradescope.

Over the last few weeks, we’ve learned how to solve problems using a variety of data structures and algorithm templates. Next week, we’ll explore how to apply these algorithm ideas through a case study of sorting, one of the most well-studied problems in computer science. Sorting is a critical operation in many areas of computer science with several surprising analogies and connections to the data structures concepts we’ve learned.

Midterm Exam

The Midterm Exam is 4:30–5:20 PM Friday, Feb 14 in ARC 147.

In lecture this week, we’ll begin by analyzing shortest paths in weighted digraphs: an important problem to solve for efficient navigation routing in HuskyMaps. Later in the week, we’ll apply strategies for solving problems by formulating them as graphs and then evaluate our solutions in terms of their whole effects.

HW 5: Point Sets and EX 3: Data Structures

The Midterm Exam is 4:30–5:20 PM Friday, Feb 14 in ARC 147.

HW 5: Point Sets and EX 3: Data Structures were released yesterday. For the programming homework, you may use the simplified pruning rule rather than the exact pruning rule.

For additional practice on week 4 concepts, refer to the Extra Practice Problems from section and the study guides that accompany each lecture.

• Left-Leaning Red-Black Trees
• Hashing
• Multi-Dimensional Data

So far, we’ve analyzed the implementation details and algorithm trade-offs of important data structures. Next week, we’ll explore the graph data type, a different paradigm for data organization that emphasizes the relationships between data. We’ll shift our focus towards learning how to apply graph algorithms to solve novel problems.

HW 4: Priority Queues and EX 2: Heaps

HW 4: Priority Queues and EX 2: Heaps were released earlier today. The TAs have created a video walkthrough (CSE login required) of a big-O proof for EX 1.

For additional practice on week 3 concepts, refer to the Extra Practice Problems from section and the study guides that accompany each lecture.

• B-Trees
• Priority Queues and Heaps

Next week, we’ll explore three data structures that go beyond this week’s perfectly balanced B-trees and heaps.

1. A practical and surprisingly simple balanced binary search tree implementation known as a left-leaning red-black tree.
2. A new approach to implementing sets and maps through hashing, an idea that underpins many high-performance systems.
3. A specialized tree data structure for multi-dimensional datasets such as coordinates on a map with additional applications for machine learning.

HW 3: Autocomplete and EX 1: Asymptotics

HW 3: Autocomplete and EX 1: Asymptotics were released earlier today. Autocomplete marks the first of five data structures and algorithms that we’ll be building for HuskyMaps.

For additional practice on week 2 concepts, refer to the Extra Practice Problems from section and the study guides that accompany each lecture.

• Iterative Algorithm Analysis Study Guide
• Recursive Algorithm Analysis Study Guide
• Sets, Maps, and BSTs Study Guide

Next week, we’ll apply the Algorithm Design Process to optimize binary search trees and avoid worst-case runtime. We’ll start by reinventing B-trees, a family of search trees that grow from the root rather than the leaves!

HW 2: Deques and Peer Charrettes

HW 2: Deques was released earlier today. In this homework, you’ll explore the entire life cycle of debugging, implementing, using, and testing data structures. Submit frequently to Gradescope to receive autograder feedback on your work.

The peer charrette for week 2 has also been posted to Gradescope. It’s worth 2 points in the Activities grading category (shared with reading quizzes). Submit your charrette in groups of 2 or 3 students. The peer charrette is a flexible collaboration activity designed to reward group study. Some things you might find helpful to do during charrettes are listed below and also repeated on the Gradescope submission page.

• Reviewed concepts from class.
• Discussed high-level design plans.
• Shared ideas about tests and edge cases.
• Debugged code and proposed hypotheses for errors.
• Solved study guide problems.

I just posted the Algorithm Analysis Study Guide, which provides an overview of today’s lecture and reading as well as additional recommended practice problems to help solidify your understanding.

Readings and lecture materials for next week are posted on the course website. Look forward to runtime analysis strategies and a first look at binary search trees, our starting point for exploring fundamental data structure ideas.

Welcome to CSE 332

All course information, announcements, and homework will be posted on the course website, cs.uw.edu/332. Ask and answer questions on the Campuswire Class Feed. Use Campuswire Chatrooms to quickly get in touch with other students, TAs, or the instructor via direct message.

The Syllabus Reading Quiz is due at noon on Monday, January 6 with late submissions accepted for full credit until 12:30 PM Wednesday. There will be a reading quiz due at noon before most lectures. Programming Homework 1 will be released Monday and due 11:59 PM Friday, January 10. Every assignment will be scored on Gradescope: the grade you see is the grade you’ll receive. You can resubmit as often as you like before the deadline.

You can schedule an appointment with me or find your section TAs on the Staff page. Chat with us over Campuswire! The course staff are your academic mentors: our responsibility is not only to teach the course, but also to help you meet your learning and career goals inside and outside of the classroom.

Hello, World!

This website is in beta. All posted information tentative.