Syllabus

This syllabus page is based on the NC State Syllabus Template.

Table of Contents

Instructor Information

[Abida Haque]

Email: ahaque3@ncsu.edu

Office phone: 919-513-7973

Office location: 111 Lampe, room 223

Please call and leave a message

Response Time

I’ll usually respond to messages within 48 hours (weekends non-inclusive). If you don’t hear from me, feel free to gently follow up.

Virtual Office Hours

By appointment only

Course Information

Course Website: https://wolfware.ncsu.edu/courses/my-wolfware/

Course Credit Hours: [3]

Meeting Time and Tool Used

434 111 Lampe Drive

MW 4:30 – 5:45pm

Prerequisites/Corequisites 

MA 225 or CSC 226, with a C or better

General Education Program (GEP) Information

Indicate whether the course fulfills a GEP. If none, state “none”

GEP Category Fulfilled

Include the GEP category or categories, such as Natural Sciences or Humanities. If none, state “none”

GEP Corequisites

Include whether the course satisfies a GEP corequisite(s). If none, state “none”

Course Overview

Study of three classical formal models of computation – finite state machines, context-free grammars, and Turing machines – and the corresponding families of formal languages. Power and limitations of each model. Parsing. Non-determinism. The Halting Problem and undecidability. The classes P and NP, and NP-completeness.

Structure

Organization

  • Each week is shown on Moodle as a separate subheader. Each week has 1-2 videos (available through YouTube) and guided notes that go with the slides of the video.
  • Generally, understanding these videos and doing the reading will be enough to complete the MCQ.
  • For the (nearly) weekly written homework, you should attend class to get the background info necessary. The errata we create in class (quiz questions, slides, notes, etc.) will be uploaded after each class for your review and added to that particular week.

Recommended Schedule

  • Watch the video for the upcoming week, following along with guided notes.
  • Start attempting the problem set (when available)
  • Complete the MCQ. You can start at any time during the week. These are due Friday of (almost) each week.
  • Use class to ask any questions you have about the problem sets. I’ll provide some more context, hints on how to attempt the problems, similar questions, etc. There are also in-class quizzes.

Exams

  • We do not have standard midterms with high weights. Instead, we have (near) weekly quizzes.
  • This includes an intake quiz, done in the first week.
  • We do have a final exam!

Oral Homework

  • We will have 2-3 oral homeworks, which you must use Moodle scheduler to find a time to meet with one of the teaching staff. Meetings will be 20 minutes long per person.
  • We will pick from a selection of questions, which will be given to you ahead of time, and you’ll have to present your solution.
  • You may work with a group (size up to 3). If you are one, find 20 minutes to meet, and if you’re three, find 60 minutes to meet.
  • You don’t have to submit any papers, and your homework grade will be available on Moodle.
  • There is flexible scheduling, but the topics of the oral exam will depend on how early/late in the scheduling block you meet with us.

Problem Sets

  • We have ~3 problem sets (written homework).

Homework

  • There is optional homework. We can grade it, on request, to give you feedback.

Course Learning Outcomes

Learning outcomes are also commonly referred to as goals, objectives, or competencies. NC State’s Policies, Regulations, and Rules refers to them as “outcomes”.

Student learning outcomes in different sections of the same course should not differ significantly. Include the learning outcomes related to General Education Program (GEP) objectives, if applicable. GEP objectives can be found at GEP Category Requirements.

Upon successful completion of this course, a student will be able to…

  1. Explain and formally specify basic automaton types (finite state, pushdown, and Turing machines, both deterministic and nondeterministic), basic formal language types (regular, context-free, decidable, recognizable), and basic formal grammar types (regular expressions and context-free grammars).
  2. Synthesize finite automata (DFA/NFA), pushdown automata (PDA), and Turing Machines (TM) to recognize specific languages.
  3. Convert representations of languages between different automaton and grammar types (between DFA, NFA, and regular expressions, between CFG and normal form CFG).
  4. Construct counter-examples that show particular problems cannot be solved by finite or pushdown automata.
  5. Explain, exemplify, and demonstrate uncomputability of specific languages by different automation types (DFA, PDA, Turing machines).
  6. Define measures of deterministic and nondeterministic computation time and space, the notions of deterministic (P) and nondeterministic (NP) polynomial running time, and explain the significance of the P=NP? question.
  7. Define the notion of NP-completeness, explain its significance for the P=NP? question, and demonstrate NP-completeness of specific problems by reduction from problems known to be NP-complete.
  8. Describe concrete and common examples of real-world NP-complete problems from different fields.

Topics

  • Deterministic Finite Automata
  • Nondeterministic Finite Automata
  • Regular Languages
  • Regular Expressions
  • Nonregular Languages
  • Context-Free Grammars
  • Pushdown Automata
  • Non-Context-Free Languages
  • Turing Machines
  • The Church-Turing Thesis
  • Turing Machine Variants
  • Decidability
  • The Halting Problem and Undecidable Languages
  • Time Complexity of Algorithms
  • The Classes P and NP
  • The Theory of NP-Completeness
  • NP-Completeness Reductions

Course Materials

Required Textbook and/or Software

Course textbook: Introduction to the Theory of Computation, 3rd edition, by Michael

Sipser. ISBN-13: 978-1133187790. The textbook is required.

It is fine if you have an old version of the textbook (1st or 2nd edition). Sometimes the numbering of the problems or theorems will be off, but we always refer to them by name, so you can find all the information you need.

Optional Materials

Extra textbooks (that I get problems from, sometimes)

These books are available as PDF free online.

Technology Requirements

Hardware 

NC State’s Online and Distance Education provides technology requirements and recommendations for computer hardware. 

Software

All technologies that students will need to fully participate in your course. Include a statement of its purpose. Provide information on how to obtain or access software. Also, include a link to the accessibility statement and privacy policy.

It is recommended that for Zoom meetings, you have a camera and it is on.

Minimum Computer and Digital Literacy Skills

  • Obtain regular access to a reliable internet connection 
  • Proficient typing and word processing skills (MS Word, text editors, Google Docs)
  • Ability to use online communication tools, such as email (create, send, receive, reply, print, send/receive attachments), discussion boards (read, search, post, reply, follow threads on Ed), chats, and messengers.
  • Use of Moodle
  • Download and upload attachments
  • Knowledge of copy/paste and use of spell check
  • Use computer networks to locate and store files or data
  • Internet skills and ability to perform online research using various search engines and library databases. Visit Distance Learning Services at NC State Libraries for more information.

Netiquette

Netiquette is the term used to describe the special set of rules for online communication. We will be using Ed as our discussion forum and for many announcements. This is the best way to ask and answer questions about the class.

Students should be aware that their behavior impacts other people, even online. I hope that we will all strive to develop a positive and supportive environment and will be courteous to fellow students and your instructor. Due to the nature of the online environment, there are some things to remember when engaging with others.

Tips for Success

  • Do: Follow the same standards of behavior that you subscribe to offline.  Keep in mind that all online communication is documented and therefore permanent.
  • Don’t: Flame others in discussion forums.  Flaming is the act of responding in a highly critical, sarcastic, or ridiculing manner – especially if done on a personal level.  Remember that these discussions are meant for constructive exchanges and learning!
  • Don’t: Go for long periods of time without communicating to your instructors or classmates. It is important to stay a part of the online community!
  • Do:  Remember to read over your posts before selecting “Submit.”
  • Don’t: Use slang, poor grammar, and other informal language in discussion forums or email messages to instructors or classmates.

Grading

Grading Policy

Your grade is per mil (out of 1000). See the breakdown below.

For example, a 92.7/100 is an A- on our scale, so if you earn 927/1000 points, you get an A-. (No rounding!)

# assignmentstotal valuevalue perNotes
Quiz1035050you can drop 3
MCQ homework129010you can drop 2
PS315050
Oral Homework321070
Final Exam1200200

Minimum Grade Requirement

Scoring <60% on the final results in an F in the course.

Grading Scale

This course uses this grading scale: 

LowLetterHigh
97 ≤A+≤ 100
93 ≤A < 97
90 ≤A- < 93
87 ≤B+ < 90
83 ≤B < 87
80 ≤B- < 83
77 ≤C+ < 80
73 ≤C < 77
70 ≤C- < 73
67 ≤D+ < 70
63 ≤D < 67
60 ≤D- < 63
0 ≤F < 60

Course Schedule

Check the Google sheets link or the Google calendar for an external view.

Course Policies

Late Assignments

  • Late assignments will be accepted with 5 points taken off for every day submitted late. Assignments submitted later than two days past the original due date will NOT be accepted.

Incomplete Grades

It is the student’s responsibility to work with the instructor to create a schedule to complete the class, in the event that an incomplete is warranted.

Attendance and Participation

Please review NC State’s Attendance Policy: https://policies.ncsu.edu/regulation/reg-02-20-03-attendance-regulations/ and the Withdrawal Process: https://studentservices.ncsu.edu/your-classes/withdrawal/process/

I do not mandate attendance, but I do note it. You may be referred to academic advising or CARES in the event that I believe you have excessive absences.

We have (near) weekly quizzes, in-class, that do not have make-ups. Thus, you can miss up to 3 Wednesdays with no penalty.

University Policies

Academic Integrity and Honesty

Students are required to comply with the university policy on academic integrity found in the Code of Student Conduct. Therefore, students are required to uphold the university pledge of honor and exercise honesty in completing any assignment. 

Please refer to the Academic Integrity web page for a detailed explanation of the University’s policies on academic integrity and some of the common understandings related to those policies.

Students may be required to disclose personally identifiable information to other students in the course, via electronic tools like email or web-postings, where relevant to the course. Examples include online discussions of class topics and posting of student coursework. All students are expected to respect the privacy of each other by not sharing or using such information outside the course.

Students are responsible for reviewing the NC State University PRR’s which pertains to their course rights and responsibilities:

Students with Disabilities

Reasonable accommodations will be made for students with verifiable disabilities. In order to take advantage of available accommodations, students must register with the Disability Resource Office at Holmes Hall, Suite 304,Campus Box 7509, 919-515-7653 . For more information on NC State’s policy on working with students with disabilities, please see the Academic Accommodations for Students with Disabilities Regulation (REG02.20.01) 

Trans-Inclusive Statement

In an effort to affirm and respect the identities of transgender students in the classroom and beyond, please contact me if you wish to be referred to using a name and/or pronouns other than what is listed in the student directory.

Basic Needs Security

Any student who faces challenges securing their food or housing or has other severe adverse experiences and believes this may affect their performance in the course is encouraged to notify the professor if you are comfortable in doing so. Alternatively, you can contact the Division of Academic and Student Affairs to learn more about the Pack Essentials program https://dasa.ncsu.edu/pack-essentials/

Course Evaluations

ClassEval is the end-of-semester survey for students to evaluate instruction of all university classes. The current survey is administered online and includes 12 closed-ended questions and 3 open-ended questions. Deans, department heads, and instructors may add a limited number of their own questions to these 15 common-core questions.

Each semester students’ responses are compiled into a ClassEval report for every instructor and class. Instructors use the evaluations to improve instruction and include them in their promotion and tenure dossiers, while department heads use them in annual reviews. The reports are included in instructors’ personnel files and are considered confidential.

Online class evaluations will be available for students to complete during the last two weeks of the semester for full semester courses and the last week of shorter sessions. Students will receive an email directing them to a website to complete class evaluations. These become unavailable at 8am on the first day of finals.

Syllabus Modification Statement

Our syllabus represents a flexible agreement. It outlines the topics we will cover and the order we will cover them in — but minor changes can be made. Dates for assignments represent the earliest possible time they would be due. The pace of the class depends on student mastery and interests. Thus minor changes in the syllabus can occur if we need to slow down or speed up the pace of instruction.

Back to Top