Instructor:

Dr. Jane Ingram

Office Hours:

Mon, Wed: 2:15 - 3:30 pm

Office:

365-A Trexler

Tu, Th: 9:30 - 10:30 pm

Phone:

375-2446

Also by appointment or drop in

E-Mail:

ingram@roanoke.edu

Course Web Page:

http://cs.roanoke.edu/Fall2011/CPSC390A

Course Objectives: This course is designed to give the student a basic understanding of the theoretical foundations of computer science. At the end of the course the student should have an understanding of formal models of computation from automata theory and their relationship to formal languages. Topics include formal languages, automata theory, Turing machines, undecidability, and an introduction to complexity theory.

Intended Learning Outcomes: At the end of the course the successful student will be able to

1. define finite state automata, pushdown automata, and Turing machines, describe the computational power of each, and describe the relationship to formal languages;
2. construct the appropriate automaton to prove a language is a given type;
3. given an automaton determine the language it accepts;
4. construct a proof that a given language is not a given type (e.g. regular);
5. prove that a given problem is Turing computable by constructing a Turing machine;
6. describe the idea of undecidability and prove a problem is undecidable;
7. construct a program to simulate a given automata or recognize a given language.

Prerequisites: CPSC 170

Text: Introduction to the Theory of Computation, 2^nd Edition, by Michael Sipser, Course Technology, 2006.

Attendance Policy: Attendance is a very important factor in the student's success in this course. Each student is expected to attend every class and is accountable for any missed classes.

Grading Policy: The course grade will be based on 2 tests (part may be take-home), homework assignments, programming assignments, three co-curricular activities, and a comprehensive final examination. The course grade is determined using the following weights:

Make-up Policy: Everyone is expected to take tests and the exam at the scheduled time. Make-ups will be given only for legitimate, documented absences that the instructor has been notified of ahead of time. Make-up tests, if given, may be oral.

Homework: The best way to learn the theoretical, mathematical material in this course is to do it on a regular basis. Consequently there will be homework problems assigned every class period that will be turned in and graded. These problems are due at the beginning of class on the due date (which will often be the next class period after they are assigned). For some designated problems (primarily those that are theoretical in nature -- mainly proofs), students will have two tries. If the first attempt is not both logically correct and well-written, no grade will be given. The student may re-do the problem and turn it in again the next class period. Students may discuss problems and work together on solutions but in all cases each student must write up his/her final solutions independently (no copying!). Late homework will not be accepted unless permission has been received from the instructor BEFORE the due date.

Programming Assignments: There will be at least two programming projects that relate the theory to practical applications. Programs must be written in C++ and adhere to good programming practice and documentation standards. Students may discuss general solution techniques and C++ issues that arise in writing the programs but each student must write their programs independently. If you anticipate being unable to meet a deadline for a program, talk to me at least 24 hours before the deadline. In extenuating circumstances special arrangements may be made. Please note that this must be discussed - just sending an email does not automatically grant you extra time. If you have not been granted extra time ten percent per calendar day (24 hours) will be deducted for late work. Work more than 4 days late will not be accepted.

Co-Curricular Requirement: The Department of Mathematics, Computer Science, and Physics (MCSP) is offering a series of discussions that appeal to a broad range of interests related to these fields of study. These co-curricular sessions will engage the community to think about ongoing research, novel applications, and other issues that face our disciplines. You are invited to attend all of these events but participation in at least 3 is mandatory. Within one week of attending an event you must submit a one page paper reflecting on (not just summarizing!) the discussion. All papers must be submitted to Inquire. If your paper is not submitted to Inquire within the one week time frame you may not count that event as one you attended. The MCSP discussions are generally scheduled for Wednesdays at 5:30 or Tuesday or Thursday at 7:00. A schedule will be provided soon and will be posted on the course web page. Please discuss scheduling conflicts with the instructor ASAP.

Special Needs: If you are on record with the College's Special Services as having special academic or physical needs requiring accommodations, please meet with me as soon as possible. We need to discuss your accommodations before they can be implemented. Also, please note that arrangements for extended time on exams and testing in a semi-private setting must be made at least one week before the exams. If you believe you are eligible for accommodations but have not yet formally contacted Disability Support Services, please contact Ms. Barbara Awbrey, at 375-2247 or drop by the Center for Learning and Teaching in Fintel Library.

Academic Integrity: Students are expected to adhere to the Academic Integrity policies of Roanoke College. All work submitted for a grade is to be strictly the work of the student unless otherwise specified by the instructor. The policies as outlined in the Academic Integrity Handbook will be strictly enforced in this course.

Electronic Devices and Academic Integrity: All cell phones and other electronic devices must be turned off prior to entering the classroom or lab. Laptops may be used during class only for taking notes or other class activities. The use of any electronic device during a test or quiz is prohibited. Any use of such a device during a test or quiz will be considered a breach of academic integrity. Handheld calculators may be used only with the permission of the instructor, and when permitted, may not be shared by students (each student must have his/her own).

Computer Use Policies: All students must abide by the Computer Use policies of Roanoke College. Failure to do so will result in involuntary withdrawal from the course.