CS 417-001 Introduction to the Theory of Computation

Spring 2011, 2:00PM - 3:15PM, EMS E190

Instructor: Adrian Dumitrescu

  • Syllabus
  • Office hours: Monday and Wednesday 4:00--5:00PM, or by appointment.
  • TA: Drew Onderko; e-mail: donderko@uwm.edu ; Office hours: Thursday 2:15pm - 3:45pm

    Assignments:

  • Homework 1 (due Feb. 7, 2011) Exercise 1.6(a, b, c, d, e, f, g, h)
    Other suggested exercises: 1.1, 1.4, 1.5

  • Homework 2 (due Feb. 16, 2011) Exercises 1.7(b, c, d, e, g, h), 1.14, 1.16(b)
    Other suggested exercises: 1.8(a), 1.9(a), 1.10(a)

  • Homework 3 (due Feb. 23, 2011) Exercises 1.18(a, b, c, d, e, f, g, h), 1.19(b, c), 1.21(a)
    Other suggested exercises: 1.20

  • Homework 4 (due Mar. 2, 2011) Exercises 1.29(b), 1.30, 2.4(b, c, e, f) and the next one:
    Use the pumping lemma to show that the following language over Sigma={a,b} is nonregular:
    {w | w contains fewer a's than b's}.
    Other suggested exercises: 2.1, 2.3, 2.6(a)

  • Homework 5 (due Mar. 28, 2011) Exercises 2.2, 2.9, 2.10, 2.26, 2.30(a)
    Other suggested exercises: 2.32

  • Homework 6 (due Apr. 6, 2011) Exercises 3.1(c), 3.2(b, d), 3.7, 3.8(b, c), 3.11

  • Homework 7 (due Apr. 13, 2011) Exercises 3.15(b,d,e), 3.21, 4.2, 4.3
    Other suggested exercises: 4.5

  • Homework 8 (due Apr. 20, 2011) Exercises 4.4, 4.6, 4.7, 4.8, 4.12
    Other suggested exercises: 4.9

  • Homework 9 (due May 4, 2011) Exercises 5.1, 5.2, 5.4, 5.17, 5.19
    Other suggested exercises: 5.3