Document URL: http://www.cs.arizona.edu/classes/cs473/fall09/
C SC/MATH 473
|
Automata, Grammars and Languages |
| Class Meetings: Real and Virtual |
This course is available in traditional lecture format, meeting twice
a week. It is also available for on-line registration. There is
an honors section that meets for an additional hour each week that is
available to traditional in-person student who are members of the Honors
Program. The choices are:
|
||||||||||||||||||||||||||||||||
| Web Page | The Web site for C SC473 is: www.cs.arizona.edu/classes/cs473/fall09. This document is the one you are reading now, and contains general information about the course, policies, notes, assignments, schedule information, etc. There is also a link to it on your D2L ``Course Home" page. | ||||||||||||||||||||||||||||||||
| D2L |
Please note:
Both the course Web page and the D2L pages for the course are accessible
to all students, whether in-person or on-line. It is worth familiarizing yourself with the D2L pages for this course. Changes will occur throughout
the semester, and you are expected to visit your ``Course Home" page
regularly.
|
||||||||||||||||||||||||||||||||
| About Video |
Lectures are not broadcast in real time. Instead lectures will be
recorded, processed and available for viewing through D2L a few hours after class.
These video recordings are available to both on-line and in-person students,
and will remain accessible for review throughout the semester.
Lectures will be available in two forms.
|
||||||||||||||||||||||||||||||||
| Prerequisite | C SC 345: Analysis of Discrete Structures is a mandatory prerequisite. Without 345 or an equivalent from elsewhere (typically entitled "Discrete Mathematics") the likelihood of success in this course is small. We will need specific material and facts from the prerequisite course, experience with mathematical techniques and methods of thought introduced there, and the ability to use standard language and notation. It is assumed you are familiar with the following topics: trees, graphs, elementary algorithm analysis, induction, recurrence relations, and combinatorics. | ||||||||||||||||||||||||||||||||
| Instructor | Peter J.
Downey
pete at cs dot arizona dot edu (520) 621-2207 Gould-Simpson 739 Office Hour: TR 12:00-1:15 or by email appointment. |
||||||||||||||||||||||||||||||||
| Teaching Assistants |
Qiyam Tung
Teaching Assistant qtung at cs dot arizona dot edu (520) 621-4089 Gould-Simpson 710B Office Hour: M 2:00-4:00; W 1:00-3:00 Carlos Rubio-Medrano Teaching Assistant cerubiom at cs dot arizona dot edu (520) 621-4089 Gould-Simpson 710A Office Hour: TR 3:30-5:30 Daniel T Mathis Videographer danielm at email dot arizona dot edu |
||||||||||||||||||||||||||||||||
| Communication |
|
||||||||||||||||||||||||||||||||
| Text |
Required:
Michael Sipser,
Introduction
to the Theory of Computation, 2nd Edition PWS Publishing, Boston, MA, 2006. ISBN 0-534-95097-3
|
||||||||||||||||||||||||||||||||
| Course Schedule |
Further University-wide calendar information can be found at: |
||||||||||||||||||||||||||||||||
| Course Description & Outline |
This course is an introduction to the fundamental models of computation
used throughout computer science: finite automata, pushdown automata, and
Turing machines. The hierarchical relationships among these models, their
relative power and limitations, and their variants are studied. Student
skills are developed in understanding and using rigorous definition and
proof to attack precisely formulated questions about computability and
computation. The only successful method known for learning these skills
is by working challenging problems, therefore, heavy emphasis is laid upon
student problem assignments. The course aims at improving students written
communication skills, and serves as a writing emphasis course.
The course explores models for and fundamental limitations of the computational
process. Proof techniques, major results and computing applications of the
results will all be stressed.
The material in this course is used in later, more advanced
computer science courses.
For example, regular expressions and context
free grammars are essential in the design of software such as compilers and
text processors; and closure properties and nondeterminism are needed to
explore inherent intractability (NP-complete problems).
Thus every effort is made to (1) motivate concepts with
example applications, (2) build a standard vocabulary
of concepts and techniques the student will later use frequently, and
(3) emphasize the algorithmic and constructive basis of the
proofs of results (e.g., regular expression to finite automaton conversion;
problem reductions).
Topics covered include: finite automata and regular expressions, turing machines,
properties of regular sets, Church's thesis, context-free grammars and
pushdown automata, decidable and Turing-recognizable sets, properties of
context-free languages, universal machines, parsing applications, undecidable
problems and reducibility.
|
||||||||||||||||||||||||||||||||
| Grading Policies |
Grades for this course will be based in the following items:
Each graded item, such as a homework or examination, is first awarded a raw score; raw scores vary with the number of questions, their difficulty, and their length. For each graded item, the raw score is then normalized to a ``traditional" scale in which 90 - 100 is an A, 80 - 89 is a B and 70 - 79 is a C. Both this normalized score and raw score appear on the report returned with each graded item. For each graded item, only the normalized score is recorded. The final cumulative course grade is computed as a weighted average of these normalized scores, using the weights described above. At the end of the course, the resulting weighted average is converted to a final letter grade using the ``traditional" scale. Decisions on whether borderline scores (such as 79) will be recorded as the next highest letter grade will be made using (a) performance on the final examination and (b) evidence of accomplishment in the subject that is cumulative over the term. The instructor reserves the right to fail for the course any student who fails the final comprehensive examination, irrespective of their earlier grades or their final weighted average. |
||||||||||||||||||||||||||||||||
| Other Policies |
Attendance is not enforced, but you are responsible for all material
covered in lecture or assigned as reading or homework.
Arriving late to class is rude and disruptive; if you cannot arrive on time, do not bother to come. Without prior arrangements with me, missed exams result in a grade of zero. Homework is due at the start time of class on the due date, using the D2L Dropbox Tool. Late homework is not accepted. (Homework submission times are recorded by the Dropbox Tool.) Exceptions to these deadline rules can be granted only in dire circumstances. If homework or exam grading seems incorrect, unfair or inconsistent, you may appeal for a re-grade. Prepare a brief memo that explains which problems are of concern to you, and why you think they should be reviewed. Submit your memo, and the original homework paper and grading sheet to the course TA or instructor during office hours, or during an appointment, and explain (and defend) your re-grading request. To obtain such a grade review, contact a member of the course staff for an appointment within 48 hours after the graded item was returned to you. After this 48 hour window, the grade will stand as originally awarded. If you do not obtain satisfaction on a grading appeal from your instructor, you have a right to appeal a grade to the Department Head, and thence to the Dean. For the procedure to be followed, see the University's website at Grade Appeal. All other academic policies of the University are adhered to in this course. A comprehensive list may be found by selecting ``Academic Policies" in the University of Arizona General Catalog 2009-10. It is assumed that: you have the prerequisites for this course, and their prerequisites, etc., recursively. The content of this syllabus is subject to change at the discretion of the instructor. |
||||||||||||||||||||||||||||||||
| Academic Integrity |
Assignments in this course require individual attention and effort to be of any benefit. All work is expected to be that of each student alone, without consultation with others, without reference to borrowed solutions and not the product of team efforts or collaboration with other authors. Plagiarism is the incorporation of someone else's words or ideas without proper attribution, whether taken from another student, an author, the instructor's published solutions or the Internet. Plagiarism constitutes theft of intellectual property, and those who engage in it will receive the failing grade of ``E''. These and other provisions are governed by the University's Code of Academic Integrity which applies to all those in this course. It is a violation of the Code to use another person's solutions as your own, whether those solutions are taken from a student in this course, taken from solutions obtained from an earlier offering of this course, taken from the files of a student who took this course earlier, or taken from the Internet. A Synopsis of the University Code of Academic Integrity is attached as part of this syllabus. The Department of Computer Science Course Policy on Collaboration contains some excellent advice, and is found at http://www.cs.arizona.edu/policies/collaboration.html A video entitled ``Academic Integrity Podcast" is available for viewing on the Dean of Students web page http://deanofstudents.arizona.edu. |
||||||||||||||||||||||||||||||||
| C SC Computer Account |
Obtaining a C SC Computer Account:
Computer accounts for C SC Department machines are available to any course registrant, either in-person or on-line. The account can be used on any machine in the Department's open labs, or through the Internet via ssh or other virtual terminal connection (e.g., PuTTY, iTerm). Read about obtaining such accounts at http://www.cs.arizona.edu/computing/accounts/accts-key.html. You can initialize or renew an account through the Web page: https://www.cs.arizona.edu/computing/services/account.html.
Login Name and Password:
Your initial password for C SC Department machines will be sent to your email.arizona.edu address at the beginning of the semester. For this reason, you must have an active email.arizona.edu account in order to receive a C SC account. When you log in to lectura.cs.arizona.edu for the first time you will be forced to change your initial password to a more secure password. See Rules for Acceptable Passwords for information on choosing strong passwords.
Access to Gould Simpson and Labs:
UPDATE:
Computer Science ID (CSID):
For any account problems, send email to lab@cs.arizona.edu. |
||||||||||||||||||||||||||||||||
| Accommodation |
Students with disabilities, who may require academic adjustments or reasonable accommodations in order to participate fully in course activities or to meet course requirements, must first register with the Disability Resource Center, 1540 E 2nd St, 621-3268, email drc@w3.arizona.edu, URL http://drc.arizona.edu. DRC staff will qualify students for services, and provide a letter to the instructor listing accommodations to be made. This letter should be submitted by the student directly to the instructor as soon as possible during the first week of classes. The student should meet as soon as possible with the instructor by appointment or during office hour to discuss accommodations and how course requirements and activities may impact the ability to fully participate in the course. |
||||||||||||||||||||||||||||||||
| Lecture Notes |
The lecture notes for this class, in PowerPoint form, are divided into about a dozen sections, each called a ``Discourse". PDF and PPT versions of these slides will be placed here in advance of the lecture that discusses them. On-line students should print a copy of the relevant Discourse for taking notes while running the screencast or video of the lectures. For in-person students, paper versions of these notes will also be passed out in class ahead of time.
|
||||||||||||||||||||||||||||||||
| Homework Standards |
All written work submitted for credit must be prepared using a program that produces typeset output with the appropriate type faces, symbols and notation used in the theory of computation (e.g., TeX, LaTeX, Word + Equation, etc). Figures can be rendered using a drawing tool like xfig, Word, paint, PowerPoint, etc. Do not submit scanned images of handwritten work. Rules for submitted work: Start each solution on a new page, repeat the problem statement, and number each page. Write concise and clear solutions, since failure to communicate clearly will cost points whether or not the conclusion is correct. Remember that this is a Writing Emphasis Course, and work will be graded in part on the quality of your writing, not just on its technical content. Submit answers electronically, before class time on the due date. Submit in PDF format only, using the D2L Dropbox Tool, accessible from your "Course Home" D2L page. All good writing is based upon revision. It is essential to revise your work before submission, and to consider whether your argument will be understandable to the reader. For example, it is never a waste of effort to explain the strategy you intend to use in a proof or construction, before beginning to present the work in technical detail. Think of the reader. Explain as if teaching a colleague in your class. Revise. Revise again. |
||||||||||||||||||||||||||||||||
| Homework Assignments |
Reading assignments need to be completed before the relevant lecture on the subjects covered. A schedule of readings from the text will be given here, and updated as the semester progresses.
Exams
|
Exams are administered in different ways, depending upon whether you are an
in-person or on-line student:
|
Information about forthcoming examinations (e.g., topics, example questions, rules for taking the exam) will appear here prior to the event.
|