Department of Computing and Information Science
Queen's U.


Course Description - Winter 2017

Classes Instructor and TAs Textbook Lecture Topics
Assignments Tests and Exams Grading Software


March 23
The midterms will be returned in class tomorrow Friday. Sample solutions are here.

March 20
The eight assignment has been posted on the assignments page. Assignment 8 is due by 3:30 PM on Thursday March 30.

March 8
The seventh assignment has been posted on the assignments page. Assignment 7 is due by 3:30 PM on Thursday March 23.

Announcements concerning the course will be posted above and you are expected to check this page frequently.


Slot 4 Tuesday 8:30 AM Wednesday 10:30 AM Friday 9:30 AM

Classes are in Slot 4, meeting in Stirling Auditorium, campus map


Teaching Assistants

Note: TA office hours begin the week of Jan. 16th.

TA office hours are for tutorial help with course material and assignments, and discussions of assignment grading.

If you need additional help, please see the COMPSA web page.

Required textbook

The textbook is available at the campus bookstore. Information can be found here for CISC and here for CMPE.

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

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 the notes for each week.

Note: The purpose of the posted outlines is to assist you in taking notes in class. Reading the posted notes is not a substitute for attending the classes. In particular, most of the examples we go over in class are not included in the posted outlines.

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 9 small assignments, due on Thursdays of Weeks 2, 3, 4; 6, 7, 8; 10, 11, 12.
The assignments contribute a total of 20% to your course mark. Your assignment mark is computed as the sum of your best 8 assignment marks (out of the total of 9 assignments). That is, each of your 8 best assignments contributes 2.5% to your course mark.

The assignment questions (and their solutions after the due date) will be posted on the assignments page.

Each assignment should take less than an hour to complete, assuming that you have attended the classes and reviewed the relevant material.


If the submission consists of several pages, the pages must be stapled together.

The marking scheme is the same for groups of sizes 1, 2, 3 or 4.

You are encouraged to work together with a group since often it is easier to learn new theoretical concepts by interacting with others. You may learn more if you work with smart people but, in any case, the intention is that all people in a group should be involved in creating the solution. You can, of course, choose to sign an assignment you haven't done, but then you risk not learning the material. In the exams you will be required to solve similar problems by yourself.

Note: You are asked to write your assignment solutions using non-erasable pen (or to type the solutions). Solutions written in pencil or erasable ink will be marked, but they will not be considered for remarking after the assignments are returned.

If you have questions concerning assignment marking, you should discuss them with the TA who did the marking within one week from the time when the marked assignments are made available. All assignment marks are considered final after that time.
If you cannot attend the office hours of the TA, please fill out the form here. Place the form and your assignment in an envelope and hand it to the instructor in class or to any of the TAs within one week after the marked assignments were returned in class.

Late Assignment Penalty

Late assignments will be accepted up to 24 hours after the assignment is due. A late assignment will have deducted a penalty of 15% of the maximum mark.

Late assignments should be put into the same locked CISC 223 drop-off box on the second floor of Goodwin hall (near rooms 233, 241).

An assignment which is more than 24 hours late will not be accepted.

Tests and Exams

There will be two 40 minute midterms during the class hour on Each midterm is worth 15% of the course mark. The midterms are closed book exams. You may bring one 8.5" x 11" page of notes to the midterm exam.

The final exam will be held during the regular Winter term final examination period. The final is a 3 hour closed book exam. You may bring one 8.5" x 11" sheet containing notes and use it during the final exam.


Your grade is calculated as follows (with the two modifications listed below):

1st Midterm 15%
2nd Midterm 15%
(best 8 assignment marks)
Final exam 50%
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.


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 zeus server which runs Solaris (a commercial version of Unix, fairly similar to Linux). This is accessible from workstations in the CASLab.

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: