CSE 592 Advanced Topics in Computer Science -- Propagation
Processes and Algorithms on Networks
Fall 2010
Section Information
Date: Mon-Wed
Time: 5:20pm-6:40pm
Room: 1306
Instructor Information
Instructor: Luis Ortiz
Email: le [last name] at cs followed
by .sunysb and finally .edu
Office: 2313-c
Phone: (631) 632-1805
Office Hours: 6:50pm-7:50pm M, 2:00pm-4:00pm Tu (or by appointment)
Course Description
The need to study and solve problems in complex systems, and
specially complex networks, has given rise to a variety of so called
computational ``network-based''
models. Despite the specific differences in the nature of the settings and
problems each model addresses, there is striking
commonality on some of the kinds of algorithms that have been
developed to solve the different problems. One such class of
algorithms is inherently based on so called propagation processes, in
which ``local information'' (with respect to the network graph) is
passed between nodes in the network with the ultimate goal of
achieving some ``global'' objective. Of course, the precise type of
information propagated depends highly
on the specific setting and problem, as are the notions of
``local'' and ``global.''
Propagation-based algorithms have had
tremendous practical success in areas such as near-optimal coding in
digital communication, planning, scheduling and other resource
allocation problems in AI, speech recognition, the analysis of digital circuits in electrical
engineering, the determination of protein structure in computational biology,
and stereo and image restoration in computer vision, to name a
few. The now widely famous PageRank algorithm, which is fundamental to
the way in which Google rank pages, also has an interpretation as a
propagation algorithm.
This course will cover the fundamental ideas behind propagation-type
processes and other similar algorithms that have been used to solve
problems in a wide variety of network-based models. There will be an emphasis on
highlighting and exploring commonalities between the different
propagation processes and algorithms among the different models. The
interest is on applying existing or developing novel propagation-based
algorithms to new domains. There is also interest in potentially
gaining or providing alternative insight into the behavior of
propagation algorithms (empirically and theoretically), and perhaps even
improving upon them.
Course Purpose and Objectives
- To introduce students to a variety of network-based models as used in different contexts and the problems they address
- To expose students to state-of-the-art propagation methods and
their applications in a variety of domains
- To prepare students for continuing research and development work in the area
Course Organization
The course format involves formal lectures, discussions and presentations, some led by the students themselves. Reading material from a variety of sources, including textbooks, tutorials, classical and recent research papers, and other possible web content, will be handed out, posted or assigned to supplement the lectures.
Course Project
Students complete a research project on a
relevant topic. The specific problem requires the instructor's
approval. Possible projects include, but are not limited to, an
application of a particular model and technique to a specific problem,
the development of a system based on network model ideas to solve a
particular problem for a particular application domain, or novel
experimental evaluations and comparisons of one or various propagation
techniques. Ideally, the project would incorporate a combination of theoretical and experimental work. Projects that involve exclusively theoretical work may be permitted only under very close consultation with the instructor and should involve a narrowly and clearly defined problem description and line-of-attack.
Students periodically submit progress reports to monitor
the project's development. Students give a presentation and submit a
written report on the results of the project by the end of the course.
Student Evaluations
Students performance will be evaluated based on their level of participation during the discussions, and the quality of their topic
oral presentation and written report, as well as their project's
proposal, progress reports, oral presentation and final written
report. There may also be sporadic written and/or code/implementation homework assignments (at the discretion of the instructor).
Tentative List of Topics
See syllabus for a tentative list of topics