Lecturer:
Prof. E. G. Coffman, Jr.
Office hours: Monday 10:00 am
to 12:00 pm by appointment.
Most other days will be available as
well, including weekends.
Office: 813 Schapiro (CEPSR) Bldg.
Phone: (212) 854-2152 (office) (212) 316-9038
(home)
Email: [email protected]
URL: http://www.ee.columbia.edu/~egc
Time: Tuesdays, 6:10-8:00pm
Room: Engineering Terrace 386
Syllabus: The syllabus can be found in Syllabus.ps
Notes: Math foundations can be found in notes.ps which is
a version of
a set of notes compiled by Philippe Nain. The course notes will
be supplemented by
many applications worked out in class. Applications will
be accumulated in the
file Applications.ps
Scheduling items: On Mar. 9th, we will have a midterm.
By Feb 24th, you must have a two-page proposal for a research project.
You may combine with one other person.
Course structure:
There will be a mid-term, a final, and a research
project. Students may be
asked to give talks on their results. Homework assignments will
be given out
on a regular basis and maintained in Problems.ps
. Problems in the Applications
file
are to be done right after the applications have been discussed in class.
Review of course progress and preview of next week
Week 1: Probability refresher, with
elementary combinatorics/counting
Week 2: More probability,
generating samples from a given distribution,
Poisson process, common distributions,
limit theorems, inequalities
Week 3: Analysis of interleaved memory systems; expected value arguments,
Poisson processes in two dimensions (polling model)
Homework assignment: 2,3,4,5 from problem set.
Week 4: Markov chains, expected value arguments, Little's theorem,
carried
load = offered load. The M/G/1 queue (for notes on the calculation
of the generating function see MG1.pdf )
Week 5: Birth
and death processes, analysis of the single server processor
sharing queue. Proposals for projects due.
Week 6: Birth and death processes continued. Models and problems
of
fault tolerant computing. Models of disk head motion.
Week 7: Return to continuous polling systems with a brief discussion
of
continuous state-space Markov chains. Expected value argument
for finding mean busy period durations. General approach to
finding the transform of the busy period distribution.
Do problems 10,11,12,13 from the problem set to hand in 3/23
Week 8: Midterm to
be administered by Teddy. You will be able to
take the midterm home to work on it, but it must be handed
in within 24 hours. (Put in my mail box or under my office
door.
Week 9: Semester break
Week10: Priority queues, foreground-background service disciplines,
brief review of midterm. Please set up appointment to
discuss
progress on the project.