CS 4550/5550 Theoretical Computer Science
Syllabus, Spring 2022

Class Schedule
The class meets from 11:00-11:50, Mondays, Wednesdays, and Fridays in Belk 310.


Instructor
Dr. Alice McRae

Preferred pronouns
She, her, hers


Office
312-L Belk Hall


Telephone Numbers
Office: 262-2385, Home: 265-3359


Office Hours
2:15-4:45 M-F


Textbook
Introduction to the Theory of Computation(3rd ed) by Michael Sipser (e-book on ASULearn)

Required Supplies:
3-ring binder for worksheets and assignments

Content
This course builds on an introductory theoretical computer science course that focused on automata and grammars. We will review this pre-requisite material in chapters 0 through 2 of the Sipser text. We will try to cover much of the material in chapters 3 through 10 of Sipser's textbook, emphasizing computability theory and complexity theory. Time and interest permitting, we may go back and look at some topics related to grammars and their applications.

Pandemic Concerns
These are uncertain times. Normally a syllabus is a contract from an instructor, but there may be many parts of this course that need to change based on unexpected events. All of us need to remain flexible and do our best to care about the safety of ourselves, our family, other students, and the community. All students should stay home when sick, wash hands frequently, and follow the ASU Face Covering Policy. Let's hold each other accountable and stay safe.

Attendance and Class Participation
It is important that you attend class. Some of the material for this course will be presented only in class; it is not all in the textbook. Further, the material in this class is advanced and it is not easy to grasp. Students who do not attend class will perform very poorly on tests. It will be difficult to catch up if you fall behind in this course; the material builds on itself.

Every day we meet you are expected to be 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.

This class is face-to-face. However, if you are sick, you should not attend class. I will try to remember to start a zoom session at the beginning of each class, and I can record the class is a student makes such a request. Although not ideal, students can attend this way if it becomes necessary through quarantining. There is no reason to log into a zoom session, and then go do something else.

If there is snow or ice, it is possible that the class will meet online via zoom. You should receive an e-mail early with information about the change.

Unless the university goes all online, all tests must be taken in person.

Grading
A ten point grading system will be used: 90-100 A, 80-89 B, 70-79 C, 60-69 D, and below 60 F. It is possible these numbers will be adjusted up (maybe 78 - 88 will be B, for example), but the adjustment will apply to all students, and the adjustment will only help, and never hurt, the final grade. The lowest numeric grade in each category will result in a minus added to the letter grade (e.g. 90 is A-), and the highest will result in a plus.

Tests 40%
Final 20%
Online Quizzes 10%
Homework 15%
Group Solutions 15%

Homework
You may work on homework problems in groups. However, each student should write up the solutions in his or her own words. Problems on the tests will use similar techniques to those needed on the homeworks. Late homeworks are not accepted.

Students often will be assigned at least one starred homework problem from each chapter or an additional problem that the teacher has been thinking about. Sometimes the teacher even does not know the answer! These problems are meant to be challenging; more than getting an answer, the point of these problems is often to widen the student's perspective and to lead the student into asking underlying questions about the topic at hand. If you can't get "an answer," write about what you did learn or what you tried - perhaps modify the question to something you can answer. Occasionally, one of these questions could suggest research topics for a thesis - perhaps even a PhD dissertation. Students are ENCOURAGED to discuss these problems together.

Group Solutions
Often students will work on problems in class as a group. In class activities, students can work together with any others. Sometimes, the results of groupwork will be collected, and credit is given for participation. Additionally, students will be assigned special groups at the beginning of the semester for outside-of-class activities. The whole group does not need to meet together outside of class, but the group in some sense will be accountable to one another. There may be forum activities or Flipgrid assignments in which students work within their groups. During the semester, groups can choose specific problems and at least one member of the group will present a solution to the class. Each student will need to present during the semester. These presentations (usually short) will be graded. It will be the responsibility of the group members to help the presenter prepare and practice the solution. More information about groups will be given when we get through add/drop week, and I'll add an update about groups on ASULearn to reflect the information.

Reading
When applicable, try to read the appropriate sections of the book before lecture. At the beginning, we will move fast because you have already seen the material before. In later chapters we usually will cover only two or three pages a day, and even when it seems those pages are written in Greek, you will at least have an idea what the class will be about, and you can come with questions. Also, there may be some assigned reading that is not from our textbook.

Tests and Final Exam
Unless arrangements are worked out in advance, missed tests cannot be made up. If a student has an excused absence on a test day, then the final exam grade will substitute for the missed test. The final exam is scheduled for Friday, April 29th from 11:00 am to 1:30 pm.


Appalachian's Syllabus Policy
I will follow the university's common syllabus policies: Syllabi Policy and Statement Information

Academic Integrity Code (quoted from Vice Provost)
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 on the Office of Student Conduct Web Site at www.studentconduct.appstate.edu.


Accomodations for Students with Disabilities (quoted from Vice Provost)
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 http://www.ods.appstate.edu/ or 828-262-3056. Once registration is complete, individuals will meet with ODS staff to discuss eligibility and appropriate accommodations.

Personal Inclusive Excellence Statement
I want every student to be treated with dignity and respect in this classroom. For the most part, students seem to be better at this than I am. I have got lots to learn. Please feel free to correct me and help me learn how to be the person I want to be. Hold me accountable.


Special Days
Friday, January 14 Last day to add a class
Monday, January 17 Martin Luther King Holiday - no class
Monday, Mar. 7 – Friday Mar. 12 Spring Break - no classes
Monday, March 21 Last day to drop the class or withdraw using a career drop
Friday, April 15 Easter Holiday - no classes
Wednesday, April 27 Last day of classes
Thursday, April 28 Reading Day
Friday, April 29
11:00am–1:30		 Final exam period (meet in regular classroom)