CSCI 250 (GOLDWEBER)
Spring 08: 1/14/08
Languages and Automata
CSCI 250
Instructor: Michael Goldweber
Office: 134 Hinkle, 745-3936 email: mikeyg@cs.xu.edu home page: http://www.cs.xu.edu/~mikeyg
Office hours: Tuesdays through Fridays from 2:00-3:00, or by appointment. See http://www.cs.xu.edu/~mikeyg/schedule08s.html for my schedule this semester.
Course Home Page: http://www.cs.xu.edu/csci250/08s/
Schedule: Lectures are Mondays, Wednesdays, and Fridays at 11:30-12:20 in Alter 214.
Required Text: Kinber and Smith, Theory of Computing: A Gentle Introduction, Prentice Hall, 2001.
Additional readings as assigned.
Prerequisites: CSCI 180 (CS 2) and MATH 180 (Discrete Mathematics). CSCI 220 (CS 3) is recommended.
Required Work: In addition to regular attendance of the lectures and staying current with the assigned reading there will be weekly homework assignments. Most of these assignments will be traditional paper and pencil style assignments.
Hopefully, there will be some exceptions to this. In particular, if time allows at the end of the semester, there will be the Major Theorem Assignment; a one-on-one session where you give an intuitive explanation of why one of the major theorems studied this semester is true. Furthermore, you will demonstrate its use in solving a problem. Additionally there is the Modeling Assignment; an in-class presentation of a real-world problem/artifact that can be analyzed using one of the models of computations studied during the semester.
All assignments will be due at the beginning of class time on the announced due date, AND WILL BE COLLECTED AT THE BEGINNING OF CLASS. No late work will be accepted. It is recommended that you submit your best work on time than to give an answer to all the problems. If you cannot solve a problem you should indicate as such and also provide some statement of what your ideas were, where you got stuck, and where you were hoping to take your ideas to.
Exams: There will be 2 non-cumulative midterm exams in addition to the cumulative final exam. Furthermore, there may be 2-3 quizzes throughout the semester. The dates for the two exams will be announced approx. 2 weeks in advance. The final exam is scheduled for Wednesday May 7 in the morning (10:30-12:20). Use this date to make your travel plans accordingly.
Attendance and Classroom Participation: While there is no formal attendance policy, you are expected to arrive prepared to ALL (approximately 41) course sessions. Furthermore you are expected to participate in the classroom discussions and activities to the best of your abilities. Given the difficult nature of the material and the interactive lecturing approach that will be used, it is difficult to envision a student missing and/or arriving unprepared to a number of the class sessions and still succeed in the course.
Grading: Grades on all assigned work will be based on correctness, clarity and style. Your grade will be based on the following
The Department of Computer Science and Mathematics has adopted the following grading standards:
Plus/minus modifiers on grades will be used solely at the instructor's discretion. In cases where the instructor believes the plus/minus modifiers help give a more honest and accurate assessment, they will be used.
A more detailed explanation can be found at http://www.cs.xu.edu/~mikeyg/gradingStandards.html.
Exceptions to the Rules: Almost all rules are designed to be broken under the correct set of extraordinary circumstances. It is strongly recommended that you communicate to the instructor at the earliest possible time any circumstances you feel warrant an exception (e.g. illness, religious holiday, personal and/or family crisis, etc.). Remember that going into hiding is probably the worst strategy you can adopt! There is a direct relationship between the amount of sympathy you can anticipate from an instructor and the amount of time remaining until a given assignment's due-date. Finally, remember that if you are uncomfortable discussing something directly with an instructor (e.g. personal problems) you can always contact someone in the Dean of Students Office and have that individual contact the instructor.
Course Objectives: Theoretical computer science is the mathematical study of models of computation. Instead of studying the capabilities of a specific machine architecture we will study the capabilities of various abstract machines. Three different abstract machines in particular; finite automata, pushdown automata, and Turing machines. We will examine how the limits of what these abstract machine can compute relates to what a real computer can compute. Along the way we will try to formalize mathematically the definition of an algorithm. Finally we will study a method of classifying problems according to their inherent complexity (complexity theory), and discover that there exist some problems that are unsolvable.
Honor Code: All work submitted must be your own. You are strongly encouraged to discuss the homework with your classmates or with the instructor, but you must work out, write up, create, or program your own solutions. Work you hand in must be conceived, created, and fully understood by you. The best way to ensure this is to craft your solutions/answers/programs when you are by yourself rather than during your discussions with others. This will insure that your work is based on your own understanding rather than on that of your classmates. To do otherwise is a violation of the college's policy on academic honesty and will be handled accordingly. Please refer to the rules described in the Student Handbook.
I encourage you to follow these two guidelines, stated on many course websites, but perhaps originating most recently at Duke University.
Remember, un-noted collaboration or any form of cheating will need to be dealt with harshly to protect the integrity of everyone involved.
Always remember:
Don't Panic


File translated from TEX by TTH, version 3.74.
On 10 Jan 2008, 14:31.