Handy links:
Course Description
Covers abstract data types and structures including dictionaries, balanced trees, hash tables, priority queues, and graphs; sorting; asymptotic analysis; fundamental graph algorithms including graph search, shortest path, and minimum spanning trees; multithreading and parallel algorithms; P and NP complexity classes.
Course Overview
The goal of this course is to expand your tool kit for solving a variety of computational problems, and to evaluate the quality of your solutions. In particular, we will cover:
- Abstract Data Types and their Data Structures, including:
- Dictionaries
- Balanced Trees
- Hash Tables
- Priority Queues
- Graphs
- Sorting Algorithms
- Asymptotic Analysis
- Fundamental Graph Algorithms, including:
- Graph Search
- Shortest Path
- Minimum Spanning Trees
- Multithreading and Parallel Algorithms
- P and NP complexity Classes
Learning Outcomes
At the conclusion of this course, a successful student will be able to:
- Explain what is distinct about each abstract data type, including:
- The operations associated with each
- The resource complexity of each operation (time and space)
- When each can and should be used
- The tradeoffs among different choices of abstract data type
- Use graph terminology with fluency
- Identify and justify the resource complexity of the covered graph algorithms
- Solve new graph problems by using or modifying a pre-existing graph algorithm
- Analyze a pre-written algorithm to determine its resource complexity
- Produce programs that make non-trivial use of multithreading
- Identify opportunities to accelerate programs using parallelism
- Identify the characteristics of problems which belong to classes P and NP, then reason about the implications this classification has on the efficiency of solutions to such a problem.
Eligibility
You should take this course if and only if
- You have credit for CSE 311 (Foundations of Computing I) or equivalent
- You are a CSE major
Background
This course will assume competency with Java programming (covered in the CSE12X or CSE14X sequence) and knowledge of several topics from Discrete Math (covered in CSE 311)
In particular, we assume knowledge of:
- Logarithms and identities (Log rules)
- Sets
- Functions
- Proof Techniques
- Logic and Notation
- Recursion
- Java Programming
| This Website |
Central repository of course information and content including: syllabus, schedule, file hosting, readings, assignment writeups, etc. |
| Canvas |
Linking to all of the other tools, lecture recordings, roster maintenance |
| Ed Message Board |
Course content and policy questions |
| Gradescope |
Homework submission and grading |
What to expect in this course
In the opinion of this instructor, a data structures course should serve to:
- introduce students to common, important, or otherwise noteworthy data structures
- provide opportunity for students to develop skill in selecting, using, and modifying data structures.
Since developing a skill is a much more substantial undertaking than understanding prior work of others, a substantial portion of your homework time will be spent on developing that skill. This will be at times uncomfortable, occasionally frustrating, but hopefully always fun and valuable in retrospect. I have a few guidelines/suggestions for how you can get the most out of this course:
- Follow the instructions in the assignments. I’ve been a student before, and I understand the dizzying experience of learning something brand new. For this reason, I do not ask trick questions that are specifically intended to mislead you. If a question seems misleading, then most likely either there’s something about the instructions or the content that you’re missing, or else I made an error in drafting the assignment. In either case, the best thing to do is ask!
- Think carefully and precisely: While I will not purposefully mislead you, I may ask questions that are specifically designed to expose and correct a misleading intuition or common misconception.
- Don’t expect homework to match lecture perfectly: Lecture is designed to introduce topics/concepts/strategies, and show how they operate. To maximize the future usefulness of this course’s content, it covers topics whose applications are broad. We will explore that breadth through the combination of lectures and assignments. Almost always, I will tell you which topics to employ in the assignments. It may not be obvious how or why that concept is relevant, but I promise it is. The goal of the assignment is to broaden your understanding of the concept and its applications so that you are better prepared to use it in a greater breadth of circumstances after you complete this class.
- Think critically about assignment requirements. We make every attempt to ensure that the assignment specifications are sufficient to complete each task. It may be the case, however, that we have intentionally left space for you to carefully interpret the requirements to make design decisions. If there are cases where you perceive the assignment requirements as ambiguous, first reason carefully about all potential interpretations to see if you can rule any out. In most cases, either there is only one interpretation is consistent with class content and/or the other requirements of the assignment, or else there are several interpretations which will equivalently satisfy the requirements.
What to expect in office hours
Instructor and TA office hours will be available to assist you in understanding course concepts and applying those concepts to your assignments. Office hours should never be used as a substitute for your own learning or for your own earnest effort. As such, the amount of assistance the course staff will provide should correlate with the amount of effort you’ve made and understanding you demonstrate. In short, the more effort and understanding we see from you in office hours, the more precise the help we will provide. If you’re just beginning to solve the problem or are missing some concept then the help given will be more conceptual in nature. You should not expect direct feedback on your current work unless the task is nearly completed.
Our TAs are critical to the operation of this course, and are responsible for a number of activities (office hours, grading, staff meetings, leading section, personal prep, etc.). Because variety of tasks they are involved in, office hours is a limited resource. As such, we have some expectations in place designed to most equitably provide office hours to students in the course:
- When there is a queue in office hours, we will limit each student-TA interaction to addressing just a single question. To ask multiple questions you will need to re-enter the queue. The reason for this policy is to help as many students as quickly as possible, since after a first round of assistance you will have an opportunity to make more progress on your own before your turn comes up again. I recommend arriving prepared with the question that is your biggest
blocker
to progress.
- Work-in-progress code is often difficult for a third-party to read. Be prepared to help the course staff member to understand your approach by explaining your high-level approach, knowing what portions of your code as responsible for each step of that high-level approach, and providing as much information as you have about where you think the error might be occuring.
- For clarification questions or high-level conceptual questions, consider using the Ed Message Board first. Your question may already be answered there, and even if not then you may get an answer faster compared to going to office hours. If what you ask is something that would be more effective to discuss in office hours, we’ll let you know that, too!