Instructor: Prof. Arkady Yerukhimovich
Email: arkady@gwu.edu
Prerequisites: Software Engineering (CS 2113); and Discrete Structures II (CS2312) or Introduction to Computer Systems (CS 2460) or Computer Architecture (CS 2461) (See undergraduate curriculum).

Time/Place:

  • Class meets: Tuesday, Thursday 11:10am - 12:25pm in SEH 1300, 1400, and 1450

Office Hours:
Check Course Homepage for updated hours.

Online Platforms

  • Piazza for discussions
  • Gradescope for homework submission and grades
  • Blackboard for synchronous lectures and recordings
  • Webpage for lecture slides, tutorials, and other materials

Course Staff:

Course Description and Learning Outcomes

This is a core undergraduate Computer Science course on the theory of computing. The course introduces the foundations of computer computer science including questions such as “what is computation”, “what are the mathematical models of computing machines”, “what is a computable problem”, and “what is efficiently computable”. The course covers these questions and in the process introduces important concepts such as Turing machines, formal languages, models of automata, and an introduction to complexity theory. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical abstraction and problem solving skills. The lecture, and some lab sessions, will consist of in-class activities and students will be required to work in groups.

By the end of this course, students will be able to:

  • Understand key concepts in the theoretical foundations of computer science including: automata models such as finite state automata, pushdown automata and Turing machines; formal languages and grammars including regular languages, and context free grammars; Turing computability and the language hierarchy, and computational complexity.
  • Identify relationship between languages and computability including the language/machine hierarchy.
  • Develop problem solving skills and proof techniques.
  • Develop the ability to abstract computational problems, and construct mathematical models (and proofs) to determine complexity and limits of machine models.
  • Understand the concept of unsolvable and solvable problems, as well as efficiently solvable and unsolvable problems and develop skills to prove hardness of problems.

Course Outline

  • See the course webpage for weekly schedule

Textbook and Resources

There are three options for a textbook; the instructor recommends the book by Sipser, but all three books will have relevant material for review. The textbooks are NOT required, but can be beneficial for additional reading.

Lab Sections

You must be registered in a lab section – the sections meet on Wednesday 10:00am and 11:15am. These will be conducted by the TAs. The labs will review material but will also include exercises, quizzes and discussions.

Workload and Grading

The course will be taught through live synchronous lectures. As a 3 credit course, it will require a minimum of 2.5 hours per week of direct instruction and minimum of 5 hours of independent learning. In addition, the laboratory section will require 75 minutes of direct instruction and will include independent learning exercises to assist in your learning. Over the course of the semester, your independent learning will include readings (lecture notes and/or textbook), and homeworks. The lectured will include presentation of material, exercises, and discussions. All lectures will be recorded, and recordings will be provided on blackboard.

Grading:

  • 20%: Class participation The class participation grade will consist of the following:
    • Discussion participation: Students are expected to actively participate in lectures and lab by asking questions and engaging in discussion, as well as in online discussion through Piazza. Your level of engagement will be reflected in the participation grade.
    • In-class quizzes: Quizzes will be held either during the lab or during the lecture session. Late arrival means you may miss the quiz - no extra time will be provided for those who arrive late. On average there will be a quiz scheduled approximately every week except during the weeks of the two exams and the first week of class.
    • Lab exercises: There will be required in-class (group) exercises during the lab or lecture sessions. Participation in and submission of these exercises will count towards your participation grade.

  • 30%: Homeworks. A number of homework assignments will be given. The goal of the homework is to improve your learning of the concepts covered in the lectures. No collaboration of any kind on the homework. The lowest homework score will be dropped when computing the grade.

  • 50%: Three exams.
    * There will be two (midterm) exams, one covering regular languages, finite automata, context free languages and push-down automata; and the other covering computability theory. The final exam will be comprehensive but will focus mostly on content after the second midterm exam. The exams will be worth 20% each with the exam on which you receive the lowest score counting for only 10%.

Final Grading

  • Do I curve the grades? Yes.
  • Grades will be based on the ‘weighted total’ after curving and scaling, where the weights for each category are shown above - normalization places your total as a percentage of the highest total in the class, and curving identifies clusters.
  • Grades in each category and your weighted total will be posted on blackboard.
  • Grades are skewed toward the higher end if course average (or median) is high and skewed towards lower if they are low.
  • Grades are then approximately (since they will depend on the final distribution, including median score) assigned in the following ranges when the assumption is that the normalized average or median is around 78-80. Grades are skewed toward the higher end if average is higher and skewed towards lower if average is lower.
Percentage Letter grade
90-100 A range (A- to A)
80-89 B range (B- to B+)
70-79 C range (C- to C+)
60-69 D range (D- to D+)
below 60 F

Course Policies

If you have a disability, or a health or a family emergency, that may effect your participation in this course and wish to discuss academic accommodations, please contact me as soon as possible.

Late work policy: There are no late submissions allowed in this course. The only exception to this rule is if you have a medical or family emergency, and you should contact the instructor or the TA before the due date.

Grades will be posted on Blackboard – make sure you check and inform the instructors (by email) if you see any disparity between what is posted on blackboard and what you think your grades are. You have one week after the grades are posted to contact the instructor – after that there will be no regrading.

Email policy: You can send email to my GW email address. However, do not expect an instantaneous response. We encourage you to post questions on Piazza since that will be monitored by the entire instruction team and your classmates.

Illness policy: If you are ill and it will cause you to miss class, lab, or an assignment, you should let me know in advance if possible. I cannot extend deadlines unless you contact me. You are still responsible for all material you missed, which generally will be available on the course website or on blackboard.

Academic Integrity policy: It is very important in this course (and in life), that your work be your own. These guidelines will help you achieve that.

You must:

  • Do your best to solve all homework, quizzes, and exams on your own.
  • Notify me if you are using a tutor (this is not a problem, just let me know).

You may:

  • Discuss general approaches to solving the homework problems with other students by referring to questions in the textbook.
  • Discuss general mathematical concepts (proof techniques, formalisms, etc.) with another student although it is recommended that you contact one of the TAs or LAs for this purpose.

You may not:

  • Copy homework solutions from other students or people (or places/web) outside of the class.
  • Have someone else complete your homework for you.
  • Copy solutions from the internet.
  • Write solution as a group and then submit identical or slightly modified versions—if you discuss general approaches to solving a problem together, you still must be writing up your own independent solution.

The Academic Integrity Code will apply to this course. Please read through the code carefully. Penalties for violating the code or the policies described here include failing this course, and are elaborated in the GW Academic Integrity Code. Note that the minimum punishment is failure of the assignment.

Support for students outside the classroom.

  • Academic Commons. Academic Commons provides tutoring and other academic support resources to students in many courses. Students can schedule virtual one-on-one appointments or attend virtual drop-in sessions. Students may schedule an appointment, review the tutoring schedule, access other academic support resources, or obtain assistance at academiccommons.gwu.edu.
  • Disability Support Services (DSS) 202 994 8250. Any student who may need an accommodation based on the potential impact of a disability should contact Disability Support Services to establish eligibility and to coordinate reasonable accommodations. disabilitysupport.gwu.edu
  • Counseling and Psychological Services. 202 994 5300. GW’s Colonial Health Center offers counseling and psychological services, supporting mental health and personal development by collaborating directly with students to overcome challenges and difficulties that may interfere with academic, emotional, and personal success. See Health Center.