On this page:
Foundations of Computer Science (Fall 2016)
1 Introduction
2 Lectures
3 Assignments
4 Turn-In and Grading
4.1 Turn-in
4.2 Assignment Scores
4.3 Exam Policy
4.4 Homework Numeric Grade
4.5 Numeric Grade
4.6 Letter Grade
5 Help
6 Readings
7 Software
8 Fine Print

Foundations of Computer Science (Fall 2016)

This class is taught by Jay McCarthy. Call him Jay. Email him at first-name DOT last-name AT gmail DOT com.

We meet in Olsen 104 at 1100-1215 on TR.

Jay McCarthy’s office hours are TR 0800-1400 in Olsen 221.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this mailing list.

1 Introduction

A survey of the mathematical foundations of Computer Science. Finite automata and regular languages. Stack Acceptors and Context-Free Languages. Turing Machines, recursive and recursively enumerable sets. Decidability. Complexity. This course involves no computer programming.

2 Lectures

 

Day

 

Date

 

Topic

 

Links

 

Notes

 

1

 

09/01

 

Preliminaries

 

 

ITC 0

 

2

 

09/06

 

Regular Languages: Finite Automata

 

 

ITC 1.1 (slides)

 

3

 

09/08

 

cont.

 

 

 

4

 

09/13

 

Regular Languages: Nondeterminism

 

 

ITC 1.2 (slides)

 

5

 

09/15

 

cont.

 

 

 

6

 

09/20

 

Regular Languages: Regular Expressions

 

 

ITC 1.3 (slides)*

 

7

 

09/22

 

cont.

 

 

*

 

8

 

09/27

 

Regular Languages: Nonregular Languages

 

 

ITC 1.4 (slides)

 

9

 

09/29

 

cont.

 

 

 

10

 

10/04

 

Context-Free Languages: Context-Free Grammars

 

 

ITC 2.1 (slides)

 

11

 

10/06

 

cont.

 

 

 

12

 

10/13

 

Context-Free Languages: Pushdown Automata

 

 

ITC 2.2 (slides)

 

13

 

10/18

 

cont.

 

 

 

14

 

10/20

 

Context-Free Languages: Non-context-free Languages

 

 

ITC 2.3 (slides)

 

15

 

10/25

 

Midterm Review

 

 

 

16

 

10/27

 

Midterm

 

 

See Midterm

 

17

 

11/01

 

Church-Turing Thesis: Turing Machines

 

 

ITC 3.1 (slides)

 

18

 

11/03

 

cont.

 

 

 

19

 

11/08

 

Church-Turing Thesis: Variants of Turing Machines

 

 

ITC 3.2 (slides)

 

20

 

11/10

 

cont.

 

 

 

21

 

11/15

 

Church-Turing Thesis: Algorithm Definition

 

 

ITC 3.3 (slides)

 

22

 

11/17

 

Decidability: Decidable Languages

 

 

ITC 4.1 (slides)

 

23

 

11/22

 

Decidability: Halting Problems

 

 

ITC 4.2 (slides)

 

24

 

11/29

 

cont.

 

 

 

25

 

12/01

 

Reducibility: Undecidable Problems from Language Theory & Mapping Reducibility

 

 

ITC 5.1 & 5.3

 

26

 

12/06

 

cont.

 

 

 

27

 

12/08

 

Final Review

 

 

 

28

 

12/15

 

Final (1500-1800)

 

 

Jay will not be present on days marked with a * in the Notes column.

This schedule is likely to change.

3 Assignments

 

Assignment

 

Code

 

Out

 

Due

 

Chapter 0

 

a1

 

09/01

 

09/08

 

Chapter 1, Sections 1.1-1.2

 

a2

 

09/06

 

09/20

 

Chapter 1, Sections 1.3-1.4

 

a3

 

09/20

 

10/04

 

Midterm

 

midterm

 

 

 

10/27

 

Chapter 2

 

a4

 

10/04

 

10/27

 

Chapter 3

 

a5

 

11/01

 

11/17

 

Extra Credit*

 

e1

 

 

 

12/08

 

Chapter 4

 

a6

 

11/17

 

12/08

 

Final

 

final

 

 

 

12/15

Assignments marked with a * are optional, extra credit.

Out dates are suggestions—you may need to start earlier—but we ensure that the course will have covered everything necessary by that date.

This schedule may change.

4 Turn-In and Grading

I highly recommend that you read this article about grading. I also recommend you read this article about the stress that you may experience in a computer science program. Please try to make healthy productive choices in your life. I would love the opportunity to help you in any ways I can.

4.1 Turn-in

You turn in your assignments by putting them on the lectern at the start of class on the day they are due. No assignments will be accepted after class starts. If you cannot turn in your assignment personally, you may have a friend do it or give it to me early. Each assignment should clearly have your name on it and the assignment code (listed in the Code column of the assignment table). I recommend preparing them electronically with LaTeX. In any case, you are responsible for my ability to read and understand the paper.

4.2 Assignment Scores

Each assignment’s page describes how it will be graded. All assignments will receive a grade from the closed interval between 0 and 1.

4.3 Exam Policy

Exams must be taken in person, at the scheduled time, and must be turned in on stapled-together paper with your writing on it as produced by your hand and a pen or pencil, except in special situations as required by students with special needs. Bring your own paper.

Exams must be completed without any notes, books, or resources of any kind.

Each exam will receive a grade from the closed interval between 0 and 1.

4.4 Homework Numeric Grade

I will compute your homework numeric grade by averaging the homework grades without weighting.

4.5 Numeric Grade

I will take your various points and combine them with this function to get a numeric grade:

> (define (sum l)
    (foldl + 0 l))
> (define (average l)
    (/ (sum l) (length l)))
> (define (combine hw midterm final)
    (+ (* 1/3 midterm)
       (* 1/3 final)
       (* 1/3 hw)))

Examples:
> (combine 0.0 0.0 0.0)

0.0

> (combine 0.5 0.5 0.5)

0.5

> (combine 1.0 0.5 0.5)

0.6666666666666666

> (combine 0.9 0.5 0.8)

0.7333333333333334

> (combine 1.0 1.0 1.0)

1.0

4.6 Letter Grade

I will then run the following function to convert it to a letter:
> (define (convert-to-letter ng)
    (cond
      [(> ng 0.93) "A"]
      [(> ng 0.9) "A-"]
      [(> ng 0.86) "B+"]
      [(> ng 0.83) "B"]
      [(> ng 0.8) "B-"]
      [(> ng 0.76) "C+"]
      [(> ng 0.73) "C"]
      [(> ng 0.7) "C-"]
      [(> ng 0.66) "D+"]
      [(> ng 0.6) "D"]
      [else "F"]))

Examples:
> (convert-to-letter 1)

"A"

> (convert-to-letter 0.94)

"A"

> (convert-to-letter 0.899999)

"B+"

> (convert-to-letter 0.81)

"B-"

> (convert-to-letter 0.74)

"C"

> (convert-to-letter 0.6999999)

"D+"

> (convert-to-letter 0.62)

"D"

> (convert-to-letter 0.57)

"F"

5 Help

My job is to help you.

If you need a "shallow" amount of help, then look at the Google Group. First, see if I have already answered your question. Then, send your own email.

Only send me personal email if you need to talk about something private, such as your grades. Anything else is best discussed in public, so others can benefit. If you do send personal email, put [CS304] as a prefix in the subject.

If you need a "deep" amount of help, please come to my office or call me (801-361-0732) and we’ll talk and try to resolve whatever ails you.

6 Readings

(ITC) We’ll be using the book Introduction to the Theory of Computation (3rd Edition), by Michael Sipser (Amazon link). (If you need to use a different edition, there will be minor differences, but the main content will be the same. You are responsible for the differences.)

You are expected to procure ITC yourself. It is available in digital formats. I highly recommend searching for it.

7 Software

The class does not include any software or programming components. However, if you prepare your homework electronically, I suggest using LaTeX.

8 Fine Print

In this course, all work is to be each student’s own. Students should therefore be familiar with the University’s rules on academic dishonesty, which can be found in the Bulletin of Undergraduate Studies and in the Schedule of Classes. In particular, plagiarism will not be tolerated! Any student caught plagiarizing another’s work will automatically receive a grade of F for the course. If you are unsure as to what constitutes plagiarism, it is your responsibility to check with the instructor. Other forms of dishonesty will result in similar actions. You may collaborate with your classmates on the design and results of the programs you will write in this course, but each student must implement these programs alone. Submission of shared student code is not permissible, and will result in a grade of F for the course. Help files are typically provided for each programming assignment, and students are encouraged to cut and paste useful code from these help files into their assignment submissions, but all other code must be the specific work of each student.

This course is based on 91.304 by Prof. Daniels.

You are not allowed to post solution code to problem sets assigned in this class in public places (e.g. Github). This includes your own solutions as well as solutions that may be provided by the instructors. This policy is a courtesy to future students, who — to the fullest extent possible — should have the opportunity to struggle with the problems in the same way that you do. Non-compliance will be pursued rigorously per UMass Lowell’s academic integrity policy.