# CSC 280: Computer Models and Limitations

## Spring 2011

Basic Course Information
Instructor: Professor Joel Seiferas
Workshop TAs: Frank Ferraro, Darcey Riley
Class Time: Mondays and Wednesdays, 3:25pm-4:40pm, CSB 601

Workshops: TBD

These workshops are optional but HIGHLY recommended. Their sole purpose is to help you better understand and master the material. One of the things that 280 helps to teach is that your peers can be of tremendous asset to you. To that end, these workshops are modeled after the official college-sponsored workshop program, so the main point behind them is to facilitate collaborative problem solving. However, these workshops are not affiliated with the college program, so the term "workshop" is somewhat of a misnomer. As a result, we are not restricted to the strict College workshop format; if the need arises, these sessions can easily become a Q&A session, or even more of a standard recitation. Regardless of the exact format, they will be motivated by you, and helped by the workshop TA.
Workshop Schedule
After every workshop, a brief outline of what was discussed will be posted. Generally, this will only be an outline (read: incomplete), intended to help those who cannot legitimately attend, or to serve as a refresher for those who did attend. If any interesting problems are discussed, the problems, hints, and/or solutions may be posted as well (most likely as PDFs).

27 January, 2011
• More closure properties
• Sketch of proof for pumping lemma (regular language):
• Every regular language has an equivalent DFA M
• M has finite number of states (by definition)
• Acceptance as a walk through a graph
• Pigeon-hole principle for all strings of a sufficient length: there must be a cycle in the walk
25 January, 2011
• More on the Pumping Lemma for Regular Languages
• L={0^n1^n | n \in \mathbb{N}}
• L={ww^R | w \in {0,1}*}
• Initial closure properties of regular languages
20 January, 2011
• Regular languages
• The Pumping Lemma for Regular Languages
• (Deterministic) automata
18 January, 2011
Notes (same as for 13 Jan.)

13 January, 2011
Notes
• Automata vs computational vs complexity theory
• Countable vs uncountable sets
• Decidable vs undecidable problems
• Halting problem and diagonalization
• Some simple proofs (contradiction, pigeon-hole principle, etc.)

Last change: 14 Jan 2011