Homework Assignment 1
Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Spring 2004
Due Dates: Oral presentations of material begin on 5 February.
Written descriptions of material presented due one week after presentation.
Topics: Finite State Automata (Chapter 1).
An integral part of this class is understanding and presenting the problems
assigned as homework. Everyone is expected to do all the problems,
but we will take turns on who presents the problem solutions to the class
(every 2-3 weeks, depending on the number of students in the class). Within
a week of presenting a problem solution to the class, you must submit a written
description of it, via the Blackboard system. The written solutions
will be posted on the Blackboard website for the class, so, they can used
by everyone to study for the exams. Since it's hard to write
down answers that are concise and are easily readable by all, if you wish
to improve a grade on any problem, you may resubmit it for grading.
Using Blackboard
In general, to use the Lehman College Blackboard Server, you must
have an alpha account, available free to all Lehman students
from the Computer Center. To use the Blackboard system for this
course, you must be enrolled in the course. A login name
and default password are generated for each enrolled student.
These should be available during the first week of class from the
Academic Computer Center.
Logging In
Once you have your login, access the Blackboard server at:
http://blackboard.lehman.cuny.edu Click the Login button, type your username, press Tab (not Enter),
type your password, and click OK. You may have to repeat this process
the first time you access Blackboard.
You should change your password regularly. To change your password,
choose the "Personal Information" menu from the left hand side of the
Blackboard window, and then choose "Change Password."
Taking Quizzes
On the "Announcements," there is a link to the first quiz. After
reading the Academic Integrity Policy discussed on the first day, you should
take this quiz. All Blackboard quizzes can be taken multiple times, until the deadline.
You have the option of taking the quizzes on paper,
from 8:30 to 8:50 on the day the quiz is due.
If you choose the paper option, you must give 48 hours notice
so that a copy of the quiz is printed for you.
The on-line and paper quizzes are different but will cover the same
material.
- If you have a documented learning disability that allows extra time,
you must provide written documention at least two days before the quiz
to have the extra time. All extended time quizzes are given on paper
(not on-line), on the day the quizzes are due (with
the same ending time as others taking the quiz).
- If you are found cheating or accepting help from others on the on-line
quizzes, you must take the quizzes on paper.
Submitting Written Descriptions
We will use the "Dropbox" option of Blackboard to submit your written descriptions
of problem solutions. The Dropbox is available off the main menu, and
has two options: Add or Send. The Add option stores a file in your
account (but no one else can see it), while the Send option will send a copy
to me. Use the Send option to submit written descriptions.
Academic Integrity
Quizzes and assignments are open book and open notes, but you may not accept
help from others while taking your quiz. For assignments, you must acknowledge
all others (including books and websites) with whom you worked with or received
help. All work must be your own. See Academic Policy of the bulletin for more details.
Undergraduate Problems
All students enrolled should complete the following:
- Take the first quiz on Blackboard.
- Exercise 1.1
- Exercise 1.1a,b,e,f for the machine M_4 on p 38.
- Exercise 1.2.
- Exercise 1.3.
- Exercise 1.4a.
- Exercise 1.4b.
Graduate Problems
Students enrolled for graduate credit, should complete all the undergraduate problems, as well as:
- Exercise 1.4d.
- Exercise 1.4e.
- Exercise 1.4h.
- Exercise 1.4k.
- Exercise 1.4l.