CMPT 706 - Algorithms for Big Data - Spring'19

Instructor | Times & dates | Homeworks & midterm | Lectures

Announcements

Office hours to review the final exam: Wednesday April 17, 9:30am-12:00pm
Final Exam
When: Tuesday, April 16, 9:00 - 10:30am
Where: AQ3181
Duration: 1.5 hours
What's included: `theory' questions (definitions, theorems, algorithms, etc.) on all subjects studied in the
course except large graphs processing
Problems to solve: Similar to HW1 - HW5, and those in quizes
More you can learn from a sample final exam posted on the course webpage.
What do you need to have with you?: Only a pen or pencil. No pocket calculators or cell phones.
Office Hours: Sunday Apr 14, 9:00am - 11:00am
Monday Apr 15, 10:00am-2:30pm
I mistakenly posted online a wrong version of HW5 (it's different in problem 3). We will count solutions to both versions.
Quiz 5 will be on Dynamic Programming (Lectures 17-18)
I will be away in the week starting March 11. Dr Joseph Peters will substitute for me
Due to various delays the deadline for Homework 3 is changed to March 7
Due to various delays the schedule for homeworks and quizzes has changed, see below
Due to cancellation of classes today, February 12, Quiz 2 will be Thursday, February 14 at the usual time
There was a typo in problem 1 of Homework 1: in the second line of the algorithm, the range of the second `for' loop should
be i+1 to n,rather than from i+1 to j. The online version is now fixed. Sorry for inconvenience.
On Wednesday Jan 16 we have our first discussion session. We will discuss some concrete and more general questions related
to the current topic. I hope to keep the discussion as free and open as possible, with some moderation by the TAs. Questions
for the first session are posted, see below. Please read them and try to think of any ideas you may have concerning them.
Here I explain how you should solve and submit the first homework.
- Solving.
  Solutions to the homeworks must be your own. It does not mean that you cannot solve them with your friends, this means that
  you have to write solutions on your own, avoiding copying and consulting. This is what the university policy requires.
  
  There are no specific requirements for formatting solutions, title pages and so on. Use your common sense to make sure your
  writing and your solutions are clear and understandable. Don't forget to indicate your name, student ID, and assignment number
  on the first page.
- Handing in. There are 3 ways to hand in your work.
  
  1. You can bring it to the class on the due day, and put it on my desk BEFORE THE CLASS. 70% of people usually do that.
  
  2. You can slide under my office door.
  
  3. You can use the CS Course Management System to upload the solution: https://courses.cs.sfu.ca/ and follow the instructions.
  You can upload a pdf of MS Word document, there are two components of the submission, you have to use only one of them
  depending on the type of the file you have.
- Deadline: The moment I step into my office after the class on the due day. All works handed in after this moment will be
  considered as late submission. There is absolutely no submission after I post solutions. This will normally happens a day or two
  after the due day.
Course information handout:
Course Texts: "Algorithms", S. Dasgupta, C. Papadimitriou, U. Vazirani, McGraw-Hill Higher Education, 2008, 9780073523408.
An e-text version is available: ISBN 9780077245139
Errata for the textbook

References:
- "Algorithm Design" by Jon Kleinberg and Eva Tardos, Addison Wesley, 2005
- "Introduction to Algorithms" by T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw Hill, MIT Press
- "The Art of Computer Programming. Vol. 1,2,3,4" by D. E. Knuth, Addison Wesley
- "Concrete Mathematics" by R. L. Graham; D. E. Knuth; and O. Patashnik, Addison-Wesley, 1994
Instructor: Andrei Bulatov (abulatov@sfu.ca), Office: TASC 8013
TA:
- Amirhossein Mozafari Khameneh, email: amozafar@sfu.ca
- Akbar Rafiey, email: arafiey@sfu.ca
Where and When
- Lectures:
  - TuTh 13:00-14:20 in AQ 3150
- Discussion Sessions:
  We (biweekly) 10:00-11:30 TASC 9204 (W), starting Jan 16
- Tutorials:
  We (biweekly) 10:00-11:30 TASC 9204 (W), starting Jan 23
- Office Hours by Instructor: Mo 13:00-14:30 (starting from Jan. 7th) and Th 11:30-12:30 in TASC 8013 (or by appointment).
- Office Hours by TAs: Tu 9:00-10:00 in ASB 9808
Important dates (TENTATIVE)
- Assignments due:
  - Assignment 1 is due Thursday, January 24.
  - Assignment 2 is due Thursday, February 7.
  - Assignment 3 is due Thursday, ~~February 28~~ March 7.
  - Assignment 4 is due Thursday, ~~March 14~~, March 21.
  - Assignment 5 is due Thursday, March 28.
- Quizzes:
  - Tuesday, January 29, regular time 13:00 - 14:20, regular room, AQ 3150
  - ~~Tuesday, February 12,~~ Thursday, February 14, regular time 13:00 - 14:20, regular room, AQ 3150
  - Tuesday, ~~March 5~~, March 12, regular time 13:00 - 14:20, regular room, AQ 3150
  - Tuesday, ~~March 19~~, March 26, regular time 13:00 - 14:20, regular room, AQ 3150
  - Tuesday, April 2 regular time 13:00 - 14:20, regular room, AQ 3150
- Final exam:
  - Tuesday, April 16, 9:00-10:30am, room AQ 3181
Homeworks and Midterms
Lectures
I will post slides I use in class.
Relevant Links
- Large Graphs Processing
  - Google's Pregel framework for large scale graph processing. A video presentation is available here:
    https://www.youtube.com/watch?v=yX_zJyNbpac
  - GraphChi: Large-Scale Graph Computation on Just a PC (vertex-centric approach using preprocessing to produce shards).
    The conference paper, presentation video, and presentation slides are all available on this web page:
    https://www.usenix.org/conference/osdi12/technical-sessions/presentation/kyrola
  - X-Stream: Edge-centric Graph Processing using Streaming Partitions (edge-centricscatter-gather approach with no preprocessing).
    The conference paper is here: http://sigops.org/sosp/sosp13/papers/p472-roy.pdf and the video presentation is here:
    https://www.youtube.com/watch?v=3YkpUEnLW4s&index=30&list=PLn0nrSd4xjjZsNjpfWvNE
- Some basic graph algorithms implemented with Pregel can be found here and here
- The Ethernet protocol. Find our algorithm in this description.
- Paxos consensus

CMPT 706 - Algorithms for Big Data - Spring'19

Announcements

Where and When

Important dates (TENTATIVE)

Homeworks and Midterms

Lectures

Relevant Links