CS 3100 -- Models of Computation -- Fall 2010

Table of Contents

1  Update history

2  General Course Info

3  FAQs

(faq URL) -- (faq.pdf)

4  HANDOUTS AND WEEKLY SCHEDULE

You are required to read the indicated chapters ahead of time, at least cursorily, to get an idea of what will be covered.

5  HANDIN Info

To hand-in assignments electronically use the 'handin' utility available in the CADE lab. To hand-in assignment one, type:

handin cs3100 asg1 <file>

where <file> is the actual assignment file. Typing handin cs3100 will list the assignments available for hand-in (currently only asg1).

WebHandin can also be used: See

https://webhandin.eng.utah.edu/

6  JFLAP Info

JFLAP is a free tool for experimenting with FA's. Download at:

http://www.cs.duke.edu/csed/jflap/

To run the jar file on linux from a shell type: java -jar JFLAP.jar

JFLAP is also available on CADE in /home/cs3100/jflap/bin/jflap. To use it put the directory /home/cs3100/jflap/bin in your path

(see

http://www.cade.utah.edu/index.php?module=faq&FAQ_op=view&FAQ_id=21

for info on how to do that).

Alternately, type  cs3100/jflap/bin/jflap. To be able to use JFLAP on CADE remotely connect with 'ssh -Y' (don't use the -X flag, it won't work well). Even so, it will be slow due to network delays. Your best bet is to be at the CADE lab or download your own JFLAP copy.

Other ways to connect remotely:

http://www.cade.utah.edu/index.php?module=faq&FAQ_op=viewFAQs&FAQ_cat=12.

Let us know if you have any questions about JFLAP.

7  Book

Required Textbook: ``Introducing the Theory of Computation,'' by Wayne Goddard, Jones and Bartlett, 2008

8  Learning Goals

This class is about the fundamental capabilities and ultimate limitations of computing devices (as described on Page 1 of our textbook by Goddard). It is designed to give you an appreciation for what computing devices can and cannot do. For a computer science student, knowing these absolute limits is as important as knowing the velocity of light or the lowest possible temperature is for a Physics student.

Making a light source brighter does not alter the fundamental limit of the speed of light any more than providing more memory or providing more CPUs alters the power of a computer. That said, there are distinct classes of computational devices that differ only in terms of their discipline of memory access. We shall study the following amazing facts in this course: We will be studying the types of tasks that these varieties of computers can carry out and what they cannot.

8.1  A real-world Turing machine

Lest you think that these machines are figments of one's imagination, a Turing machine can really be built! See
http://www.parallax.com/tabid/854/Default.aspx.
Of course, you may prefer to use a real laptop or desktop machine instead of this computer---although they are strictly equal in power! Unfortunately, we will not be constructing such computers in this class (!). Rather we will take a standard computer (equivalent to a Turing machine) and program it to follow the rules of finite-state or pushdown computers.

8.2  Computability and complexity

After appreciating the main characteristics of the three basic machine types,1we will be focusing our attention on two ideas; namely, computability, and complexity.
Computability:
What can Turing machines solve and what can they not solve?

Complexity:
How do we formally understand the class of ``solvable but hard'' problems called NP-hard and NP-complete problems? What do these problems tell about the design of algorithms for many important real-world problems?
While we won't study the topic of complexity a whole lot, the similarity of approaches to formalizing computability and complexity would serve as another affirmation that there is something fundamentally elegant about Turing machines.

8.3  How should you approach the subject?

In order to understand these ideas concretely, we must use the tools of Discrete Mathematics that you have studied in CS 2100 (or an equivalent class). We must learn to patiently construct mathematical proofs, and learn how to avoid flawed arguments---all reinforced by our assignments and exams (more on them later). This will be of primary emphasis throughout this course. Of course, we shall employ liberal doses of real-world examples and light-hearted analogies whenever possible.

It is quite easy to get discouraged by the ``pain of having to learn math.'' My advice is this:

9  Email

Our primary mode of communication with you is through email. Your email is supposed to be automatically included in cs3100@eng.utah.edu. The TAs will be sending a few test messages on the first day of classes. IT IS YOUR RESPONSIBILITY TO LET US KNOW by August 26th (second lecture) IN CASE YOU DID NOT RECEIVE THESE MESSAGES.

10  Grading

This class will have two midterm exams and a final exam---all closed book. The weightages are: The midterms will emphasize portions covered since the previous midterm (or the beginning of the course, in case of the first midterm). The final exam will emphasize portions covered after the second midterm. The final exam will also include higher level questions covering the whole course.

10.1  EXAM SCHEDULES

The exams will be on the following dates:
MIDTERM EXAM #1:
9/23 During class time -- subject to change with sufficient notice
MIDTERM EXAM #2:
11/16 During class time -- subject to change with sufficient notice
FINAL EXAM:
12/16 in class 10:30 to 12:30, as per http://www.sa.utah.edu/regist/calendar/finals/finExamSch.htm


10.2  Final Grade Calculation

After determining your individual scores, we will divide the class scores into percentile groups. Here is how the final grades will be assigned: 90th percentile and above : A; 83-89 : A-; 78-82 : B+; 75-77 : B; 72-74 : B-; 68-71 : C+; 65-67 : C; 62-64 : C-; 58-61 : D+; 55-57 : D; 52-54 : D-; and Below 52 : E.

10.3  Grade Lookup

The TAs will be assigning you a pass-code using which you can look up your grades. They will be sending you a website URL at which the grades will be available for lookup.

10.4  Assignment and Lecture Notes Postings

Assignments will be posted pretty much every week on Tuesdays (with exceptions that will be announced). You will see the assignment on the class webpage by Tuesday midnight (sometimes earlier). We will not be handing out hardcopy assignments in class. All assignments will be due in a week (i.e., Tuesday, by 10:30am (15 minutes before the lecture begins), unless otherwise indicated.

All lecture handouts and supplementary material will similarly appear online on the day of the lecture (with the exception perhaps on Lecture 1) and won't be distributed in hardcopy form.

10.5  How to submit?

Because of the very high overhead of typesetting your solutions, we strongly encourage handwritten solutions (so that you can focus most of your time on solving rather than typesetting).

Please drop off all assignment submissions by 10:35am of the due date---that is 10 minutes before the lecture begins. We will not accept assignments in class. The drop box is located near the School of Computing office, Room 3190 MEB. This is near the staircase that leads to the 3rd floor in the Merrill Engineering Building's North-West corner.

If you insist on typesetting, please make sure that the work is neat; we will not accept poorly typeset documents. You may submit these beautifully typeset documents through handin (instructions to do so will be mailed to you by the TAs).

If you hand-wrote an assignment but for some reason cannot come to class

10.6  LATE POLICY

11  Please Solve Assignments Yourselves!

We encourage high-level discussions amongst yourselves. However, discussing specific details pertaining to a problem constitutes cheating. We will have a zero-tolerance cheating policy enforcement amounting to failure in the course and referral to suitable authorities concerned with cheating. Allowing your work to be copied also constitutes cheating.

Since automata theory is taught universally and the number of favorite problems tends to be rather small, it is also possible to accidentally ``stumble into previous solutions.'' Even literally copying these solutions constitutes cheating. To earn points for your solutions, therefore, you must provide at least a few steps leading to the final answer. We don't want verbose documentation---but we can't accept cryptic answers without even one or two justifying sentences either.

12  Students with Disabilities

Reasonable accommodation will gladly be provided to the known disabilities of students in the class. Please let the instructor know the situation as soon as possible. If you wish to qualify for exemptions under the Americans with Disabilities Act (ADA), you should also notify the Center for Disabled Students Services, 160 Union Building.

13  Class Etiquette

To prevent disruption of class and to have an engaged class that is fully caught up, please try to follow these guidelines:
1
Linear Bounded Automata are like TMs except they allow only the input to be ``stomped over''---that is, overwritten. The rest of the tape is read-only. TMs can read/write anywhere. LBA are between PDAs and TMs in power.
This document was translated from LATEX by HEVEA.