CSCI 4333 - Theory of Computation

http://kahuna.clayton.edu/csci4333

(Fall 2021: CRN 82994/83075)

Printable Course Syllabus

Byron Jeff

E-mail: byronjeff@clayton.edu
Phone: 678-466-4411 (Please leave a voicemail)
Office: UC 340
Office hours (In person, Teams or E-mail):
    MW 2:30 - 3:30 PM, R 1:30 - 2:30 PM, or by appointment

Note: the syllabus and schedule are subject to change.

Course Description (3-0-3)

Theory of Computation: This course is a study of the main areas of theoretical computer science and their hierarchical interconnections. Basic results relating to formal models of computation are studied, with emphasis on grammars and languages, finite automata, Turning machines, and computational complexity.

Course Objectives:

Students are expected to obtain a developing level of mastery in computer science. Students will demonstrate an emerging level of knowledge of a broad range of fundamental computer science concepts and topics. Students should show potential to perform independently and should exhibit a high level of reasoning, critical thinking and problem solving skills. Course objectives are listed for each CS program outcome: At the end of the course the student should be able to:
  1. Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines
  2. Design finite automata corresponding to given regular sets, and describe the regular set associated to a given finite automaton. Do the same with pushdown automata and context-free languages, and with Turing machines and recursively enumerable sets
  3. Comprehend and apply a number of algorithms such as: the subset construction to transform a indeterministic finite automaton into a deterministic one; the DFA state minimization to minimize the number of states in a deterministic finite automaton; and the conversion algorithms from regular expressions to finite automata and vice versa
  4. Understand limitations of finite automata (respectively, pushdown automata) and prove that some sets are not regular (respectively, context-free) by using the pumping lemma for regular languages (respectively, context-free languages)
  5. Simulate CFGs by NPDAs and vice versa, that is, convert a given context-free grammar to an equivalent nondeterministic pushdown automaton, and convert a nondeterministic pushdown automaton to an equivalent context-free grammar
  6. Apply algorithms to transform context-free grammars into normal forms such as the Chomsky and Greibach normal forms
  7. Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction

Program Outcomes:

The CS curriculum is built on six core program outcomes. Successful completion of this course will contribute to the following subset of these outcomes. Graduates will demonstrate a Mastery Level for the following outcomes: 1.Solve complex and significant problems with professional skill by formulating efficient and effective algorithmic solutions to a wide variety of sophisticated problems normally encountered in computing and in academe,

3.Apply core concepts in computer science,

6.Demonstrate an ability to acquire, interpret, and communicate results orally or in writing.

Prerequisites

CSCI 3333: Programming Languages

Meeting Times

Day of weekTimesCRNCourse Delivery Method
R 3:10-4:10 PM 82994/83075Asynchronous Online Content Delivery with In-Class Assessment/Project Activities

Class Email:

CSCI4333-1AFall20@groups.clayton.edu (82994 R afternoon/online class)

CSCI4333-1BFall20@groups.clayton.edu (83075 R afternoon/online class)

Textbook

Introduction to Languages and the Theory of Computation, 4/e (4th Edition) by Martin, McGraw Hill

Assessment

You will have numerous opportunities to practice and demonstrate mastery of the materials covered in this course. It is up to you to keep current on all readings and assignments (including in-class announcements). *If you fall behind, you will most assuredly fail this course!*

Grading will be based upon the following scale:

GradeRange
A >= 90%
B 80% - 89%
C 70% - 79%
D 60% - 69%
F < 60%

Assignment weights are as follows:

AssignmentPortion of Grade
Final 30%
Three Monthly Tests 36% (12% for each of 3 tests given approximately once a month)
Review Quizzes 16%
Project Portfolio (see details below) 12%
D2L online Discussions (see details below) 6%

The final for this class is comprehensive. In addition the grade on the final can be used to redeem one *(and only one)* monthly test grade. So if your grade on the final is higher than your lowest monthly test grade, then that monthly test grade will be replaced with the grade from the final. This policy is designed to give a student the chance to improve one poor monthly test showing.

Partial credit may be given.

Hybrid course delivery, assessment, and communication

The conversion of on campus classes to a hybrid online environment brings a few challenges. These include course delivery, assessment, and communications issues. This section addresses how these items will be managed in this course.

The first issue is handling how to deliver instruction. My plan is to generate a series of screencasts of course content and to make those available via D2L. My expectation is that students would access these videos asynchronously, at the time of their choosing within a certain window. They will be posted into your D2L course. I plan to keep them short, under 30 minutes each. As such you will be responsible for multiple content items in a unit timeframe.

Assessment in an hybrid online environment is going to be a challenge. Normally with an hybrid online class, assessment would also be asynchronous, with wide time windows and time limits. Something along the lines of having a week to take an assessment, while having 90 minutes to do it after starting. Unfortunately, that setup simply facilitates way too much information sharing among students which makes it difficult to ascertain who actually knows what material. My plan to combat this trend is to perform synchronous assessment at the scheduled class times. This is the reason that the course is hybrid online but also has an assigned class time. So everyone will get the test/quiz at the same time at the beginning of the specified synchronous course time and have limited time take it, and must turn it in at the "end of class". Because of this, please plan to make available the listed class time for such activities as review quizzes and tests. These will be offered most weeks in the 2nd time slot (Wed or Thurs). There may be an occasion assessment that will be slotted for the 1st time slot (Mon or Tue).

Having done hybrid online classes before, I would like to point out the two biggest challenges to operating in the hybrid online class environment. The first is engagement. On campus classes facilitate a regular engagement of both students and instructors because each have to be in a classroom at a specific time. Just the action of being present facilitates engaging in the material. Online decouples students (and the instructor), from that sometimes passive engagement strategy. If you don't log in, review the material, or do the work, then it's easy to become disconnected from the course. I am asking that each of you plan to touch base with the course every day, or at worst every other day in order to remain connected to the activities going on in the class. In addition I will be rather insistent about discussions in public forums as opposed to private discussions via E-mail. The rationale is simply the fact that if the entire class can see a productive discussion, then all class members can benefit from it. So please expect that questions asked via E-mail will either be requsted, or transferred by me, into the public discussion forums for the course.

The second challenge is communication. Again it is easier to communicate a lot of information when gathered in a single spot for an extended period of time. In the hybrid online environment, communication is a critical component. But I admit that it can be a challenge for folks like me who are talkers, and not writers. I plan to push communications via class E-mail and answering questions in the Q/A discussion boards of each course. The Q/A discussion boards are set up to deliver me an immediate notification to shorten the turnaround time for answers. If you need to communicate with me, use the Q/A discussion boards for each UNIT for items that are relevant to the entire class, and CSU E-mail (not D2L e-mail please!) to communicate personal or urgent issues. Like I expect from you, I'll be checking into each class every day so you can expect 24 hour or less turnaround to Q/A posted items. Be aware that the more you ask, or the more complicated the issue, the longer it may take to get back to you. For example 5 individual short posts/E-mails will likely get faster answers than one single post/E-mail with all 5 items in it because I generally try to solve all of the problems before answering.

Course Topics

The list of course topics below will be presented in the order listed below. The listed exams are inserted following the likely coverage of the material that the exam will cover. Be aware that in class adjustments of both the material and the exam coverage may be made. Any in class adjustments superceeds the outline listed here. Exact test dates will be announced a minimum of one week before the actual exam.

COVID-19 Health and Safety Syllabus Addendum

Clayton State University is committed to providing and promoting a healthy and safe learning environment. All students, faculty, and staff are expected to comply with all social distancing mitigation measures, practices, guidelines and policies. Please note the following rules and regulations that are in place during the Fall 2021 semester due to the COVID-19 pandemic:

  1. Anyone who is feeling ill should refrain from coming to campus and should consult the symptoms related to COVID-19 to determine if a visit to a physician or clinic is necessary. Any faculty, staff or student who is exhibiting COVID-19 symptoms, has been sick with COVID-19 symptoms, tested positive for COVID-19, or has been potentially exposed to someone with COVID-19 (either through community-related exposure or international travel) should self-isolate or stay home and report their case using the COVID-19 Reporting Form. Faculty and staff should also notify their supervisor. Students should consult with University Health Services.

  2. For the health and safety of your fellow classmates and the campus community, we strongly encourage you to wear a face covering during class, during in-person office hours and while inside campus facilities.

  3. Assigned seating will be used in all classes on campus, and attendance will be taken on a daily basis. Seating charts will be accessible through the D2L course space and should be reviewed prior to the first day of class. Students are to refrain from entering the instructor designated space unless the instructor allows.

  4. Disinfecting wipes or other approved cleaning solutions will be available to all students and faculty who have an on-campus class.

  5. All persons are to adhere to the posted signs and directions in hallways and buildings, except in the case of fire or other emergency requiring evacuation.

  6. Students are not to enter rooms until 10 minutes before class and must vacate the space at the end of class. Any classrooms that are not in use for classes should be left vacant unless prior scheduling approval has been granted.

  7. To aid in ventilation of classrooms and to maximize air exchange rates, classroom doors should be closed during each class meeting and make sure they are closed after their class concludes. Air purifiers should be left on and will operate based on a sensor.

Project Portfolio

Please read carefully!

A comprehensive student generated project portfolio must be submitted by each student on the specified date near the end of the semester. The portfolio consists of a number of required project elements coupled with additional project elements selected by the student. The portfolio will serve as the single grading instrument for the project portion of the course. The portfolio will be graded on the following elements:

Each element of the project portfolio will have a milestone/feedback deadline during the semester. Project elements that are substantively complete and correct (i.e. not perfect but mostly done) and turned in by the milestone/feedback deadline will receive feedback that the student may use to improve their project for the portfolio. However, any project element that is not submitted for feedback by the given deadline, or is not substantively complete/correct at that deadline will not receive credit for meeting the milestone/feedback deadline nor feedback incorporation element for that project element.

Active Feedback System

Soliciting and incorporating feedback is an essential element for success in the learning and development of technological systems. In order to encourage active student participation in the feedback process, this course implements an active feedback points system. The system is governed by the following rules:

Attendance Policy

Your active participation in class is expected. Class attendance is expected because it's much easier to learn if you're participating in class and asking questions about things that confuse you.

Late Work Policy

Late work delays both the learning process and the feedback process. Project elements needs to be turned in a timely fashion. D2L assignment submissions for project elements will be closed 24 hours after the feedback deadline.

The instructor may waive late penalties if techical problems to homework submission occurs. In the event of technical difficulties:

Words of Wisdom (TAKE THIS PART SERIOUSLY!)

Academic Misconduct

Any student is found obtaining or granting inappropriate help in this course on any in-class graded assignment (test, quiz, exam) will subject to acadmic discipline. The offense will go on permanent record with the university. If this is not the student's first academic misconduct offense at CSU, he will be recommended for expulsion from the university. This is in full accord with CSU's policy, and we encourage you to read and review the university's policy in your student handbook.

So it is permissible to do group work or work with a tutor or other instructors on outside work in this course that is to be turned in for a grade. However, remember that the objective is to gain understanding of the problem solving process and apply that understanding. Note that the majority of the course grade is done via an in-class assessment, which each student must do on their own work without assistance.

Academic discipline can range from a zero for the in-class assessment in question to expulusion from the University depending on the circumstances.

All alleged instances of acadmic misconduct will be referred to the Office of Student Affairs.

Hardship Withdrawal

Students who experience an unexpected event or circumstance beyond their control that directly interferes with their ability to continue to make satisfactory progress in classes, such as serious illnesses or unexpected major life events, may petition the Dean of their major for a hardship withdrawal from all classes. In order to be considered for a hardship withdrawal, the student must have been passing all courses at the time that the emergency or other hardship arose and notify his or her instructors or other University officials about the hardship situation as soon as possible after it arose (per University and BOR policy, passing is defined as a grade of D or above). Hardship requests that are not filed in a timely manner are subject to denial even if the student was passing and the hardship was legitimate. Students who attend any classes through the end of a term and complete all course requirements (i.e. final project or exam) are not eligible for hardship withdrawal. If you have taken a final exam in any of your courses, you may not request a hardship withdrawal. For more information go to: http://www.clayton.edu/registrar/Withdrawal

ITP Choice Information

Beginning Fall Semester 2001, all students at CCSU are required to state that they have on-demand access to a notebook computer that meets the recommended hardware/software specifications that have been established by Clayton State faculty. Academic penalties may be incurred for not meeting this requirement. See http://www.clayton.edu/hub/itpchoice/notebookcomputerpolicy for more information.

Computer Skill Prerequisites

Students in this course must have the following prerequisite skills:

Disruption of the Learning Environment

Behavior which disrupts the teaching-learning process during class activities will not be tolerated. While a variety of behaviors can be disruptive in a classroom setting, more serious examples include belligerent, abusive, profane, and/or threatening behavior toward the instructor and/or other students in the class. A student who fails to respond to reasonable faculty direction regarding classroom behavior and/or behavior while participating in classroom activities may be dismissed from the class. A student who is dismissed from the class is entitled to due process and will be afforded such rights as soon as possible following dismissal, in collaboration with the Office of Community Standards. If found in violation, a student may be administratively withdrawn and may receive a grade of WF. More detailed examples of disruptive behavior are provided in the Code of Conduct and Disciplinary Procedures sections of the Clayton State University Academic Catalog and Student Handbook.

Weapons on Campus

Clayton State University is committed to providing a safe environment for our students, faculty, staff, and visitors. Information on laws and policies regulating weapons on campus are available at http://www.clayton.edu/public-safety/Safety-Security/Weapons

Disability Services

Students with disabilities who require reasonable accommodations need to register with Disability Services (DS) in order to obtain their accommodations. You can contact them at 678-466-5445 or E-mail at disabilityservices@clayton.edu .