This course is required for all computer science  MAJ   majors and  MIN   minors.

This course is a follow up to a course in computer programming and would be of interest to students who want to pursue a degree in computer science or to those who are interested in learning foundational ideas in the science of computing.

Lab	In addition to classes, this course has one structured laboratory session per week.

Prerequisites:  COMP 1001, and COMP 1002 or Mathematics 2320

Availability: This course is usually offered on-campus in Fall and Winter semesters.

Course Objectives

The objective of this course is to provide an in-depth introduction to object-oriented programming in Python followed by an introduction to formal languages, automata, computability and intractability.

Representative Workload

• Assignments 10%
• Lab Quizzes 15%
• Midterm Exam 30%
• Final Exam 45%

Representative Course Outline

• Objects and Classes (15 hours)
• Introduction to objects and classes
  • Designing an implementing classes
  • Using objects
• Testing and Assertions
• Operator Overloading
• Inheritance and Polymorphism
• Operator overloading
• Sets and Dictionaries
• Theory of Computation (15 hours)
• Formal languages:
  • Alphabets
  • Strings
  • Languages as a sets of strings or sequences
  • Regular Expressions
• Automata
  • Deterministic Finite Automata and Non-deterministic Finite Automata
  • Converting regular expressions to NFA, subset construction of NFA to DFA
  • Context Free Grammars and Pushdown Automata
  • Turing Machines and Context Sensitive Grammars
• Computability
  • Halting Problem, Universal Turing Machine
  • Reductions and diagonlization
• Intractability
  
  • NP hardness, NP completeness, and languages outside NP

Notes

• This course requires programming in Python.