Announcements

  • Final Exam: Mon May 14, 5:30 — 8:30pm, GHC 4401 (Rashid). Practice final is now available. Review Session: Sunday May 13, 7pm also in GHC 4401.
  • Assignment 9 has been posted.
  • Assignment 8 has been posted.
  • Midterm II: Thu Apr 5, 7 — 8:20pm, WeH 7500. Practice midterm II is now available.

Overview

This course 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. The course, however, 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 significant more depth on algorithmic issues.

The concepts covered by this course include:

  • Problem vs. Algorithm: A problem defines an interface (e.g., sorting) while an algorithm defines a particular method to solve the problem (e.g., quicksort). Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components. We cover a variety of fundamental problems (sorting, minimum spanning tree, nearest neighbors, ...) and a variety of algorithms for solving them (quicksort, Dijkstra's algorithm, ...).
  • Asymptotic Analysis: Although the so-called big-O analysis is not going to accurately predict wall-clock time, it is critical for getting a rough estimate of the performance of an algorithm and helping guide algorithm design and selection. In the class, we analyze performance in terms of work, span and space. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and various counting arguments.
  • Techniques in Algorithm Design: There are just a few techniques that play the key role in the the design of most parallel/sequential algorithms and data structures. In this class, we cover these techniques, including using collections (sets, sequences, priority queues, ...), divide-and-conquer, contraction, the greedy method, balanced trees, hashing, sparse matrices, and dynamic programming.
The assignments use Standard ML (SML). We use Standard ML for several reasons, including: (1) it is safe for parallelism, (2) it properly supports higher-order functions, and (3) its module system does a good job of supporting abstract interfaces without confounding interfaces with state.

Course Information

Lectures:

Tue and Thu 12:00-1:20pm, WeH 7500

Recitations:

Section A - Wed 10:30-11:50, MM 103
Section B - Wed 11:30-21:20, PH A18B
Section C - Wed 12:30-1:20, WeH 5302
Section D - Wed 1:30-2:20, WeH 5302

Textbook:

There is no course textbook. Course notes will be provide instead. As we may not be able to cover all the material during lectures, please read the notes for additional background and further details.

Grading:

45% Assignments
30% Midterms
25% Final

Policy

Late Assignments

Homeworks are due at 11:59PM US Eastern Time unless otherwise noted on the assignment.

Your homework will be considered 1 day late if it is handed in within 24 hours after it is due and 2 days late if handed in within 48 hours after it is due. You are permitted a budget of FOUR (4) late days per semester at no grade penalty (e.g. you might use 2 on 1 assignment, and 1 each on two other assignments). At most TWO (2) late days may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not your score) per late day. Except in extraordinary circumstances, no late homework will be accepted beyond the late date.

Electronic devices during class

As research on learning shows, unexpected noises and movement automatically divert and capture people's attention, which means you are affecting everyone's learning experience if your cell phone, pager, laptop, etc. makes noise or is visually distracting during class.

For this reason, we ask you

  • to turn off the sound on your electronic devices, and
  • to sit in the back row if you plan to use your laptop.

Academic Integrity

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 or what is written on the board, and you must allow four 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.

We may sometimes 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.

Course Information

Lect: Tu, Th 12-1:20pm, WeH 7500
Sec A: Wed 10:30-11:50, MM 103, Bill Zorn
Sec B: Wed 11:30-21:20, PH A18B, Vincent Siao
Sec C: Wed 12:30-1:20, WeH 5302, Jonathan Paulson
Sec D: Wed 1:30-2:20, WeH 5302, Grant Strimel