Announcements

• Piazza Discussion.

Introduction

Welcome to CS46: Theory of Computation! Computer technology changes rapidly, but the underlying model of computation is relatively unchanged in the past 50 years. How do computers compute, and why is this method of computation preferred over others methods? Do other methods even exist? Could we solve more interesting problems with another model? Could we solve the same problems we solve today using a simpler model of computation? In this course will will look at various theoretical models of computation and examine the computational power of these models. For each model we consider problems that can and cannot be solved, and develop a rigorous method of classifying how difficult certain problems are to compute. While the course emphasis is on theory, there are many applications of the topics discussed. Regular expressions, compilers, CPU job scheduling, and many other real-world problems have some underlying computational model rooted in the theory of computation.

Class info

Room: Science Center 128
Time: TR 8:30am–9:55am
Lab A: T 1:05pm–2:35pm
Lab B: R 2:40pm–4:15pm
Text: Introduction to the Theory of Computation 3rd Ed., M. Sipser

Professor: Andrew Danner
Office: Science Center 247
Phone: (610) 328-8665
Office hours: by appointment. Drop by if my door is open, or email me to set up a time

Schedule

WEEK	DAY	ANNOUNCEMENTS	TOPIC & READING	HOMEWORK
1	Jan 21		Math preliminaries Languages Intro to finite automata Read Chapter 0, 1.1, notes	HW1 pdf notes
	Jan 23
2	Jan 28		Finite automata regular languages Read Chapter 1	HW2 pdf notes
	Jan 30	Drop/Add ends (Jan 31)
3	Feb 04		non-determinism non-regular languages	HW3 pdf notes
	Feb 06
4	Feb 11		Context free grammars	HW4 pdf notes
	Feb 13
5	Feb 18		Pushdown automata Context free languages	HW5 pdf notes
	Feb 20
6	Feb 25		Turing Machine Intro
	Feb 27	Midterm I 7-9pm Sci 104
7	Mar 04		Turing machine extensions
	Mar 06
	Mar 11	Spring Vacation
	Mar 13
8	Mar 18		Decidability, Unsolvable problems	HW6 pdf notes
	Mar 20
9	Mar 25		Reductions	HW7 pdf notes
	Mar 27	Last day to declare CR/NC or withdraw with a "W" (Mar 28)
10	Apr 01		Intro to Complexity Theory
	Apr 03	Midterm II 7-9pm Sci 104
11	Apr 08		Computational complexity
	Apr 10	No Class
12	Apr 15		NP-complete problems	HW8 pdf notes
	Apr 17
13	Apr 22		Approximation Algorithms	HW9 pdf notes
	Apr 24
14	Apr 29		Wrapup
	May 01
	May 08	Final exams start
	May 17	Final exams end

Grading

Grades will be weighted as follows:

35%	Homework assignments
10%	Lab assignments
5%	Class Participation and Discussion
30%	Midterm exams
20%	Final Exam

Homework policy

Each week, reading and several problems will be assigned. You should work on all of the problems but hand in clearly written solutions to a subset (usually four) of the problems at the beginning of the Thursday session. Sometimes I will specify certain problems that must be part of what you hand in. All students should be prepared to discuss the reading and solutions to any of the problems. Always do all parts of a problem unless I specify otherwise.

It is best if you start the assignments early, and at least read the problems and make sure you understand what the problem is asking soon after the problems are assigned. If you do not understand a problem, ask for clarification. I often find that the solution to problems in this course only come if the problems sit in your brain for several hours, even if you are not constantly thinking about the problem during that time.

Late assignments will not be accepted except in extreme situations and only if you contact me well before the deadline. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.

Academic Accommodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services (Parrish 113) or email lhempli1 to arrange an appointment to discuss your needs. As appropriate, she will issue students with documented disabilities a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact her as soon as possible. For details about the accommodations process, visit the Student Disability Service website.

To receive an accommodation for a course activity, you must have an Accommodation Authorization letter from Leslie Hempling and you need to meet with me to work out the details of your accommodation at least one week prior to the activity.

You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through Leslie Hempling in the Office Of Student Disability Services.

Academic Integrity

Academic honesty is required in all your work. Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Please contact me if you have any questions about what is permissible in this course.

External Links

Links that are related to the course may be posted here. If you have suggestions for links, let me know.

LaTeX symbol classifier
A real DIY Turing Machine
JFLAP: Java Formal Languages and Automata Package

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:44 PM