General Course Information  What this Course is About  Required Background  Textbook 
Required Work  Grading  The laptopfree
classroom 
Detailed Course Schedule 
TAs hold office hours in Fulton 160.
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, finitestate
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 upperdivision 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 minimalcost
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 hardcopy, 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 errorsinfelicitous 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.)
My colleague Bob Muller calls this policy the 'laptopfree
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 email 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 inclass
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 28September 1 
Propositional Logic 
What the welldressed 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 notsoshort 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 oppositethe 2:00 section did much better on the Wason cards, much worse on the leap years. The soupandsalad 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 68 (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 solverdownload 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 1115 
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 1822 
Sets and Functions 
A
sort of computerized 'proof' that certain sets are
countable 
Assignment
4, due October 1. LaTeX source for Assignment 4. 
September 2529 
More Sets and Functions 
Review materials for midterm Solutions to review questions 

October 24 
Predicate Logic 
Assignment
5, due October 19 LaTeX source for Assignment 5 

October 6 
First Midterm 
The exam, with
solutions. 

October 1113 (no class on Columbus Day, October 9) 
Relations. Proofs 
Assignment
6, due October 27 LaTeX source for Assignment 6 

October 1620 
Proof by Induction 

October 2327 
More Induction 
Some basic recursive functions, written in Python: Factorial, Fibonacci (a recursion disaster), Solution to the Towers of Hanoi puzzle. 
Assignment
7, due November 8 LaTeX source for Assignment 7 
October 30November 3 
Number Theory 
Some basic
numbertheoretic functions, written in Python (base
conversion, Euclid's algorithm): Recursive version Iterative version 
Assignment
8, due December 1 LaTeX source for Assignment 8 
November 610 
More Number Theory,
Finite State Machines and Regular Expressions 
Review Problems for
Second Midterm Solutions Errata for solutions (there was an error in the solution to 5(b)) Exam with solutions and results 

November 1315 
Finite State Machines,
Turing Machines and Computability 
Assignment
9,due December 9 LaTeX source for Assignment 9 

November 17 
Second midterm 

November 20 (no class on Thanksgiving break, November 2224) 
Turing Machines and Computability 
Python program for
Turing machine simulation. (This will also
draw state graphs for the input TM, which you can view
with GraphViz.) Specification of the TM that tests for equal numbers of a's and b's. Automatically generated state graph for this TM. 

November 26December 1 
Turing Machines and Computability 

Decmber 46 
Turing Machines and
Computability 

December 8 
Wrapup and review 
The
exam from 2015 The exam from 2016 some (hastily scrawled) solutions to the above Review summarynote that the problems given here, especially those concerning Turing machines, are more involved than typical exam problems. 
