Computer Science 746
Discrete State Stochastic Models
Spring 2003

Instructor: Gianfranco Ciardo       (757) 221-3478       ciardo@cs.wm.edu       http://www.cs.wm.edu/~ciardo/

Textbook: None (some class notes and research papers will be distributed during the semester)

Office hours: Wednesdays 9:00 a.m. - 11:00 a.m. and Thursdays, 1:30 p.m. - 3:30 p.m., McGlothlin-Street Hall 117

Class meetings: Tuesdays and Thursdays, 11:00 a.m. - 12:20 p.m., McGlothlin-Street Hall 104

Final project due: Monday, May 5, 4:30 p.m.

Prerequisites: CSci 616 or equivalent

This course explores the logic, performance, and reliability analysis of discrete-state systems, with an emphasis on "exact" analytical/numerical approaches (as opposed to simulation). The course covers three main aspects:

Formal specification of a system model:

• The state space of a model.
• Logic, timed, and probabilistic models.
• Commonly used description formalisms: automata, Petri nets, queueing networks, task graphs, ad-hoc languages.
• Temporal logics.
• Stochastic processes: continuous and discrete time Markov chains, semi-Markov and Markov regenerative processes.

Model solution algorithms:

• Explicit and implicit techniques for state space generation and exploration.
• Numerical solution algorithms for ergodic or absorbing Markov chains.
• Matrix-geometric solution (possibly).
• Product-form solution (possibly).
• Approximate analysis of large models: state-space truncation, decomposition, interpolation (possibly).

Practice:

• Implementation and use of modeling packages.
• Modeling applications meaningful to computer science.

Coursework

Homeworks will be assigned during the course (50% of the grade). These are to be done individually, with no collaboration. If you foresee having to turn in an assignment after its due date for justifiable reasons (such as an illness), it is fundamental that you let me know as soon as you can, and certainly before the deadline. Sending me e-mail or coming in person to my office are the best ways to do so.

Classic papers from the literature will be assigned weekly throughout the course. Each student must carefully read the papers and be ready to present them in class (10% of the grade).

Instead of a final in-class examination, students will work on a research project which will be due on the day of the final (40% of the grade).

The choice of the topic for the final project must be discussed with the instructor. It is wise to make this choices as early as possible, and certainly by mid-semester.

This is an advanced graduate course. While class participation is not given an explicit weight in the overall grade, it is essential that each student actively participates in the classroom meetings.

Grading policy

If your overall grade amounts to x%, your grade for the course will be determined as follows:

x between 0 and 57 : F

x between 57 and 60 : D-

x between 60 and 63 : D

x between 63 and 67 : D+

x between 67 and 70 : C-

x between 70 and 73 : C

x between 73 and 77 : C+

x between 77 and 80 : B-

x between 80 and 83 : B

x between 83 and 87 : B+

x between 87 and 90 : A-

x at least 90 : A

Students with disabilities

If you have a disability that may affect your participation in this course and wish to discuss academic accommodations, please contact me as soon as possible.