CS 301: Languages and Automata — Spring 2018

Prerequisites

• CS 151: Mathematical Foundations of Computing
• CS 251: Data Structures (co-requisite)

This is a theoretical course. Students are expected to be familiar with the basics of structuring and writing proofs involving sets and functions.

Grading

The final course grade is based on exams, homework, labs, and quizzes.

• Midterm exams (30%)
• Final exam (20%)
• Homework (30%)
• Weekly labs (10%)
• Weekly quizzes (10%)

Letter grades will be assigned based on your weighted total points.

• 85%–100% – A
• 70%–84% – B
• 60%–69% – C
• 50%–59% – D
• 0%–49% – F

Any student who does not take the final exam will receive an F.

There may be a small amount of extra credit available throughout the semester, but no more than 5% of your total grade.

Exams

There are two midterm exams and one final exam at the dates and times listed at the top of this page.

Exams are closed book; however, you are allowed to bring one sheet of 8.5” by 11” paper, hand written on both sides with any information you think you’ll need. This sheet of notes will be turned in along with your exam but will not be returned to you.

Homework

There will be six homework assignments during the semester. Per the collaboration policy, you are free to work with other students on the homeworks, but you must write up your own solutions.

All of your written solutions must be typeset. You are strongly encouraged to use the LaTeX typesetting system to write up your solutions, but you are free to use other tools (such as Microsoft Word). See the resources below for more information on LaTeX.

In addition to written solutions, you will also produce DFAs, NFAs, PDAs, and Turing machines using JFLAP.

• Homework 1 Due Sunday, Feb. 4, 2018 at 23:59
• Homework 2 Due Sunday, Feb. 18, 2018 at 23:59
  Data file You will need this for Part I.
• Homework 3 Due Sunday, Mar. 11, 2018 at 23:59
• Homework 4 Due Sunday, Apr. 1, 2018 at 23:59
• Homework 5 Due Sunday, Apr. 22, 2018 at 23:59
• Homework 6 Due Sunday, May. 6, 2018 at 23:59

Labs and quizzes

Each week (starting the second week of the semester), you will have to complete a lab in discussion section as well as take an online quiz via Blackboard.

The labs and quizzes are designed to help prepare you for the homework and exams.

Course Materials

Textbooks

• Required. Michael Sipser. Introduction to the Theory of Computation, 3rd edition.
• Optional. Richard Hammack Book of Proof (available online).

Resources

JFLAP is software that you will use for building the machines we will be discussing in class.

LaTeX is a typesetting system which you are encouraged to use to write up solutions to the homework. Here is an example proof written in LaTeX and here is the corresponding source code.

LaTeX distributions are available for macOS, *NIX, and Windows:

• TeX Live (all systems)
• MacTeX macOS 10.10 and higher
• MiKTeX Windows, macOS, and Linux

There are a number of good references on the Web, including

• The Not So Short Introduction to LaTeX, a good introduction;
• User’s Guide for the amsmath Package, documentation for mathematical environments;
• TeX Stack Exchange, a Q&A site; and
• Our Piazza Forum;

There are many tools that can assist in writing LaTeX, including a variety of specialized editors such as Texmaker and TeXShop. There are also add-ons for editors like Emacs (AUCTeX is the best of those) and Vim.

Writing your solutions in LaTeX will take time at first, but as you become more familiar with it, you’ll find that it’s an invaluable tool. I strongly recommend you learn to use it well.

Course Policies

Attendance Policy

Class attendance is not mandatory; however, research indicates that students who attend class are more likely to be successful. You are strongly encouraged to attend every class. Lectures are not recorded. If you are unable to attend class, you should consider asking a classmate to take notes for you.

Missed or Late Work Policy

Homework is due by the time specified on each homework page. After the due date has passed, you may turn in the assignment up to 24 hours late with a 25% penalty.

Electronic Communication Policy

All electronic communication with course staff should take place on Piazza unless emails are specifically requested by the staff. Course staff may, from time to time, respond to emails, but a response to one email does not guarantee a response to a second. Use Piazza!

Collaboration Policy

You may collaborate with as many other students in the class on the homework. On your homework submission, you must list the name of everyone you discussed the homework with. You must write up your solutions entirely on your own.

Academic Integrity Policy

As an academic community, UIC is committed to providing an environment in which research, learning, and scholarship can flourish and in which all endeavors are guided by academic and professional integrity. All members of the campus community–students, staff, faculty, and administrators–share the responsibility of insuring that these standards are upheld so that such an environment exists. Instances of academic misconduct by students will be handled pursuant to the Student Disciplinary Policy.

The following are examples of academic misconduct.

• Claiming someone else’s work as your own.
• Searching for existing solutions to assignments.
• Sharing solutions to quizzes or exams.
• Falsifying program output.

Religious Holidays

The UIC Senate Policy on religious holidays is the following.

The faculty of the University of Illinois at Chicago shall make every effort to avoid scheduling examinations or requiring that student projects be turned in or completed on religious holidays. Students who wish to observe their religious holidays shall notify the faculty member by the tenth day of the semester of the date when they will be absent unless the religious holiday is observed on or before the tenth day of the semester. In such cases, the students shall notify the faculty member at least five days in advance of the date when he/she will be absent. The faculty member shall make every reasonable effort to honor the request, not penalize the student for missing the class, and if an examination or project is due during the absence, give the student an exam or assignment equivalent to the one completed by those students in attendance. If the student feels aggrieved, he/she may request remedy through the campus grievance procedure.

Academic Deadlines

See the academic calendar.

Grievance Procedures

UIC is committed to the most fundamental principles of academic freedom, equality of opportunity, and human dignity involving students and employees. Freedom from discrimination is a foundation for all decision making at UIC. Students are encouraged to study the University’s Nondiscrimination Statement. Students are also urged to read the document Public Formal Grievance Procedures. Information on these policies and procedures is available on the University web pages of the Office of Access and Equality.

Course Evaluations

Because student ratings of instructors and courses provide very important feedback to instructors and are also used by administrators in evaluating instructors, it is extremely important for students to complete confidential course evaluations online known as the Campus Program for Student Evaluation of Teaching evaluation. You will receive an email from the Office of Faculty Affairs inviting you to complete your course evaluations and will receive an email confirmation when you have completed each one.

For more information, please refer to the UIC Course Evaluation Handbook.

Results for the “six core questions” will be published on the UIC course evaluation website.