CSCI2243 Home Page



CSCI2243-Logic and Computation

Fall, 2017



General Course Information What this Course is About Required Background Textbook
Required Work Grading The laptop-free classroom
Detailed Course Schedule

General Course Information


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:


TAs hold office hours in Fulton 160.

Alexandro Forte (forteal@bc.edu) OH: M 9PM-midnight.
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:

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.


Textbook

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.

Help us make this book better! 

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


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!

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.



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.


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
A sort of computerized 'proof' that certain sets are countable
Assignment 4, due October 1.

LaTeX source for Assignment 4.
September 25-29
More Sets and Functions


Review materials for midterm

Solutions to review questions


October 2-4
Predicate Logic



Assignment 5, due October 19

LaTeX source for Assignment 5
October 6
First Midterm
The exam, with solutions.

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



Assignment 6, due October 27

LaTeX source for Assignment 6
October 16-20
Proof by Induction


October 23-27
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 30-November 3
Number Theory
Some basic number-theoretic functions, written in Python (base conversion, Euclid's algorithm):

Recursive version
Iterative version

Assignment 8, due December 1

LaTeX source for Assignment 8
November 6-10
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))

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