CMSC858E, Models and Algorithms for Socio-Technical Networks, Spring 2011
Class Venue and Time: CSI 3118, 9:30-10:45AM Tue, Thu
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
Topics will include the following, with some possible modifications
based on class interest:
The class will also include presentations
and projects conducted by the students.
- the basics of graph theory, probability, and distributed algorithms;
- clustering, expansion & spectral approaches, random graphs &
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.
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
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
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
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
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
Homework 1, due February 15th.
Homework 2, due March 10th.
Homework 3 (ungraded).
Homework 4, due May 10th.
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
The CourseEvalUM (course evaluation)
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.