UNIVERSITY OF PRINCE EDWARD ISLAND
Computer Science 4910
Introduction to Complexity Theory
May 2022
Title:   Intro to Complexity Theory
     
Instructor:   Cezar Câmpeanu
     
Email:   ccampeanu < at > upei < dot > ca
     
Office:   CASS 408
     
Tel:   (902)566-0485
     
Course web site:  

Go To: http://www.smcs.upei.ca/~ccampeanu,
and follow the links Teaching, and CS4910 under Spring 2022,
or
go to http://www.smcs.upei.ca/, Then follow the links: Faculty Members, Cezar Câmpeanu, Personal webpage(under Island Scholar Biography), Teaching, and CS4910 under Spring 2022.
     
General description:   This course introduces formal languages, computability, and complexity. Topics include: formal languages, computability, complexity related to various computability models
     
   

Topics of the course

  1. Mathematical Review
  2. Basic Concepts and Notations
  3. Formal languages; Chomsky hierarchy.
  4. Automata, Regular Expressions, and Regular Languages
  5. Rewriting systems
  6. Decidability, Computability, and Complexity
     
PREREQUISITE:   CS 2920 and Math 2420
     
    No prerequisite waiver for those who failed the above courses. Do not insist on circumventing the SMCS rules.
     
Essential to review:   elementary symbolic computation(logarithms, trigonomery, polynomials, matrices, exponentials), induction, derivatives, order relations, comparing real valued functions, graph theory.
     
Time and Location:   web/office
     
    This course is taking place on the traditional and unceded territory of the Lnu Epekwitk (Island Mi'kmaq), a district of Mi'kma'ki, the Mi'kmaq Nation.
     
ACADEMIC HONESTY:   This course is committed to the principle of academic integrity. Submitted work is expected to reflect an individual effort. Copying or cheating on assignments or tests will be dealt with harshly. Students should read Academic Regulation 20 in the UPEI Calendar at page 61 (http://files.upei.ca/calendar.pdf).
     
Avoiding Plagiarism:   The following link will help you identify and. avoid plagiarism http://resources.library.upei.ca/plagiarism/index.htm.
     
Individual Work Expectations:   You are expected to write your own code, your own proofs, your own examples, and so on. Unless explicitly specified in the assignment's text, the submitted work should be all yours.
     
Grading scheme:
Assignments Midterm Examination Final Project
35% 35% 30%
   
Course Resources:
  1. Assignment Policy
  2. Assignments
  3. Handouts
  4. Moodle login
   
Important Notices: Please, check course web site periodically for updates. For any problems concerning the CS4910 pages, please contact me.
   
To make sure you are viewing the most recent version of this page,press the shift key while clicking on the Reload button.
It is your responsibility to check this page for updates.
Last modified:Thursday November 17, 2022 at 08:45 pm AST
Cezar Câmpeanu