CPSC 433: Formal Languages and Automata
Spring 2006


[Announcements] [Syllabus] [Calendar] [Culture Activities] [Useful Links]


Announcements

Back to beginning


Syllabus

Instructor: Prof. Jennifer Welch
Office: 415 H.R. Bright Bldg
Office Hours: Mondays 2:00 - 3:30 PM and Wednesdays 8:45 - 10:15 AM; other times by appointment (*updated on 1/25*)
Email: welch@cs.tamu.edu
Office Phone: 845-5820

Teaching Assistant: Mu-Fen Hsieh
Office: 329 H.R. Bright Bldg
Office Hours: Mondays, Wednesdays, Fridays 3:00 - 4:00 PM; other times by appointment.
Email: mufen@tamu.edu
Office Phone: 845-0269

Prerequisite: CPSC 311, Analysis of Algorithms.

Lecture: Tuesdays and Thursdays, 12:45 - 2:00 PM, HRBB 113.

Textbook: Introduction to Automata Theory, Languages and Computation, 2nd ed., Hopcroft, Motwani and Ullman, Addison Wesley, 2001.

Course URL: http://www.cs.tamu.edu/faculty/welch/teaching/433.s06


Course Goals: Course Content and Tentative Schedule: The course will cover the following topics.

week of topic reading
1/17 Introduction and Math Preliminaries Ch. 1
1/24 Finite Automata Ch. 2
1/31, 2/7 Regular Expressions and Languages Ch. 3
2/14 Properties of Regular Languages Ch. 4
2/21 Context-Free Grammars and Languages Ch. 5
2/28, 3/7 Push-Down Automata Ch. 6
3/14 SPRING BREAK .
3/21, 3/28 Properties of Context-Free Languages Ch. 7
4/4 Turing Machines Ch. 8
4/11 Undecidability Ch. 9
4/18, 4/25 NP-Completeness Ch. 10

Assignments and Grading: All assignments will be announced in class and posted on the web page calendar. If you miss class for any reason, it is your responsibility to find out what assignments you missed.

Your grade will be based on four components:

No late assignments will be accepted. There will be no make-up exams except for university-excused absences. Please discuss unusual circumstances in advance with the instructor.

Course grades will be assigned according to this scale:

percent of total points 90-100 80-89 70-79 60-69 < 60
letter grade A B C D F

Collaboration: For the assignments in this class, discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used.

Americans with Disabilities Act (ADA) Policy Statement: The Americans with Disabilities Act (ADA) is a federal antidiscrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.

Back to beginning


Calendar

This calendar lists all due dates as they become known for Follow the links to get

Monday Tuesday Wednesday Thursday Friday
1/16
MLK Holiday
1/17
Introduction
1/18
1/19
DFAs
Read Chs 1 and 2
Quiz 1
1/20
1/23
1/24
NFAs; Conversion from NFA to DFA
Quiz 2
1/25
1/26
More Conversion; Regular Expressions
Read Ch 3
Culture 1 due
1/27
1/30
1/31
Conversions Between Regular Expressions and NFAs
Quiz 3
HW 1 due
2/1
2/2
Pumping Lemma for Regular Languages
Read Ch 4
2/3
2/6
2/7
More Pumping Lemma; Properties of Regular Languages
Quiz 4 2/8
2/9
More Properties of Regular Languages; Context-Free Grammars
Read Ch 5
2/10

Monday Tuesday Wednesday Thursday Friday
2/13
2/14
Chomsky Normal Form
Read Ch 7, Sec 1
Quiz 5
HW 2 due
2/15
2/16
More Chomsky Normal Form
Culture 2 due
2/17
2/20
2/21
Review
HW 3 due
2/22
2/23
Exam 1
2/24
2/27
2/28
Push-Down Automata
Read Ch 7
3/1
3/2
PDAs and CFGs
Quiz 6
3/3
3/6
DLS: Jamieson
3/7
Pumping Lemma for CFLs
Quiz 7
3/8
3/9
Pumping Lemma for CFLs
Culture 3 due
3/10
3/13
SPRING BREAK
3/14
SPRING BREAK
3/15
SPRING BREAK
3/16
SPRING BREAK
3/17
SPRING BREAK

Monday Tuesday Wednesday Thursday Friday
3/20
3/21
Properties of CFLs
Quiz 8
HW 4 due
3/22
3/23
Turing Machines
Read Ch 8
3/24
3/27
3/28
TMs and Church-Turing Thesis
Read Ch 9
Quiz 9
3/29
3/30
Undecidability; A Non-RE Language
Culture 4 due
3/31
4/3
4/4
Review
HW 5 due
4/5
4/6
Exam 2
4/7
4/10
4/11
A Non-Recursive Language
Quiz 10
4/12
4/13
Rice's Theorem
4/14
READING DAY - NO CLASSES

Monday Tuesday Wednesday Thursday Friday
4/17
4/18
P and NP
Program 2 (part of HW 5) due (extended)
Quiz 11
Read Ch 10
4/19
4/20
NP-Completeness
Culture 5 due
4/21
4/24
4/25
More NP-Completeness
Quiz 12
4/26
4/27
Review
HW 6 due
4/28
5/1
5/2
FRI CLASSES MEET
5/3
READING DAY
5/4
READING DAY
5/5
5/8
5/9
5/10
FINAL EXAM 8:00 - 10:00 AM
5/11
5/12

Back to beginning


Culture Activities

There is a lot more to Computer Science than you will be exposed to through your normal coursework. The purpose of the CS culture activities is to give you an opportunity to learn about current trends in computing. Keeping up with industry trends and learning to evaluate critically what you read are valuable professional skills.

You are to find, read, and write short reports on three technical papers in computer science journals. Articles in the following two journals are usually at about the right level:

Both are in the library; if you click on the journal titles, you will get to the ACM and IEEE Computer Society digital libraries respectively (if you are behind the TAMU firewall). Each article must have been published after Jan 1, 2006.

Each report is to be one to two pages long, typed, and must include

For two of the culture reports, you will have the opportunity to attend a lecture and write up a short report (including cover sheet, title of talk, name and affiliation of speaker, date of talk, summary of talk, and at least one comment or question as for the journal paper reports). These opportunities Distinguished Lecturer Series. If you have a schedule conflict with the lectures, you may substitute a report on a journal article written by the distinguished lecturer.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See academic integrity policy in the syllabus.

Here are some tips for getting full credit on your reports.

Distinguished Lecture dates and report due dates are indicated in the calendar and reproduced here for convenience:

Back to beginning


Useful Links

Course-Related

Computing-Related at TAMU

Careers and Mentoring

Back to beginning