Instructor: Prof. Rebecca Hwa
Email: rebecca.hwa@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.

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 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.

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. 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.
    • One-on-one meetings: The instruction team will be holding 15-minute long one-on-one meeting sessions throughout the semester. At these meetings, you will be required to explain certain concepts (typically one of the questions from a previous quiz/lab exercise) to a member of the instruction team. We expect to hold sessions for 8-10 topics. Each session contributes to your participation grade, but you may miss up to two sessions overall.

  • 20%: 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. You must complete the homework on your own. The lowest homework score will be dropped when computing the grade.

  • 60%: 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.

Final Grading

  • The course grades will be curved.
  • 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 instruction team 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: Please send email to everyone on the instruction team. We will endeavor to get back to you quickly (within 24 hours of a work day), but you should not expect instantaneous responses.

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:

You must:

  • Do your best to solve all homework on your own first, seek allowable help only after you’ve thought about it for some time. You must enumerate all resources you referenced (even if briefly) – this includes websites, software, books, other people. In general, it’s better to over-include than under-include.
  • Complete quizzes and exams entirely on your own.

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 but we strongly recommended that you contact one of the TAs or LAs for this purpose.
  • Discuss general course concepts (not specific homework problems) with an AI assistant; however, you must review your session with the instruction team.

You may not:

  • Copy homework solutions from another person or place.
  • 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 (and don’t forget to list all your study partners as “resources”).

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.