Department of Computing and Information Science
Queen's U.


Course Description - winter 2021

Textbook Instructor and TAs Goals of the Course Lecture Notes Assignments Grading Software

Required textbook

Supplementary reading

Suggested additional reading may be found in the Introductions to Parts A and C and in the additional-reading section at the end of every chapter in the text.

There are many textbooks covering the material in the first half of the course (Part C in our textbook).


Teaching assistants: For information on the teaching assistants please login to your CISC223/CMPE223 onQ page.

Goals of the course

The first part of the course provides an introduction to several conceptual tools that are widely used in computing: state diagrams, regular expressions and context-free grammars. In the second part you will learn to verify the correctness of (small) programs using logic based techniques. This part of the course builds on material you have studied, for example, in CISC 204. Additionally, we will briefly discuss the theoretical limits of algorithmic computation.

Learning Outcomes

Academic Integrity

Please see a Statement on Academic Integrity from the Arts and Science web site posted here.

Lecture topics and notes

Class note outlines will be posted on the lecture notes page. A reference to the corresponding chapter in the textbook can be found at the begin of each section of the notes.

The material in the text will be discussed in order: Part C, Part A, Part D. We will not have time to cover the material in Part B.


There will be 5 sets of assignments due during Thursdays of weeks 3, 5, 8, 10, 12. The assignment questions will be posted at the CISC223/CMPE223 onQ page.
The assignments must be based on individual work. Each assignment is worth 9% of your course mark.

The assignments are submitted in onQ (file submission). Assignments sent by email are not accepted.

Note - important: There are different variants of the assignment questions. You must answer the assignment questions that you can access by login to your own onQ page. Answering questions that are different from those posted on your own onQ page results in zero marks (and may be a violation of academic integrity).

Quizzes and final exam

There will be two quizzes held during the term on Thursday February 25 and Thursday March 18. Each quiz has a time limit of 2 hours. The first quiz is worth 15% and the second quiz 20% of your course grade.

The final exam will be held during the regular winter term final examination period. The final exam is 3 hours in length.


Your grade is calculated as follows.

5 Assignments
(each assignment worth 9%)
2 Quizzes
(1st quiz is worth 15% and 2nd quiz 20%)
Final exam 20%
Total: 100%

Note: The components of this course will receive numerical marks that will be used to calculate a percentage final grade, as explained above. The final grade you receive for the course will be derived by converting your percentage grade to a letter grade according to Queen's official grade conversion scale.

Note2: The individual grade items (for the assignments and quizzes) will be posted on the onQ page where you can check them. However, your percentage grade for the entire course will be calculated using a spreadsheet outside onQ.

Accommodations Statement

Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at:

Academic Consideration for Students in Extenuating Circumstances

The Senate Policy on Academic Consideration for Students in Extenuating Circumstances ( was approved in April, 2017. Queen's University is committed to providing academic consideration to students experiencing extenuating circumstances that are beyond their control and which have a direct and substantial impact on their ability to meet essential academic requirements. Each Faculty has developed a protocol to provide a consistent and equitable approach in dealing with requests for academic consideration for students facing extenuating circumstances. Arts and Science undergraduate students can find the Faculty of Arts and Science protocol and the portal where they submit a request at: Students in other Faculties and Schools should refer to the protocol for their home Faculty.


Programming Language

A small fragment of the C programming language is used in the text. A compact reference manual may be found in Appendix A of the text book and
on-line as a PDF file.

The text assumes that a file specdef.i of "headers" and definitions has been included into all programs; this is Program 3 on page 7 of the text.

An on-line reference manual on C programming:

Programming Platforms

Any implementation of C (or C++) may be used, but for this course we recommend an interpretive implementation of C called EiC. Although its run-time performance is relatively poor (comparable to Java), it has good error messages and run-time checks.

EiC has been installed on the CASLab Linux servers and workstations. For more information about accessing CASLab Linux, consult the CASLab How To.

To use EiC to parse and run a C program file prog.c in the current directory, just enter a

eic prog.c
at a command-line prompt. Use re-direction to read from a file input or to write to a file output, as in
eic prog.c < input > output
To get a summary of available command-line options and directives, enter
eic -h
For more details see the link EiC.

The following on-line tutorials will be useful if you are unfamiliar with Unix-like systems:

Several other free C or C++ implementations which may be of interest are available:

Program Editors

Any text editor (such as Notepad on Windows) may be used to create and modify C programs. We suggest you use one window as a command-line interface (running EiC as necessary), and a separate window (or windows) to edit C source files.

On Unix-like systems such as Solaris and Linux, the most popular text editors are vi (or an improved version such as vim) and emacs (or an improved version such as xemacs); but if you are not familiar with either of these, we advise you to use nedit at a GUI (graphical user interface) and jed at a CLI (command-line interface).

An "integrated development environment" (IDE) combining a program editor, a compiler or interpreter, and possibly a debugger, won't be needed for the relatively small and, one hopes, verified programs you will be coding in this course.

PDF Readers

Assignments and other documents posted at this web site will be in Portable Document Format (PDF). The CASLab computers you use should have PDF viewers installed.

If you want to install a PDF viewer on your own computer, viewers for most platforms are available at no charge here: