General Course Information | What this Course is About | Required Background | Textbook |

Required Work | Grading | The laptop-free
classroom |
Detailed Course Schedule |

Instructor:

Howard Straubing

Computer Science Department

251 St. Mary's South

tel.:617-552-3977

e-mail: straubin@cs.bc.edu

Office Hours: TuTh 2-4

#### Teaching Assistants:

Shikun (Jason) Wang (wangapb@bc.edu) OH: TuSa 2-4.

Marina Thetford (thetford@bc.edu) OH: M2-3 Sa noon-2

Will Bullock (bullockw@bc.edu) OH: Su noon-2.

#### Meeting Times:

Both sections meet Monday, Wednesday and Friday in Fulton
415, Section 1 at 1:00 and Section 2 at 2:00.

## What this Course is About

CSCI2243, Logic and Computation is one of two courses, required
of all Computer Science majors, designed to provide you with the
mathematical background you will need for upper-division courses
in the field. Ideally, this course and its companion, CSCI2244,
Randomness and Computation should be taken by CS majors by the
end of their sophomore year, although of course some students
will not complete it until somewhat later. It is strongly
recommended that you take CSCI2243 before CSCI2244.

CSCI2243 is devoted to the role played in computer science by logic, understood both narrowly (formal logic, mathematical models of computation) and broadly (abstract mathematical structures such as sets, functions, relations; basic number theory and techniques of mathematical proof). A complete list of topics can be found in the detailed course schedule below.

While this is in many respects a mathematics course, I will emphasize the relevance and applications to computer science throughout the semester. In addition to solving pencil-and-paper problems and reading and writing proofs, you will experiment with some software tools, like digital logic simulators and satisfiability solvers, that are built on the mathematical principles we study in the course, and you will also be asked to write a bit of code.

###

## Required Background

You should be comfortable with high-school
mathematics at the pre-calculus level, especially reading
and writing algebraic notation. Strictly speaking, you
do not need any calculus (although you do for
CSCI2244), but most of you have taken a calculus course by
now, and I may occasionally make reference to some topics
typically studied in a calculus course in the explanations
and examples.

You should also have some programming experience. All the code samples and programming problems will be in the Python programming language. Most of the students in the class will have already taken CSCI1101 in Python. For those who have not, the rudiments of Python can be picked up rapidly if you have programmed in another procedural language (like Java, C, or C++).

### Note for dual Math/CS majors:

## Textbook

#### Help us make this book better!

## Required Work

### Homework

As mentioned above, this will look and feel very much like a
math course. There will be weekly homework
assignments. A certain amount of drill-work is
unavoidable, and some of it can be pretty dry. (You just
have to learn this stuff.) Some of the homework problems
will involve programming or other use of software tools, to
stress the applications of the mathematical material.

All the assignments will be posted on this website, and submitted through the Canvas site for this course. The assignments are due by 11PM on the due date.

Your assignment must be submitted electronically, and it must be typed. Typing an assignment with a lot of math in it can be a chore, but electronic submissions of photographs of handwritten work have proved too difficult to read. There are several methods you can use to prepare the assignment.

When you have completed Assignment*n*, you should
place all the files in a folder named

`First Name_Last Name_Assignment_n`

(Please use your full first and last name, as they appear on the registration documents.) For instance, if Igor Eagle were a student in the course, he would name the folder for the first assignment Igor_Eagle_Assignment_1. Compress the folder to produce a .zip file, and then upload this through the submission portal on Canvas. Do not submit assignments as attachments to e-mail messages, and do not submit a bunch of separate files that have not been bundled in a folder.

Late homework will not be accepted, except in rare
instances that have been cleared with me prior to the due date.
The assignments themselves will be posted on the course website,
and the solutions on the Canvas site.

**Quizzes **

At least once a week, I will give an in-class exercise or a
quiz. These will all be posted as quizzes on Canvas,
however only the actual quizzes will generate a grade that will
be figured into your average. For the in-class exercises,
you will just receive an attendance grade for submitting the
work. (This is, among other things, a sneaky way to introduce a
*de facto *attendance requirement without officially
requiring attendance.)

### Exams

There will be an in-class midterm exam in on Friday, October 6 (a day that I will not be present), another before Thanksgiving, and a final exam at the times scheduled by the registrar for classes in the time slot of your section: Wednesday, December 13 at 9:00 for the 1:00 section, and Tuesday, December 19 at 9:00 for the 2:00 section. I would much prefer to have a common final exam for the two sections, but the registrar will not permit this.**You must take the final for the section you
are registered for. **

### Academic Integrity

While I encourage you to discuss homework problems both among
yourselves and with me, when
it comes to finally sitting down and preparing the completed
assignment, you are required to work alone. Thus
it is acceptable to learn from another student the general idea
for writing program code to perform a particular task, or the
technique for solving a mathematical problem, but unacceptable
for two students to prepare their assignments together and
submit what are essentially two copies of identical work.
If you have any uncertainty about the application of
this policy, please check with me.

It is also acceptable to consult other sources than the course textbook. You may very well find the idea for solving a problem (or, in some cases, even the solution itself) in something you read. If that is the case, please let me know what you have found and where you found it. Generally speaking, it is okay to incorporate an idea that you discovered elsewhere into your work (but please check with me first, and cite your source), but it is plagiarism to copy a significant portion of what you find and present it as your own work.

Failure to comply with these guidelines will be considered a violation of the University policies on academic integrity. Please make sure that you are familiar with these policies.

### Eyes Front!

## Grading

To be eligible for a passing grade in this course, you
must complete at least 60% of the assignments in a satisfactory
manner. Your grade will then be computed from your performance
on assignments, quizzes and midterms, and final exam. The
assignments will account for about 40% of the grade, the
midterms, quizzes and in-class activities for about 30%, and the
final exam for about 30%. (These ratios are subject to
minor adjustments, hence all the "abouts".)

## Detailed Course
Schedule

This grid will grow and change as the semester progresses.The
list of topics is basically accurate, but the dates, if they are
more than two weeks out from when you are looking at this site,
are only a guess.

Howard Straubing

Computer Science Department

251 St. Mary's South

tel.:617-552-3977

e-mail: straubin@cs.bc.edu

Office Hours: TuTh 2-4

TAs hold office hours in Fulton 160.

Shikun (Jason) Wang (wangapb@bc.edu) OH: TuSa 2-4.

Marina Thetford (thetford@bc.edu) OH: M2-3 Sa noon-2

Will Bullock (bullockw@bc.edu) OH: Su noon-2.

CSCI2243 is devoted to the role played in computer science by logic, understood both narrowly (formal logic, mathematical models of computation) and broadly (abstract mathematical structures such as sets, functions, relations; basic number theory and techniques of mathematical proof). A complete list of topics can be found in the detailed course schedule below.

While this is in many respects a mathematics course, I will emphasize the relevance and applications to computer science throughout the semester. In addition to solving pencil-and-paper problems and reading and writing proofs, you will experiment with some software tools, like digital logic simulators and satisfiability solvers, that are built on the mathematical principles we study in the course, and you will also be asked to write a bit of code.

You should also have some programming experience. All the code samples and programming problems will be in the Python programming language. Most of the students in the class will have already taken CSCI1101 in Python. For those who have not, the rudiments of Python can be picked up rapidly if you have programmed in another procedural language (like Java, C, or C++).

If you are majoring in both Mathematics and Computer Science,
you are not required to take CSCI2243, because of the large
overlap between this course and MATH2216: Introduction to
Abstract Mathematics. There is some important
material in Logic and Computation, particularly that
concerning propositional and predicate logic, finite-state
machines and Turing machines, that is *not* covered in
MATH2216, and you may want to study some of this on your own
in case you find it used in a subsequent upper-division CS
course.

In 2014, Boston College created the Affordable Course
Materials Initiative, to address the problem of the high
cost of college textbooks. It has been found time and again
that students often do not buy the required course books, and
frequently complain that when they do buy them, their
instructors only use a small fraction of the required
materials. The Provost's office awarded grants to a
number of faculty members to develop new minimal-cost
materials for their courses. Prof. Sergio Alvarez and I
received one of the first grants for our collaboration on a
free electronic textbook for CSCI2243 and CSCI2244.

The CSCI2243 book is in the form of a PDF file, and you
should be able to read it either on a computer screen or a
tablet computer. (Or, for that matter, a smartphone, but I
don't recommend it.) If you prefer hard-copy, it is up to you
to do the printing and binding (which will still be much
cheaper than a conventional book.) There are links within the
text both internally, to direct you to other portions of the
book, and externally, to direct you to websites.
The entire book, in its 2016 version, is posted at the Canvas
site for this course. There will be some updates and
revisions posted during the semester.

Your feedback is encouraged, and as a reward for your
collaboration, I will award **2 homework points** (one
assignment = 100 homework points) for each typographical error
you call to my attention, and **8 homework points** for
each mathematical error (of which I hope there are
none). Only the first person to spot an error will
receive the reward, and I will be the final judge of what
constitutes an error. I should point out that the same
reward was offered to students each of the last two
years. They found dozens of errors, and reaped
substantial rewards. I hope that the pickings are slimmer this
year!

Many things that are not actually errors--infelicitous turns
of phrase, obscure explanations, missing examples, etc.---are
likely to be more serious problems than typos. Feel free
to weigh in on these as well. (In this case, your reward
is the satisfied feeling this will bring you.)

All the assignments will be posted on this website, and submitted through the Canvas site for this course. The assignments are due by 11PM on the due date.

Your assignment must be submitted electronically, and it must be typed. Typing an assignment with a lot of math in it can be a chore, but electronic submissions of photographs of handwritten work have proved too difficult to read. There are several methods you can use to prepare the assignment.

- Use the equation editor in Microsoft Word. This
produces acceptable results, and can be mastered very
quickly.

- Use the mathematical typesetting system LaTeX (which was
also used to produce the textbook). This is far more
flexible and gives prettier results, but it has a steeper
learning curve. I will point you toward tutorial materials
that should help you pick up the basics quickly. LaTeX has
become something of a standard for the production of
technical articles across a very wide array of fields, so it
is well worth putting in the effort to learn it.

- Diagrams pose a special problem. If you want to take the
time to do it, you can prepare drawings with a program like
Power Point or Keynote, convert these to image files, and
either paste the image into a Word document or include it
using the \includegraphics command in a LaTeX
document. Alternatively, you can take a photograph or
make a scan of a hand drawing and produce an image file,
which you can submit along with your assignments.

When you have completed Assignment

(Please use your full first and last name, as they appear on the registration documents.) For instance, if Igor Eagle were a student in the course, he would name the folder for the first assignment Igor_Eagle_Assignment_1. Compress the folder to produce a .zip file, and then upload this through the submission portal on Canvas. Do not submit assignments as attachments to e-mail messages, and do not submit a bunch of separate files that have not been bundled in a folder.

Late homework will not be accepted

There will be an in-class midterm exam in on Friday, October 6 (a day that I will not be present), another before Thanksgiving, and a final exam at the times scheduled by the registrar for classes in the time slot of your section: Wednesday, December 13 at 9:00 for the 1:00 section, and Tuesday, December 19 at 9:00 for the 2:00 section. I would much prefer to have a common final exam for the two sections, but the registrar will not permit this.

It is also acceptable to consult other sources than the course textbook. You may very well find the idea for solving a problem (or, in some cases, even the solution itself) in something you read. If that is the case, please let me know what you have found and where you found it. Generally speaking, it is okay to incorporate an idea that you discovered elsewhere into your work (but please check with me first, and cite your source), but it is plagiarism to copy a significant portion of what you find and present it as your own work.

Failure to comply with these guidelines will be considered a violation of the University policies on academic integrity. Please make sure that you are familiar with these policies.

My colleague Bob Muller calls this policy the 'laptop-free
classroom'.

A successful class requires your attention, engagement, and
participation. You need to be prepared to ask and answer
questions during the lectures, and to attend to the questions
and answers of your fellow students and of the
instructor. That screen open to your e-mail or Facebook
page distracts not only you, but the students sitting behind
you. For this reason, *open laptops are not permitted in
the classroom*, except during quizzes and in-class
activities that require their use.

You say you're taking *notes* on that laptop instead of
shopping on Amazon? You should be aware that (a) it is very
difficult to take notes for this class on a computer, given
the large number of mathematical symbols, formulas and
diagrams that we use; and (b) taking
notes by hand is better for you. It is acceptable
to take notes on a tablet computer with a stylus.

And while we're at it, put your phone away, too.

Week |
Topic |
Handouts and Readings |
Homework |

August 28-September 1 |
Propositional Logic |
What the well-dressed homework assignment is wearing
these days. I've provided the solution to
the kind of problem you would expect to see on the first
assignment, using two different software tools. MS Word
requires no special training: Just select
'Equation' from the Insert menu and start playing
around. LaTeX has a much steeper learning curve.
(The problem and its solution are also instructive.)---Using the equation editor in Microsoft Word (I've supplied the .docx file so you can play with it.) ---Using LaTeX (pdf output) (.tex source) Resources for learning LaTeX : The not-so-short introduction to LaTeX Wikibook on LaTeX The Wason card experiment from the quiz. The second slide shows the identical logic problem presented in the context of policing a social rule. Wikipedia page on the Wason card experiment. Results: 83 students took the quiz. 27% answered the Wason card question correctly. This is actually quite a lot larger than the results reported in the psychology literature on the test, where typically fewer than 10% of respondents answer correctly. Only 11% of the students answered the leap year question correctly. Interestingly, the performance of the two sections on the two parts of the quiz were opposite---the 2:00 section did much better on the Wason cards, much worse on the leap years. The soup-and-salad saga as an Excel spreadsheet. The September 1 quiz, with solutions and results. |
Assignment
1, due Wednesday, September 6. (for those interested in using LaTeX), the LaTeX source for Assignment 1. |

September 6-8 (No class on Labor Day, September 4) |
More Propositional Logic, Digital Circuits |
Stuff you'll need: Download the Logisim software If you get messages telling you that you have the wrong Java runtime for running Logisim, you might be able to solve it by downloading the Logisim .jar file instead. sat4j.jar (the satisfiability solver--download this to your course folder) satsolve.py (Python interface to sat4j) eightqueens.py (Encodes the Eight Queens puzzle in CNF and solves it using the Python interface to sat4j.) |
Assignment
2, due September 14. LaTeX source for Assignment 2 Logisim circuit file for use with this assignment (you will add more circuits to this.) schedule.py (Python program for generating the specification and solution of the scheduling problem. You will add some code to this.) |

September 11-15 |
Digital Circuits,
Puzzles, Satisfiability Solvers; Sets and Functions |
The
September 11 quiz, with solutions and results. |
Assignment
3, due September 22. LaTeX source for Assignment 3. |

September 18-22 |
Sets and Functions |
||

September 25-29 |
More Sets and Functions |
||

October 2-4 |
Predicate Logic |
||

October 6 |
First Midterm |
||

October 11-13 (no class on Columbus Day, October 9) |
Relations. Proofs |
||

October 16-20 |
Proof by Induction |
||

October 23-27 |
More Induction |
||

October 30-November 3 |
Number Theory |
||

November 6-10 |
More Number Theory,
Finite State Machines and Regular Expressions |
||

November 13-15 |
Finite State Machines,
Turing Machines and Computability |
||

November 17 |
Second midterm |
||

November 20 (no class on Thanksgiving break, November 22-24) |
Turing Machines and Computability |
||

November 26-December 1 |
Turing Machines and Computability |
||

Decmber 4-6 |
Turing Machines and
Computability |
||

December 8 |
Wrap-up and review |
||