MATH 421: Theory of Computation

Syllabus

Class Nbr.	1932
Mode of delivery:	synchronous online
Meeting:	MTW F,   2 - 2:50pm   via Canvas
Text:	Introduction to the Theory of Computation (3rd Ed.) by M. Sipser (ISBN-13: 978-1-133-18779-0)
Prerequisites:	MATH 320
Instructor:	Dr. Sergei Bezrukov		Office:  SW3022		Schedule and Office hours
	Tel.: 394-8523		E-mail: sbezruko@uwsuper.edu

---

Catalog Description

Thorough introduction to automata, formal languages, and computability. Topics include: models of computation; regular and context-free languages; finite and pushdown automata; Turing machines; unsolvable decision problems; and fundamentals of computational complexity.

---

Learning Objectives

Students will learn how to model computational devices, up to and including a modern electronic computer, using standard techniques of computer science. Students will be able to state, explain, and prove various capabilities and limitations of computing devices based on these models. Students will be able to work with time and space complexity, and understand the standard categories of computational complexity.

---

Course Outcomes

• Students will be able to state, explain, and prove various capabilities and limitations of computing devices based on the above models.
• Students will be able to work with time and space complexity, and understand the standard categories of computational complexity.

---

Evaluation and Grading

• Scores and grade
  • The final grade for the course depends on the averaged score for home work assignments (this score is denoted by hw), scores for two midterm exams (denoted by ex₁ and ex₂), score for the final exam (ex₃), and some amount of bonus points.
  • The total score will be computed according to the formula:
    total score = (25*hw + 25*ex₁ + 25*ex₂ + 25*ex₃) / 100 + bonus
  • The total score will be translated into the final grade according to the following table:

    	A : 93 - 96	A- : 90 - 92
    B+ : 87 - 89	B : 83 - 86	B- : 80 - 82
    C+ : 77 - 79	C : 73 - 76	C- : 70 - 72
    D+ : 67 - 69	D : 63 - 66	D- : 60 - 62
    F : 0 - 59

• Assignments (25%)
  Take home exercises will be regularly assigned, collected, graded and returned. The students are allowed to discuss the problems in groups, however writings must be done strictly individually. Returning identical work is qualified as cheating (see below).
  • Maximum score for each assignment is 100 points.
  • For final grade purposes, the lowest of the assignment scores will be dropped if it is above 60%.
  • If hw₁, hw₂, ... , hw₉ are the scores for these assignments (each number in the range 0 to 100), then the total score for the assignments is the average of these scores, that is
    hw = (hw₁ + hw₂ + ... + hw₉) / 9
    rounded off to the nearest integer from above.

• Midterm exams (two of them, each worth 25%)
  One exam will be given after 3-5 weeks of the beginning of the course, and another one will be given about 2-4 weeks before the end of the course. The maximum score for each midterm exam is 100 points.
  • The first exam covers the material from the first part of the course.
  • The second exam emphasizes on the material covered after the first exam.
  • The midterm exams, including possible take-home parts, must be done strictly individually, so no collective solutions or discussions are allowed.
  • No late submission of the take-home part (if assigned) is accepted.

• Final exam (25%)
  Date/time in Final Examination Schedule. The maximum score for the final exam is 100 points.
  • The final exam is comprehensive. So, any course content from the entire semester is fair game.
  • The final exam must be done strictly individually, so no collective solutions or discussions are allowed.
  • No late submission of the take-home part (if assigned) is accepted.

• Bonus points (0-6)
  Bonus points will be issued during the last week of classes for:
  • participation in course related discussions in class (0-2 points)
  • quality and completeness of homeworks (0-2 points)
  • overall progress in class (0-2 points)

---

Class Policies

• Instructor retains the right to make any and all deletions, additions and changes to the requirements or structure of the course and its materials as deemed necessary.
• No class work is accepted after the Final Exam.
• Problems in late homework assignments are accepted within two days after the assignment was due. In this case a student will be penalized on 10 points per assignment. However, if a solution to a problem is discussed in class or posted online, no late solution to this problem will be accepted after this. A submission is qualified as late if it is returned after the specified date and time.
• Representing someone else's work as your own without referencing or permitting another student to do so with your work is cheating.
  Cheating might result in administrative actions described in UWS14.03 UW-System Administrative Code Student Academic Disciplinary Procedures.
• A make up of an exam is allowed if an unavoidable absence occurs. A reason for absence must be documented.
• Students are required to check with the instructor if they find some of these rules unclear, before taking an action.

Class Attendance

• Students are expected to attend all class periods regardless of modality except in the case of illness such as COVID-19 or other illness that causes poor physical health and precludes you from attending in-person or online. Care-giving such as caring for a child or a family member with COVID-19 is also an acceptable reason for your absence.
• If you are absent from a class period for either an on-campus course or a synchronous online course it is your responsibility to contact and communicate with your instructor for any missed periods or resulting delays on classwork. Contact your instructor before you are absent if possible. You will not need a formal doctor's note to excuse an absence caused by illness or caregiving for COVID-19 in this course.
• If you are absent from classes for reasons related to illness or caregiving and have notified your instructor, you will not be penalized through grades, missing points, or be deprived of the chance to make-up assignments. But you must still work with your instructor to make up any missed work - either in-class or out-of-class - within the timeframe designated by the instructor.
• Students who are not ill, but are in quarantine and/or isolation during testing wait periods due to COVID-19 exposure should attend class online or complete substitute activities at the direction of the instructor.

Suggestions for Success in Class

• Do not miss classes. The class discussions emphasize on many particular aspects, a good number of them is not in the textbook or spread out over several chapters in the book so that it might be difficult to find them. These details may be very helpful for your work on the assignments.
• Ask right away in class or after the class if something is not clear.
• Read in the books the topics that are covered in class on the same day after the class. Just working on the material during the class hours is far from being enough. It is expected that a student would spend at least 2 hours in average working through the material after each class.
• Prepare yourself for the next class. That is, read in advance the material to be explained in class. Refer to the Course Outline to figure out what will be covered (it will also be announced at the end of each class). It would be much easier for you then to follow the discussion in class. In addition you would know what to pay a particular attention on and what questions to ask.
• Come to the instructor's office hours (or make a special appointment) and do not let the unclear stuff to accumulate.
• Try to find time to solve as many problems as possible (even more than it is assigned). Solving the problems is the only way to learn how to solve them.

---

University Policies

• Diversity and Inclusion at UW-Superior
  Diversity and inclusion is integral to the educational mission of the University of Wisconsin-Superior. As a community we commit to recognize, include and value inherent worth and dignity of each person; foster tolerance, sensitivity, understanding, mutual respect, and justice among its members; and encourages each individual to strive to reach their own potential. The institution recognizes these experiences are crucial for developing the requisite skills to thrive as a member of a pluralistic society and as a responsible global citizen.

  In pursuit of its goal of inclusive excellence, the University actively seeks to attract students, faculty, and staff from diverse backgrounds and life experiences, including but are not limited to: race, ethnicity, sex, gender identity, gender expression, sexual orientation, age, socio-economic background, cognitive ability, physical ability, religion and spirituality, value system, national origin, immigration or refugee status, veteran status, and political beliefs.

  The University believes that diversity among its members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life. The University of Wisconsin-Superior views, evaluates, and treats all person in any University related activity or circumstance in which they may be involved, solely as individuals. For more information about Equity, Diversity and Inclusion and/or to report bias, discrimination or harassment, please email edi@uwsuper.edu.

• Class Cancellations
  When weather conditions are dangerous, students will be informed via the media about class cancellations. Students should not call Campus Safety.

• Accommodation of Religious Beliefs
  Student's sincerely held religious beliefs should be reasonably accommodated with respect to scheduling all examinations and other academic requirements. Students should inform the instructor of these needs at the start of the semester.

• Disabilities Accommodation
  Adaptations of methods, materials or testing will be made to accommodate educational participation. Students should inform the instructor of these needs at the start of the semester.

Please refer to the University Catalog or the UW-Superior Web page for full description of these and other policies.