# Parallel and Sequential Data Structures and Algorithms

## Overview

15-210 aims to teach methods for designing, analyzing, and programming sequential and parallel algorithms and data structures. The emphasis is on teaching fundamental concepts applicable across a wide variety of problem domains, and transferable across a reasonably broad set of programming languages and computer architectures. This course also includes a significant programming component in which students will program concrete examples from domains such as engineering, scientific computing, graphics, data mining, and information retrieval (web search).

Unlike a traditional introduction to algorithms and data structures, this course puts an emphasis on parallel thinking — i.e., thinking about how algorithms can do multiple things at once instead of one at a time. The course follows up on material learned in 15-122 and 15-150 but goes into significantly more depth on algorithmic issues. Concepts covered in this class include:

• ### Problem vs. Algorithm

A problem defines an interface while an algorithm defines a particular method to solve the problem. For example, quicksort is an algorithm to solve the sorting problem. Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components.

• ### Asymptotic Analysis

In this class, we analyze performance in terms of work, span, and space using big-O analysis. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and various counting arguments.

• ### Techniques in Algorithm Design

We cover techniques that play a key role in the design of most algorithms and data structures, including: collections (sets, sequences, priority queues, ...), divide-and-conquer, contraction, the greedy method, balanced trees, hashing, sparse matrices, and dynamic programming.

## Course Textbook

The professors for the course are developing a textbook. You can find the current version here. We will also post "chapters" on the schedule, which will be updated during the semester. Comments are welcome and you can send them directly by email to Professor Acar.

• 45% Assignments
• 30% Exams
• 25% Final

Considering the size of the class, the grading policy is designed to be flexible and to minimize the need for handling exceptions. Please read the policies below carefully. If you do not follow them, you may lose points. In other words, these policies will be enforced. For example an email such as this "Professor, I understand that it is late, but while I was working on the written part my battery fell out of my laptop and when I rebooted, it started installing updates without my permission and I couldn't access my work." violates two policy items 1) requesting additional time for unacceptable reasons and 2) emailing the instructors about non-private matters. Such emails would lead to a zero grade for the relevant assignment.

Our philosophy is to use grading only as a tool to encourage clarity of explanation, introspection, and self-learning. We hope that both instructors and students can think about grades in as relaxed a manner as possible. We don't want you to stress out about grades, because we don't think they matter as much as what they are made up to be. In return, we expect you to be relaxed about grading! This means that you should not sweat the few points that you might have lost in an exam or a homework because: 1) they don't matter, and 2) we provide ways for you to make up for your mistakes.

There will be weekly assignments (11 total), 2 exams during the semester, and a final. The due dates and exam dates will all be posted on the course schedule. The assignments will be handed out, turned in, and graded via autolab. For most coding assignments we will have a suite of public tests that will provide you with feedback while completing the assignment and a suite of private tests that will be run after the submission deadline.

When calculating your assignment average we will pick your best 8 scores. The rest of your scores will not contribute to your score. We hope that you will use this flexibility to reduce your workload and have fun outside of class. In other words, there is no need for you to do all of the homeworks (but we encourage you to attempt all of them, as this is great way to drop homeworks you find more difficult than others).

As we give you some slack regarding homework, we may also choose to not grade certain questions or certain parts of each assignment (although we will grade the majority of your work). In such cases, everyone will receive a full score for the ungraded parts.

## Late Assignments

Homeworks are due at 11:59PM US Eastern Time unless otherwise indicated on the assignment or on Piazza (remember to check your email). Each assignment has a late submission deadline, which is typically (but not always) two days after the lab due date. Except in extraordinary circumstances (severe sickness with a doctor's note, etc), no late homework will be accepted beyond the late submission deadline.

You are permitted a budget of EIGHT late days per semester at no grade penalty. If you have used up these eight late days, your score will be reduced by 25% of the total points possible per extra late day used. Remember, you may not submit the homework (with or without late days) after the listed late submission deadline ("Last day to handin" on Autolab). Consider yourself warned.

We will not be able to grant you any additional late days for any reason other than a medical condition that seriously undermines your ability to do your work, by for example hospitalizing you for more than 5 day. Common cold, flu, etc are not sufficient. In case of a serious medical condition, please ask your academic adviser to email the professors. Please do not email us personally.

Handed in code will be graded for style and clarity on a pass/fail basis. You should refer to the style guide for general guidelines.

If your coding style on a particular homework assignment is sufficiently poor, then you will receive a score of 0 for the programming portion of that assignment. In order to restore your grade, you must:

• review the comments given on Autolab (which will detail why you failed style grading),

• rewrite your code for the lab (do not resubmit), making sure to address every comment, and

• If your new code is acceptable, the TA will change your style grade for the assignment to a "pass". Your original Autograded score will then be restored. It is very important that you do not attempt to resubmit any fixed code to Autolab. All submissions after the deadline are considered late and consume late days or points.

## 2 Week Cut-off

All issues regarding a given homework must be resolved within two weeks of the grades being released and announced (on Piazza). After the two week deadline, we will throw away unclaimed written feedback, and set the grades in stone. This means that if you need to contest a grade, fix a failed style grade (a zero on the coding portion!), or have any other problems regarding an assignment, you must come to the course staff within two weeks!

## Communication: E-mail, Piazza, This Website

When you need help from the course staff, please consider using piazza first (see piazza usage etiquette below). If piazza is not appropriate then you can email us at 15210-staff@lists.andrew.cmu.edu. Please refrain from emailing professors or individual TA's, except in cases that require privacy. Of course you are always welcome to office hours, or to ask the TAs or professor questions after class, time permitting.

We will post announcements, clarifications, corrections, hints, etc. on the course web site and piazza---please check them on a regular basis. When using Piazza we ask that you follow the following guidelines:

When to ask a question. Piazza is a great tool but it can create a temptation to ask every question that you may have, especially when you know that you will get a quick response. Resist that temptation as it is not good for your learning. To learn well and to learn how to think like a creative computer scientist, it is important that you give your mind the time it needs to learn. That means thinking about the questions by yourself on your own and doing the needed research on your own before seeking an answer. So in summary resist that temptation to ask as much as possible. This does not apply to certain questions. For example, a bug in the homework distribution that you just discovered should be posted as soon as possible.

Private versus public questions. It is important that you make your questions public rather than private because otherwise the course staff have to respond to the same question many times (private questions cannot be seen by your classsmates). Thus except in special circumstances (e.g. your post contains a hint to the solution of a homework problem), avoid using private questions. As a rule of thumb, if you don't feel comfortable making your question public, then it might not be an appropriate question for Piazza at all. For example, in general, posting a piece of code that you wrote and asking the TA's to correct it for you is not an appropriate question for Piazza.

## How to learn well

We would recommend: 1) taking notes (the physical action of taking notes often aids learning), 2) as you read the course notes, write down a list of questions and try to solve them, 3) develop a habit of formulating variants of exercises and homeworks that you are given and solving them and coming up with new questions, 4) think about and research the questions that you may have by yourself and try to find the answers on your own (for example for 24 hours), before talking to your friends and course staff. Of course, everyone learns in a different way, but if you feel that you are having trouble learning in this course, we will point you here first.

## Word of Caution

You will likely find this course to be difficult. There are several reasons why. First, the material covered in the course, with emphasis on parallelism, will be new to many of you. Second, the way we design our algorithms and implement them, with emphasis on higher-order programming (where functions are first-class values), can be difficult to grasp quickly, though over time you will likely not be able to imagine thinking without them. Third, this course will require generating your own algorithms in addition to understanding existing algorithms. If you don't know Standard ML, then there will also be the additional overhead of learning a new programming language, and you should start learning it immediately. There are many online resources for doing so.

It is thus important for you to mentally prepare yourself for a difficult course. If you do your work, we are confident that you will finish this class with a satisfactory grade. As you will discover throughout the semester, we have an excellent set of teaching assistants that can help great assistance. That said, you should keep in mind three things 1) there is no substitute for doing your own work, and 2) there is no substitute for doing your own work and 3) the first two things.

All students are expected to be familiar with, and to comply with, the University Policy on Cheating and Plagiarism.

Any work submitted as a homework assignment or examination must be entirely your own and may not be derived from the work of others, whether a published or unpublished source, the worldwide web, another student, other textbooks, materials from another course (including prior semesters of this course), or any other person or program. You may not copy, examine, or alter anyone else's homework assignment or computer program, or use a computer program to transcribe or otherwise modify or copy anyone else's files.

To facilitate cooperative learning, it is permissible to discuss a homework assignment with other students, provided that the following whiteboard policy is respected. A discussion may take place at the whiteboard (or using scrap paper, etc.), but no one is allowed to take notes or record the discussion of what is written on the board, and you must allow two hours to lapse after any discussion before working on the assignment. The fact that you can recreate the solution from memory is taken as proof that you actually understood it.

It is not acceptable to share your solutions or give hints to your friends for a lab after you have already discovered the correct idea. You are not helping your friends by doing so. The right thing to do is to not talk about the lab after you have a solution, and anyone struggling with the homework should visit office hours to talk to an instructor or TA. This shows the respect deserved by your friends as well as the people who have put a lot of effort into creating the labs.

In order to deter cheating we also run automatic code comparison programs (such as MOSS). These programs are very good at detecting similarity between code, even code that has been purposefully obfuscated. Such programs can compare a submitted assignment against all other submitted assignments, against all known previous solutions of a problem, etc. The signal-to-noise ratio of such comparisons is usually very distinctive, making it very clear what code is a student's original creative work and what code is merely transcribed from some other source. Often in previous semesters, however, we have discovered cheating due to the simple fact that the TAs are familiar with many different versions of the solution. Cheating is simply not worth the risk.

One final note: receiving credit for an assignment or exam is not an indication that we did not catch you cheating. Because dealing with cheating cases is a lot of work for the TA's and the instructors, we often delay enforcement until well into the second half of the semester and take action all at once, after we identified a number of cases. This usually leads to unfavorable outcomes for the students involved. Consequences for cheating may be as severe as failing this course and being reported to the Office of the Dean of Student Affairs.