|General Course Information||What this Course is About||Required Background||Textbook|
|Required Work||Grading||The laptop-free
||Detailed Course Schedule|
Alexandro Forte (firstname.lastname@example.org)
OH: M 9PM-midnight.
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, 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
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
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.)
My colleague Bob Muller calls this policy the 'laptop-free
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.
||Handouts and Readings
|August 28-September 1
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.
1, due Wednesday, September 6.
(for those interested in using LaTeX), the LaTeX source for Assignment 1.
(No class on Labor Day, September 4)
|More Propositional Logic,
|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.)
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.)
Puzzles, Satisfiability Solvers; Sets and Functions
September 11 quiz, with solutions and results.
3, due September 22.
LaTeX source for Assignment 3.
||Sets and Functions
sort of computerized 'proof' that certain sets are
4, due October 1.
LaTeX source for Assignment 4.
||More Sets and Functions
Review materials for midterm
Solutions to review questions
5, due October 19
LaTeX source for Assignment 5
||The exam, with
(no class on Columbus Day, October 9)
6, due October 27
LaTeX source for Assignment 6
||Proof by Induction
Some basic recursive functions, written in Python: Factorial, Fibonacci (a recursion disaster), Solution to the Towers of Hanoi puzzle.
7, due November 8
LaTeX source for Assignment 7
|October 30-November 3
number-theoretic functions, written in Python (base
conversion, Euclid's algorithm):
8, due December 1
LaTeX source for Assignment 8
||More Number Theory,
Finite State Machines and Regular Expressions
||Review Problems for
Errata for solutions (there was an error in the solution to 5(b))
Exam with solutions and results
||Finite State Machines,
Turing Machines and Computability
9,due December 9
LaTeX source for Assignment 9
(no class on Thanksgiving break, November 22-24)
|Turing Machines and Computability
||Python program for
Turing machine simulation. (This will also
draw state graphs for the input TM, which you can view
Specification of the TM that tests for equal numbers of a's and b's.
Automatically generated state graph for this TM.
|November 26-December 1
||Turing Machines and Computability
||Turing Machines and
||Wrap-up and review
exam from 2015
The exam from 2016
some (hastily scrawled) solutions to the above
Review summary--note that the problems given here, especially those concerning Turing machines, are more involved than typical exam problems.