Phone: 678-466-4411

Office: TBA

Office hours:

MW 3:30 - 4:45 PM, T 12:30 - 1:45 PM, or open door

Note: the syllabus and schedule are subject to change.

- Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines
- 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
- 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
- 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)
- 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
- Apply algorithms to transform context-free grammars into normal forms such as the Chomsky and Greibach normal forms
- Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction

- An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices;.
- An ability to apply design and development principles in the construction of software systems of varying complexity.
- An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.
- An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution.

CSCI 2302: Data Structures |

Day of week | Times | CRN | Location |
---|---|---|---|

MW | 2:10-3:25 PM | 80195 | UC 322 |

CSCI4333-1Fall19@groups.clayton.edu (80195 TR morning class) |

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

Grading will be based upon the following scale:

Grade | Range |
---|---|

A | >= 90% |

B | 80% - 89% |

C | 70% - 79% |

D | 60% - 69% |

F | < 60% |

Assignment weights are as follows:

Assignment | Portion of Grade |
---|---|

Final | 30% |

Three Monthly Tests | 36% (12% for each of 3 tests given approximately once a month) |

Review Quizzes | 12% |

Project Portfolio (see details below) | 12% |

Practice Discussions (see details below) | 10% |

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.

- Chapter 1: Basic Mathematical Objects
- Chapter 2: Finite Automata
**Test #1**: Late September- Chapter 3: Regular Expressions, Nondeterminism and Kleene's Theorem
- Chapter 4: Context Free Languages
**Test #2**: Late October/Early November- Chapter 5: Pushdown Automata
- Chapter 6: Context and Non-Context-Free Langauges
- Chapter 7: Turing Machines
**Test #3**: Monday November 25th, 2019- Chapter 7: Church-Turing Thesis
**Final Exam: Wednesday December 4th: 12:30 - 2:30 PM**

**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:

- Project Completeness
- Project Correctness
- Meeting milestone/feedback deadlines (feedback information below)
- Incorporating project element feedback
- Documentation of project design and development

To facilitate this practice, each student is expected to participate in practice discussions. In practice discussions, each student must bring a problem for discussion, answer another student's problem, post the answer for their original problem, and discuss what was learned during the process. Practice problems cannot come from the book or examples of the course. Students are expected to use their internet search skills to find unique problems for the class to work on.

Practice discussions must be documented via the project portfolio. Each student must explain their problem they brought to the discussion and the problems they solved in the discussions. Grading will be based on both active participation in the practice discussions and quality of the problems brought to the disucssion and worked on in the discussion.

- Each student begins the semester with a one feedback points balance.
- For each course element that requires feedback, the student is
responsible for actively soliciting feedback for that element.
- Students may only solicit feedback for course elements that are turned
in a timely fashion before the given due date.
- Students who solicit feedback before the deadline gain one point on
their feedback balance. Students who do not solicit feedback, or turn in
their assignment late, lose one point from their feedback balance.
- Students who have a positive feedback balance gain two
rewards. The first is that students with a positive feedback balance may
request and receive feedback via E-mail. The second is that students with a
positive reward balance at exam time earn two extra credit points on their
exam.
- Students who do not have a positive feedback balance must solicit feedback in person during office hours. In addition students who do not have a positive feedback balance at exam time are not eligible for extra credit points on their exam.

- The class attendance policy allows for two unexcused absences.
- All excused absences must be accompanied by documentation such as a
doctor's note.
- For each unexcused absence after the first two, 1 point will be
deducted from the final course grade for each unexcused absence. The
maximum total deduction is 5 points.
- Any excused absence for a monthly test or final must be discussed with the instructor at least 24 hours in advance. Test absences must be documented beforehand. Test absences that do not follow the above procedure will result in a grade of zero that that test or final.

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

- Please inform the instructor via E-mail of the problem.
- Please
**DO NOT SUBMIT HOMEWORK VIA E-MAIL UNDER ANY CIRCUMSTANCE!**Homework submitted via e-mail will not be accepted. All homework must be submitted via Desire2Learn.

- If class is to be canceled or delayed, you will be notified you via e-mail as
soon as possible. Any missed class topics will be covered
following class. In addition missed contact time will be made up using
alternatives such as online assignments or lecture videos.
- Skills Practice is essential for learning success. When learning new
skills that will be assessed on exams, be sure to practice examples in
order to gain the confidence to perform that skill on the exam. Not all
skills practice will be graded work. Nontheless, it is essential to
practice skills for both understanding and mastery.
- Start assignments early. This way, you can ask questions and clarify
things that are confusing. Be sure to take a look at the homework when you receive it and not an hour before it is to be turned in!
- If you cannot keep up with the pace of this class, please talk with your professor as soon as possible. Please do not simply drop the class without first discussing your situation.

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.

- Able to use Windows operating system
- Able to use Microsoft Word word processing system
- Able to send and receive email using Outlook. Your instructor will respond only to emails that originate from your Clayton State student email. Use only your Clayton State to communicate information to your instructor. D2L E-mail may have a slower response time than CSU E-mail
- Able to attach and receive attached files via email
- Able to use a Web browser