CISC5835, Algorithms for Big Data,
Fall 2018



  & Notes



Overview: The first part this course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. We study the general techniques for algorithm design (e.g., divide-and-conquer, dynamic programming, graph algorithms), as well as specific algorithms for specific problems (e.g., sorting, searching, polynomial and matrix calculations). Issues of intractability, i.e., a discussion of the classes P (problems solvable in polynomial time) and NP (problems for which a conjectured solution can checked in polynomial time), issues of NP-completeness and the famous open problem of whether P=NP or not are introduced in the course. The second part of class covers specialized algorithms for handling big data, including algorithms that operate in a single pass of the data, algorithms for streaming data, and massively parallel algorithms.

Prerequisites: CISC2200, and CISC2100/CISC2110 or equivalent

Instructor: Xiaolan Zhang
       Department of Computer and Information Science

Lecture: Tuesday 5:30-7:45pm
Office hours: Tue 2:30-4pm LL610F (LC), Wed/Thurs 1:00-2:15pm JMH340A (RH), or by appointment
TA: Liao He (lhe44 at, Office hour: Tue 3-5pm LL601 (LC), Tuesday

Course Materials:

  • Reference textbook:
    • T. Cormen, C.E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press (Referred to as CLR)
    • Dasgupta et al., Algorithms (McGraw-Hill, 2006). (Referred to as DPV)
  • Assigned readings from the reference textbooks.
  • Class Notes: Class notes (highly recommended) are posted on the class website. I suggest you print them out and bring them to class.