Spring 2003
CS 139: Concurrency in Computation



General Information

Time and Place
Mondays and Wednesdays, 10:30-12:00, 74 Jorgensen

Instructor
Alain Martin <alain@async> 294 Jorgensen

Teaching Assistant
Kevin Ko <kko@ugcs> VLSI Lab, Jorgensen
Office hours: Mon. 3:00PM-5:00PM, Tues. 4:00PM-5:00PM

Course Secretary
Betta Dawson <bettad@cs> 256 Jorgensen

System Managers
Dave LeBlanc <unix-help@cs> 272 Jorgensen
Chris Malek <unix-help@cs> 269 Jorgensen



Announcements
  • Homework 7 has been posted. I've also updated the "Lazy Stack" notes. (In lieu of solution sheets, I've been writing comments where necessary on graded assignments.) (28 May 2003)
  • Homework 6 has been posted. (21 May 2003)
  • Homework 5 will be posted this afternoon. It will contain one traditional problem as well as a programming component. Due date is two weeks from today. No class this coming Mon. or Weds. because Prof. Martin will be out of town for a conference. (07 May 2003)
  • No homework this week because of midterms. Next assignment out this coming Weds. Enjoy. (30 Apr 2003)
  • Homework 4 is posted. I will finish grading HW2 within a day or so, and I hope to have solution sheets ready in the near future. (23 Apr 2003)
  • Homework 2 is due at 12:00PM on Weds. April 16 because of the SFC. Please leave it in the CS139 box, which you may find in the VLSI lab near the telephone. (15 Apr 2003)
  • If you use TeX or LaTeX, you might find these files useful. (TeX users should be able to rename prs.sty to prs.tex.) (07 Apr 2003)
  • The homework distributed in class is valid. There was a miscommunication somewhere, and I (Kevin) take full blame. This should not happen again. (03 Apr 2003)
  • If you intend to take this course, please send an e-mail to Kevin containing your e-mail address. This will only be used to establish the class mailing list. (02 Apr 2003)

    • Homeworks
  • Homework 1 [CSP programs, Shared variables] (assigned 02 Apr 2003, due 09 Apr 2003)
  • Homework 2 [Mutual Exclusion] (assigned 09 Apr 2003, due 16 Apr 2003)
  • Homework 3 [The cigarette smokers] (assigned 16 Apr 2003, due 23 Apr 2003)
  • Homework 4 [Fair mutual exclusion from unfair semaphores] (assigned 23 Apr 2003, due 30 Apr 2003)
  • Homework 5 (notes/files) [Deadlock and Monitors] (assigned 07 May 2003, due 21 May 2003) - updated 5/17/2003
  • Homework 6 [Message Passing] (assigned 21 May 2003, due 28 May 2003)
  • Homework 7 [More Message Passing] (assigned 28 May 2003, due 04 Jun 2003 in the VLSI lab by 12:00PM)

    • Lectures and Handouts
    (Lecture scans may be from previous years)
  • Handout: Elementary Predicate Calculus
    		•  (31 Mar 2003) [pdf] [ps.gz]
  • Lecture 1: Semantics
    		•  (31 Mar 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 2: Concurrency
    		•  (02 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 2: Mutual Exclusion
    		•  (02 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 3: Dekker's Algorithm
    		•  (07 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 3: Peterson's Algorithm
    		•  (07 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 4a: Synchronization Primitives
    		•  (09 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lectures 4b and 5: Semaphores
    		•  (09 and 14 Apr 2003) [html/jpg]
  • Lectures 6 and 7: Dining Philosophers
    		•  (21 and 23 Apr 2003) [html/jpg]
  • Lecture 7: The Bridge Problem
    		•  (23 Apr 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lectures 8 and 9: Monitors
    		•  (28 and 30 Apr 2003) [pdf]
  • Lectures 9 and 10: Implementation
    		•  (30 Apr 2003 and 05 May 2003) [pdf]
  • Lectures 10 and 11: Distributed Programs
    		•  (05 and 07 May 2003) [pdf]
  • Lecture 11: The Lazy Stack
    		•  (07 May 2003) [pdf]
  • Lectures 12 and 13: A Distributed Path Algorithm
    		•  (19 and 21 May 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 13: Distributed Mutual Exclusion
    		•  (21 May 2003) [pdf] [ps.gz] [4.ps.gz]
  • Lecture 14: Deadlock
    		•  (28 May 2003) [pdf] [ps.gz] [4.ps.gz]



    Catalog Entry
    CS 139a. Concurrency in Computation.
    9 units (3-0-6); first term. Prerequisite: CS 20 or equivalent.
    Design and verification of concurrent algorithms. Topics: different models of concurrent computations; process synchronization by shared variables and synchronization primitives; distributed processes communicating by message exchange; the concepts of synchronization, indivisible actions, deadlock, and fairness; semantics and correctness proofs; implementation issues; and application to VLSI algorithm design. Parallel machine architecture issues include mapping a parallel algorithm on a network of processors, and classical parallel algorithms and their complexity.


    cs139@async.caltech.edu
    Last Modified: 28 May 2003.