Home Page for CMSC858E Models and Algorithms for Socio-Technical Networks, Spring 2011

CMSC858E, Models and Algorithms for Socio-Technical Networks, Spring 2011

Instructor: Aravind Srinivasan
Class Venue and Time: CSI 3118, 9:30-10:45AM Tue, Thu

General Information

Course Overview:

Networks have come to play a fundamental role in our lives: these include the Internet, WWW, wireless, and social networks. This course will study models for such networks, algorithms for several fundamental problems in optimally developing and operating them, as well as interesting applications.

Topics will include the following, with some possible modifications based on class interest:

the basics of graph theory, probability, and distributed algorithms;
clustering, expansion & spectral approaches, random graphs & small-world networks, and routing in small-world & faulty P2P networks;
link-based approaches to Web search;
game theory, ad auctions, and markets & strategic interaction;
network dynamics; and
the confluence of wireless networking and social networks.

The class will also include presentations and projects conducted by the students.

This course will be valid for PhD qualifying coursework and MS Comps in the Algorithms and Theory area. The primary background needed will be undergraduate-level algorithms, and an interest in algorithms and related mathematics. Additional preparations will be developed in class, as well as given in the form of reading assignments.

There is no required textbook, but Networks, Crowds, and Markets: Reasoning About a Highly Connected World by Easley and Kleinberg is a highly-recommended supplementary book for networks, and Ryan O'Donnell's online book provides excellent background on probability.

Lecture Schedule:

Please click here for a schedule of the main topics covered in each lecture.

Office Hours:

Aravind's office hours will be in his office, AVW 3263, at 2:30-3:30PM on Thursdays and 10AM-12PM on Fridays. Please email Aravind to setup alternative times if you would like to come for some office hours but cannot make it at these times. Aravind will also hold additional office hours 10AM-12 noon on March 16th (one day before the mid-term).

Grading, Teams, and Exams:

The mid-term will be open-notes (you can bring your own notes), and will be held in class on Thursday, March 17th; all material covered up to (and including) March 10th is included for the mid-term. The final examination, according to the official university schedule, will be on Friday, May 13, 8-10AM. The final exam will cover all material covered in the course, and will also be open-notes.

Students will form teams of three each, with at most one of size two. The homework and project will be done collaboratively by each group. Grading: Homework 20%, Mid-term 20%, Project 30%, and Final 30%.

The projects will be presented by each team in class on May 3rd, 5th, and 10th, with each team getting 25 minutes total. In addition, a detailed writeup of at most 15 pages (excluding references) should be submitted by May 10th by each team. The content will be the main aspect of the writeup that will be evaluated (as opposed to the length).

Homework Assignments:

Homework 1, due February 15th.
Homework 2, due March 10th.
Homework 3 (ungraded).
Homework 4, due May 10th.

Additional Information

Students claiming a excused absence must apply in writing and furnish documentary support (such as from a health care professional who treated the student) for any assertion that the absence qualifies as an excused absence. The support should explicitly indicate the dates or times the student was incapacitated due to illness. Self-documentation of illness is not itself sufficient support to excuse the absence. The instructor is not under obligation to offer a substitute assignment or to give a student a make-up assessment unless the failure to perform was due to an excused absence. An excused absence for an individual typically does not translate into an extension for team deliverables on a project.

Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester.

The University of Maryland, College Park has a nationally recognized Code of Academic Integrity, administered by the Student Honor Council. This Code sets standards for academic integrity at Maryland for all undergraduate and graduate students. As a student you are responsible for upholding these standards for this course. It is very important for you to be aware of the consequences of cheating, fabrication, facilitation, and plagiarism. For more information on the Code of Academic Integrity or the Student Honor Council, please visit http://www.studenthonorcouncil.umd.edu/whatis.html.

The CourseEvalUM (course evaluation) website is open through Wednesday, May 11. You can submit confidential evaluations there and find the summarized results at the same location; also, the system does not identify to the instructor whether or not any individual submitted an evaluation. Course evaluation is an important part of making our courses better, and students are strongly encouraged to submit their evaluations.