Lectures:	TTh 12:30-1:45, HH306
	W 1:00-1:50, MWAH 175
Course web site:	http://www.d.umn.edu/~hudson/3512

Instructor:	Hudson Turner
Email:	hudson@d.umn.edu
Office:	327A Heller Hall
Phone:	726-6168
Office hours:	MF 9:30-10:30, W 2:00-2:50, and by appt. (Hope to see you this semester!)

Prerequisites: Calc I, CS2511, or equivalent. The computer science bachelor's degree program at UMD is accredited by CAC (the Computing Accreditation Commission). One of the CAC requirements is that all students must satisfy the prerequisites in order to be admitted to a course, so if you have not passed the prerequisite courses, you must drop this course.

Textbook: James L. Hein, Discrete Structures, Logic, and Computability, Third Edition, 2010, Jones and Bartlett. Web site: http://www.jbpub.com/Catalog/9780763772062/Overview/

Bulletin description: Sets, relations, functions. Recursive definitions of functions and sets. Proof methods, including mathematical and structural induction, diagonalization. Program correctness, asymptotic time/space complexity. Formal language theory, including regular languages and expressions, deterministic/nondeterministic finite automata, Kleene's Theorem.

Things to keep in mind:

• Lecture notes will be posted on the course web page -- study them thoroughly, using the textbook for enrichment as appropriate.
• Study problems will also posted on the course web page -- some from the textbook, some not. Please ask questions during office hours or by email. Don't let difficulties pile up!
• There will be frequent in-class quizzes (typically open book, open notes). You'll need to keep up in order to do well on the quizzes.
• Most of the points in the class ride on three 75 minute exams and the final exam. These are open book, open notes. In order to do well on the exams, you will probably need to have worked steadily throughout the semester, asking questions promptly when things aren't clear. (Last-minute cramming generally won't get you very far on these exams -- the material is too demanding.)
• It is not enough to "sort of" understand what's covered in lecture; you need to be able to do the work yourself, even when (especially when) the problem you're asked to solve (or the claim you're asked to prove) is somehow different from any you've yet seen. This will happen, repeatedly, since the overall goal in this course is "understanding". I hope to help prepare you to learn additional math and cs theory yourself, since we can't hope to cover everything of this kind you might encounter in your cs careers.

Course grades:

Final grades will be based on total points, which can be earned as follows.

• 30-minute quizzes during most Tuesday class meetings. (10 points each, no makeups, lowest 2 dropped)
• Shorter, pop quizzes during Wednesday and Thursday class meetings. (5 points each, no makeups, lowest 2 dropped)
• Three 75 minute in-class exams, each announced at least a week in advance. (75 points each)
• Comprehensive final exam at the scheduled time. See UMD Final Exam Schedule, Fall 2009. (125 points)

Grades are assigned based on percentage of the total points.

• The A- cutoff is 90%
• The B- cutoff is 80%
• The C- cutoff is 70%
• The D cutoff is 60%
• Below 60% is an F

These percentages have always been lowered considerably in past semesters, and almost certainly will again this semester; they will not be raised.

On quizzes and exams: Please make your work legible and easy to follow. Show all nontrivial steps in your solutions. Little or no work shown sometimes earns little or no credit, even if the answer is otherwise correct. Solutions should be legible, clear, concise, complete, correct.

Exams will not be given early, and makeups must be justified by dire circumstances described to the instructor before the time of the exam.

In particular, the final exam will not be given early; makeup exams in case of the "no 3 exams on one day" policy, will only be given after that time. (In the Policies and Procedures chapter of the UMD catalog the Final Examination Conflicts section explains the UMD policy about having more than two final exams on a single day.)

It is Department of Computer Science policy not to return final exams, however they are kept and you can look at your exam in the instructor's office.

No electronic devices will be allowed during quizzes or exams. Notice that this means you will need to print out copies of the lecture notes --- you won't be able to look at them online during quizzes and exams.

Incompletes: The grade of I (incomplete) may be given only when (a) the student has performed satisfactorily during most of the semester, and (b) the student is unable to finish the semester's work on time for reasons beyond his or her control. Students will not be assigned an incomplete solely for the purpose of avoiding a poor grade. According to UMD policy, the temporary grade I (incomplete) is assigned only when a student has made an agreement with the instructor to complete the course requirements before the instructor submits final grades for a semester.

Equal opportunity: The University of Minnesota is committed to the policy that all persons shall have equal access to its programs, facilities, and employment without regard to race, color, creed, religion, national origin, sex, age, marital status, disability, public assistance status, veteran status, or sexual orientation. As instructor, I am committed to upholding University of Minnesota's equal opportunity policy. I encourage you to talk to me in private about any concerns you have related to equal opportunity in the classroom. To inquire further about the University's policy on equal opportunity, contact the Office of Equal Opportunity, 269-273 DAdB, (http://www.d.umn.edu/equaloo), phone: (218) 726-6827 or (218) 726-6849, email: equaloo@d.umn.edu.

Students with disabilities: If you have any disability (either permanent or temporary) that might affect your ability to perform in this class, please inform me at the start of the quarter. I may adapt methods, materials, or testing so that you can participate equitably. To learn about the services that UMD provides to students with disabilities, contact the Disability Services and Resources Office, 236 Kirby Student Center, (http://www.d.umn.edu/access), phone: (218) 726-8217 or TTY (218) 726-7380, email: access@d.umn.edu, or contact the Office of Equal Opportunity, 269-273 DAdB, (http://www.d.umn.edu/equaloo), phone: (218) 726-6827, email: equaloo@d.umn.edu.