1 Handy links

2 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; multi-threading and parallel algorithms; P and NP complexity classes.

3 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
  • Multi-threading and Parallel Algorithms
  • P and NP complexity Classes

3.1 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 trade-offs among different choices of abstract data type
  • Understand the inner workings and tradeoffs of various sorting algorithms
  • 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 multi-threading
  • 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.

3.2.1 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

4 Platforms

Platform Purpose
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

5 Assignments and Office Hours

Assignments and Learning: Learning new things is challenging, and requires a repeated process of being confused, getting stuck, and making small breakthroughs. While less of your grade is determined by assignments this quarter than perhaps you are used to, this does not make them any less important to you as a learner. We hope that the reduced grade percentage on assignments will allow you to focus more on the learning process, and make it less tempting to simply cheat in order to make sure you have the correct solution. Assignments are also intended to supplement lecture -- do not expect the materials to match precisely. We really hope you get something out of these and learn from them!

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.

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 occurring.
  • 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!

6 What to expect on the Ed Board

The Ed board serves two primary purposes for this course:

  • All course communication (announcements, etc.) will be made through Ed. In the cases of important announcements from the course staff, you will receive an email from Ed. All students are responsible for reading all announcements made on Ed which are also pushed to your email inbox.
  • Ed is also a place to ask and answer questions asynchronously, meaning you do not need to attend office hours to receive a response.

When using Ed as a place for asking/answering questions, here are some guidelines, expectations, and best practices we request that you follow:

  • There are several ways you may post on Ed. It’s your choice how you wish to post, but here’s the options and their considerations:
    • Privately: A private post will be visible by staff only. This is the best choice for inquiries which you know will only apply to you (e.g. a question about a personal circumstance, a question about an assignment that requires explaining a partial solution in order to ask). The downside to a private post is that only staff will see it, and so response times will likely be slower, and the answer will not have the opportunity to benefit other students
    • Publicly and Anonymously: A post where the contents of the post are visible to the entire class, but your name is not (be aware that the staff can see the identity of the poster). Public posts are best for questions that other students may be able to answer or that other students may benefit from having the answer to. For example, questions about course concepts or assignment instructions are most likely best made as public posts. Please do not make public posts that mention assignment solutions, or partial assignment solutions (even after the deadline has passed). The advantages to public posts are that you are more likely to get a faster response (as other students may be able to respond in addition to staff), and you’ll be contributing to the course community by adding to a information bank that’s available to all other students. Historically, the vast majority of posts fit into this category.
    • Publicly and Non-Anonymously: This category has all of the same benefits of a public anonymous post, but with the added benefit of fame and notoriety among your classmates. This type of post is best suited for posts that require people to know who made them (e.g. coordinating study groups), for people who might like to have hearts or instructor endorsements attributed to them personally.
  • We will have course staff members checking Ed every day of the week, but we do not have the resources for eyes to always be on Ed. Therefore, here are some response timing expectations:
    • Posts made outside of standard business hours should be expected to have slower response times. This applies to posts made early in the mornings, late at night, or over weekends. No staff members will be assigned to watch Ed on university holidays and breaks, so you may not get a response until after the holiday/break has passed.
  • Ed is not necessarily the best tool for all types of questions. For example, some questions may include misconceptions that require follow-up to help address. We encourage you to ask any question you have on Ed, but please recognize for some questions we may respond with a request that you come to office hours for a full response.
  • We will not help with debugging over Ed. Debugging is a skill that all computer science students need to develop an hone, and debugging questions asked over Ed often times turn into staff members doing debugging for you rather than with you. If you have a question about why your code fails to run, or fails to pass certain tests, please attend office hours instead.