# CSC 280: Computer Models and Limitations

## Spring 2011

**Instructor**:

Professor Joel Seiferas
**Workshop TAs**:

Frank
Ferraro, Darcey Riley

**Grading TAs**: Curtis Menton

**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.
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

Back to URCS Undergrad directory |

Back to URCS Home
Page