CS 2490 Introduction to Theoretical Computer Science
Syllabus, Fall 2018

Meeting Time and Place: Section 101: 9:00 - 9:50 MWF, BH 240. Section 102: 2:00 - 2:50 MWF, BH 310

Professor: Dr. Alice McRae

Email Address:[email protected]

Web Addresses: asulearn.appstate.edu, www.cs.appstate.edu/~aam

Office: BH 312L

Telephone: 828-262-2385 (office)

Office Hours
These are the hours when I plan to be in my office so that I can help you if you stop by. There are times when I am surprised by a mandatory meeting that someone schedules during my office hours, or by some other emergency. I will let you know about the change by email if I have sufficient time for that, but occasionally I may simply post a note on my office door. To make up for such occasions I keep an open door policy. You may feel free to stop by any time to see if I have time to help you. If I don't, we'll schedule an alternative time. My full schedule is available online at www.cs.appstate.edu/~aam/fall18.html. Here are my regular office hours:

Monday, Wednesday, Friday: 3:00 – 5:30. Tuesday, Thursday: 2:00 – 3:00

Text
Formal Languages and Automata, 5th edition, Peter Linz, Jones and Bartlett Publishers, 2006.

Supplemental Readings: Course Notes (AsULearn)

Required Supplies: 3-ring binder for worksheets and assignments

Course Goals
By the end of this course, students will


Grading
Students will receive the best grade computed between three grading plans.

Plan A

Plan B

Plan C

Attendance 10% 0% 0%
Homework 10% 10% 0%
Online Quizzes 10% 15% 15%
Programs 10% 10% 10%
Test 1 20/15% 20/15% 25/20%
Test 2 20/15% 2015% 25/20%
Test 3 0/10% 0/10% 0/10%
Final 20% 25% 25%

Attendance/Class Participation Every day we meet you will be responsible for actively participating in class. This may mean answering questions; it may mean being fully engaged in the material and solving problems on the worksheet for the day. An attendance grade will be assigned based on the number of days that you are marked present divided by the number of days the roll is taken.

Homework Problems. There will be weekly homework assignments. Homework assignments will be due on Fridays. Students will be given an option for many of the homework assignments, and many of the homework assignments will include options for extra credit.

Online quizzes There usually will be an online quiz every week. When there is an online quiz, usually the quiz will be due on Wednesday evening at 11:55pm, and the quiz should be posted by Monday afternoon or earlier. You may work in a group when you do the online quizzes for this course. Be sure that each person in the group submits a quiz on ASULearn.

Programming assignments. There will be several programming assignments over the course of the semester. I will grade your programs based on your use of the techniques discussed in class and the correctness of your output. Be absolutely sure that you compile and tested.

Tests and Exams. There will be two or three semester tests, two in-class tests, and perhaps one smaller test and an in-class final exam. All exams are mandatory and there will be no make-up exams unless you have to miss class for a reason that the University considers valid. In such a case you must supply appropriate documentation prior to the date of the exam unless you become ill suddenly. In that case I will need the telephone number of the doctor you saw so that I can verify your illness.

Electronic Devices in Class
In this class it is difficult to take notes using a laptop because there are so many pictures and symbols that are part of our material. Therefore I find that most people who have laptops open in front of them are not taking notes. Because I firmly believe that multitasking is not good learning behavior, I do not want you to use laptops, smart phones, PDAs, MP3 players, or any other electronic devices during class. Please set your cell phone so that it does not ring while you are in class. If you feel that you must have a cellphone or laptop open during class, then I will have a special area in the back of the classroom where you will sit. If you sit in the back of the room with your laptop open, you will be less likely to distract other students.


Reading
Try to read the appropriate sections of the book before lecture. Theoretical textbooks are difficult to read, but we usually cover only a few pages per class period. If you are not sure which sections in the book correspond to the material we are covering, please ask in class.

Students With Disabilities
Appalachian State University is committed to making reasonable accommodations for individuals with documented qualifying disabilities in accordance with the Americans with Disabilities Act of 1990, and Section 504 of the Rehabilitation Act of 1973. Those seeking accommodations based on a substantially limiting disability must contact and register with The Office of Disability Services (ODS) at www.ods.appstate.edu or 828-262-3056. Once registration is complete, individuals will meet with ODS staff to discuss eligibility and appropriate accommodations.


Academic Integrity Code
As a community of learners at Appalachian State University, we must create an atmosphere of honesty, fairness, and responsibility, without which we cannot earn the trust and respect of each other. Furthermore, we recognize that academic dishonesty detracts from the value of an Appalachian degree. Therefore, we shall not tolerate lying, cheating, or stealing in any form and will oppose any instance of academic dishonesty. This course will follow the provisions of the Academic Integrity Code, which can be found at http://academicaffairs.appstate.edu/syllabi.


Attendance Policy
It is very important that you attend class. Some of the material for this course will be presented only in class lectures; it is not all in the textbook. Although I have no formal attendance policy, most students who do not attend class perform very poorly on tests and homeworks. It is difficult to catch up if you fall behind in this course; the material in this course builds on itself. The University's attendance policy is described at http://academicaffairs.appstate.edu/syllabi.


Student Engagement
In its mission statement, Appalachian State University aims at "providing undergraduate students a rigorous liberal education that emphasizes transferable skills and preparation for professional careers" as well as " maintaining a faculty whose members serve as excellent teachers and scholarly mentors for their students." Such rigor means that the foremost activity of Appalachian students is an intense engagement with their courses. In practical terms, students should expect to spend two to three hours of studying for every hour of class time. Hence, a fifteen hour academic load might reasonably require between 30 and 45 hours per week of out-of-class work.


Topics Covered
Topics to be covered in this class include regular expressions, regular grammars, finite state machines, regular languages, push-down automata, context-free languages, context-free grammars, Turing machines, phrase-structure grammars, recursively enumerable languages and non-recursively enumerable languages, the halting problem, and possibly the complexity classes P, NP, and NP-complete.

General Policies
I teach best in a class in which I receive interaction from my students. My teaching style is to ask many questions as I proceed, and I want you all to suggest answers. It is not necessary to raise your hand to speak. I will never make you feel stupid for giving an answer that isn't correct, so speak out. Do not let one or two class members dominate discussions. If this begins to happen, I will speak with those persons outside of class. If you realize that you are offering most of the feedback in class, slow your answers down to give others a chance to speak. It is not necessary to impress me during class. You will impress me by doing good work. Let's make class a fun learning time.

I encourage you to ask questions during class, during office hours, and through email. If you need help on the homework or on a programming assignment, come see me. Also, please offer feedback on the course as it progresses. I have not taught this course in many years, and I am experimenting with a lot of ideas. I welcome comments, positive or negative, that will help me continue to improve this course.

Unethical practices by any student, such as copying all or part of a program or copying from someone else's homework or exam, will be dealt with according to the ASU Code of Academic Integrity. You may find the policy at studentconduct.appstate.edu. I do not consider discussing the homework problems or programs with your classmates a violation of the integrity code, but the work you submit to me should be your own conclusion.



Special Days
Monday, Aug. 27 Last day to add a class, last day to drop without it counting for one of your four drops

Monday, Sept. 3

 Labor Day Holiday
Tuesday, Sept. 4 Last day to drop without the class being used in the calculation of the "fifty percent surcharge"
Thursday–Friday, Oct. 11–12 Fall Break
Thursday, Oct. 25 Last day to drop the class or withdraw without academic penalty
Wednesday–Friday, Nov. 21–23 Thanksgiving Holidays
Wednesday, Dec. 5 Last day of classes
Friday, Dec. 7,
2:00pm–4:30 pm		 Final exam period (meet in regular classroom) for 2:00 section (102)
Monday, Dec. 10,
8:00–10:30 am		 Final exam period (meet in regular classroom) for 9:00 section (101)