CS 5234 - Combinatorial and Graph Algorithms
(Fall 2016)
NUS School of Computing
Prof. Seth Gilbert
Thursday 6:30pm - 9:30pm
COM1-0204
News
| October 16 | MiniProject group sign-up here. |
| October 16 | MiniProject information and project ideas here. |
| September 27 | I have added a section below contianins some potentially useful resources in learning the material covered in this class. |
| September 27 | I have updated many typos and mistakes in all the notes and problem set solutions. Thanks for all the help identifying typos. |
| September 13 | Problem Set 5 posted. Due: Sept. 29, after the break. I have also updated the notes on Sublinear Time Graph Algorithms. |
| August 29 | Problem Set 4 posted. Due: Sept. 12. Note that since this is a programming assignment, you have a few extra days to work on this problem set, but Problem Set 5 will be released next Friday as per the usual schedule. |
| August 29 | Notes from Week 4 posted. |
| August 29 | Week 4, ask me a question! HERE |
| August 29 | Updated location: COM1-0202, SR2. |
| August 29 | Solutions posted for problem sets 1 and 2. |
| August 26 | Problem set 3 posted, and lecture notes on Graph Sketches have been updated. |
| August 23 | Ask a question! Click here! (Update: Week 3 ask-a-question is over.) |
| August 23 | Updated another typo in problem set 2. Posted notes on graph sketches. |
| August 20 | Updated typo in problem set 2. |
| August 19 | Problem set 2 is posted (due next week, August 25). I have also updated the lecture notes from Week 1 (which also include material from Week 2). |
| August 12 | Problem set 1 is posted (due next week, Aug. 18). |
| August 12 | As discussed in class, I have posted a survey on IVLE that asks a few questions that will help me to understand your background. If you are planning to take the class, please fill out the survey! Don't spend a lot of time on it; the goal is to see what you know off the top of your head. |
| August 12 | Notes from Week 1 posted below. See the introduction for an overview to the class, including a discussion of problem sets, exams, etc. The notes on stream sampling are a first draft of the notes I put together for this class. (I will post updates as needed.) |
| August 11 | First class! Welcome to CS5234! |
Schedule
Below is the (very) tentative schedule for the course. I will modify the schedule as the course progresses. Problem sets will be posted below on this schedule as they become available.
| Class Number | Date | Description |
| Part 1: Sketches, Streams, and Graphs | ||
| 1 | 11/08 | Introduction and logistics. Sampling from a stream. Sketching a graph. |
| 2 | 18/08 | L0-Samplers and Graph Sketches |
| 3 | 25/08 | Graph sketches, connectivity, and minimum spanning trees. |
| 4 | 01/09 | Properties of your graph in less than linear time. |
| 5 | 8/09 | Finding the weight of an MST using sampling |
| 6 | 15/09 | Average degree, approximate diameter, and other properties of your graph. |
| Break | 22/09 | No class: Mid-semester break |
| Part 2: Efficient Algorithms for Modern Machines | ||
| 7 | 29/09 | Introduction to Caching |
| 8 | 6/10 | Mid-Term Exam |
| 9 | 13/10 | Caches and cache-efficient algorithms (Part 1) |
| 10 | 20/10 | Caches and cache-efficient algorithms (Part 2)
|
| 11 | 27/10 | Parallel algorithms (Part 1)
|
| 12 | 3/11 | Parallel algorithms (Part 2) |
| 13 | 10/11 | MiniProject presentations
|
| End of class | ||
| 14 | 28/11 | Final Exam (Morning)
|
Lectures notes
Throughout the semester, I have been producing notes of the lectures. These are divided into five different files, listed below. These are to be treated as "in progress" documents, rather than definitive reference resources. They may well contain bugs and mistakes (please let me know if/when you find such mistakes).- Sampling from a stream (pdf) [Download]
- Sketching a graph (pdf) [Download]
- Sublinear time graph algorithms (pdf) [Download]
- Cache-efficient algorithms (pdf) [Download]
- Parallel algorithms (pdf) [Download]
Miscellaneous Resources
Below you can find various resources that may help you with the material we are covering in this class.- At the beginning of the semester, I asked you to complete a short quiz covering material that I was assuming would be familiar to you from earlier classes. Thanks to Lim Wei Quan for preparing these solutions.
- Pre-Quiz Solutions
- MST proof details
- For a quick review of asymptotic notation:
- Brief Notes by TB Schardl (for an MIT undergraduate algorithms class).
- Lecture notes for the MIT undergraduate algorithms class on asymptotic notation.
- For more details, you might look at Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Chapter 3.
- For a review of some of the basic tools of randomized algorithms:
- Notes on Markov's Inequality, Chebychev's Inequality, and Chernoff Bounds.
- Recitation problems from the same class (above) on randomized algorithms.
- For notes on streaming algorithms, see the class by Jelani Nelson at Harvard. (Of particular note to this class, see the lectures on CountMin sketch and CountSketch and graph sketching.) There are also links to many other resources.
- For sublinear time algorithms, see the following classes:
- Sublinear Time Algorithms by Ronitt Rubinfeld.
- Sublinear Algorithms by Sofya Raskhodnikova.
- Czumac and and Sohler wrote a nice survey a few years ago on what is currently known about sublinear time algorithms.
- McGregor wrote a nice survey recently on the state of the art in streaming algorithms for graphs.
- Lars Arge is one of the world experts on cache-efficient algorithms. You can find notes from his class here. They cover several of the data structures we looked at. (It also includes some good references to interesting papers.)
- Erik Demaine wrote an interesting survey on cache-oblivious algorithms. You can find more recent details in his lectures notes: Lecture 7, Lecture 8, and Lecture 9 of his advanced algorithms class. (This includes details on the dynamic cache-oblivious search tree that we skipped.)
- Fork-join parallelism has been implemented in several languages. For example, see here for Java documentation. See CilkPlus for a C/C++ implementation (i.e., Intel's Cilk Plus).
- You can find a somewhat old set of notes on multithreaded progrmming here. While old, it contains most of the basic concepts we talked about. More recent lectures notes (in the same style): Lecture 1 and Lecture 2.
Course Overview
Description
The goal of this semester is to better understand how we deal with graphs (and datasets) that are very, very big. We will explore how to adapt classical algorithms, introducing a variety of tools for building efficient algorithms that can handle data at scale. As the semester progresses, we will encounter a variety of challenges:
- Scale: The problems are bigger. A graph with 1000 nodes is easy to deal with. A graph with one billion nodes is not. In many ways, this question of scale motivates much of what we are talking about this semester.
- Where is the data? The data is often not provided in a simple and accessible format. It may be distributed among different servers. It may be provided on-line as a stream of information. There may be noise in the dataset.
- Dynamic changes: The data is no longer static. For example, instead of working with a fixed, unchanging graph, the graph may change over time. It is no longer sufficient to simply solve a problem once.
- Context matters: The data comes from somewhere, and that matters. Does it represent a social network or a wireless network or a game? There are often special properties and structure of the data that you can leverage.
Imagine, for example, that you want to find a minimum spanning tree for a very large graph. Classical solutions like Prim's and Kruskal's may be difficult to implement efficiently if your graph contains one billion nodes! Can you find a faster randomized algorithm? Can you leverage special structure (e.g., is the graph planar, or derived from a social network) to derive a faster algorithm? Can you find an approximate solution faster? What if the graph is available only as a stream? What if the graph is changing over time with edges being added and removed (perhaps as friendships are made and broken). How does cache performance impact your algorithm? Can you take advantage of multicore machines to solve the problem faster? Maybe you could use a distributed cluster (or Hadoop)?
The goal this semester to develop a set of tools you can use to adapt graph algorithms these types of scenarios, when the graph is very large and you are no longer able to simply apply classical solutions.
Grading
Grades in the course will be based on problem sets (including a mini-project), a mid-term exam, and a final exam. In determining your final grade, these components will be combined as follows:
| Problem sets / Mini-project | 40% |
| Midterm | 25% |
| Final | 35% |
In the last month of the semester, you will have the chance to work on a small project that involves further exploring some of the ideas that we have covered during the class.
Course Logistics
Office Hours
For now, office hours are by apointment. Once the semester begins, I'll schedule regular weekly office hours (and update the website here).
Contact
To ask me small logistical questions, I prefer that you grab my attention immediately before or after class. For substantive content questions, schedule a meeting with me.
Problem Sets
There will be weekly problem sets in the first 2/3rds of the class. (I expect this will end up being 6-7 problem sets in total.) These problems sets will focus on algorithm questions: solving problems, devising algorithms, proving theorems. There may be a few short programming assignments.
Problems will be graded on a simplistic 0/1/2/3 scale: a 0 indicates minimal understanding (or a problem not completed); a 1 indicates some understanding but many mistakes or poor presentation; 2 indicates a satisfactory answer; a 3 indicates a perfect answer that goes beyond expectations. You should expect to get a 2 on most problems.
The following rules will help keep the problem set submission and grading process running smoothly:
- You must hand in a solution that is unique, consisting of your work alone. You may discuss high-level strategy with other students in the class. You may read the textbook, or other reference pages on general topics. However, the solution you hand in must be written by you alone, and any similarities to any other student's submission (or to any web page or solution on the web) will be considered cheating. It will be considered equally cheating whether you copy from someone else, or if someone else copies from you.
Do not compare or share your solution with others.
- You may not read or use solutions found on the web for identical problems, whether from prior years of this class or from other classes elsewhere.
- You may talk to people about general strategies, and you may use reference material available on the web (e.g., Wikipedia, lecture notes from other classes, etc.). If you talk to anyone else or read any reference material, you may not take notes on your discussion. Afterwards, spend half an hour on facebook (or some equivalent activity), before working further on the problem set.
- You are encouraged to typeset your problem sets (and are especially encouraged to use Latex). However, you may submit your problem sets in any form that is clear and easily legible. You are also encouraged to include many pictures and diagrams and examples in your problem sets. It is perfectly acceptable to typeset the problem set and attach hand-drawn figures.
- Problem sets should be handed in no later than the beginning of class on the day they are due. You may bring a physical copy of the problem set to class to give to me before the lecture begins, or you may submit it electronically on IVLE.
- Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (leave late problem sets in the envelope by my door). Beyond this point, problem sets will not be accepted.
Some advice on problem sets:
- Answers to homework should be written at a level suitable for and to address the instructor. In other words, don't put in long explanation for trivial things.
- You will be graded not only on the correctness and efficiency of your answers, but also on your clarity. Therefore, it pays to make your answers more concise and clearer. Understandability of the solution is as desirable as correctness. Sloppy answers will be at a disadvantage. Learn to make appropriate definitions to make your answers more precise and concise.
- Solutions do not have to be type-set, but they have to be neat and readable. Do not waste your time beautifying your answers. If you want to spend more time, you should spend it on improving its clarity, understandability, and other aspects of its technical content.
- From a previous module, you can find some advice on proofs here.
- From a previous module, you can find a sample of what a good solution looks like here.
Exams
There will be one two exams in the course: a midterm and a final. The mid-term exam will be held in class on October 6. The final exam will be held on November 28.
Academic Integrity
I take academic integrity seriously. To repeat the problem set instructions from above: the solutions you submit must be your own unique work. Any cases of cheating will be dealt with harshly: a first offense will result in at least a one letter grade deduction for the module (or potentially a zero for the entire module, depending on the severity). When in doubt, ask me what is allowed.