625.690.81 - Computational Complexity and Approximation

Expanded Course Description

Prerequisites

Introductory probability theory and/or statistics (such as 625.603) and undergraduate-level exposure to algorithms and matrix algebra. Some familiarity with optimization and computing architectures is desirable but not necessary.

Course Structure

The course materials are divided into modules which can be accessed by clicking Course Modules on the left menu. A module will have several sections including the overview, content, readings, discussions, and assignments. You are encouraged to preview all sections of the module before starting. Most modules run for a period of seven (7) days, exceptions are noted in the Course Outline. You should regularly check the Calendar and Announcements for assignment due dates.

Course Goals

To provide an overview of the theory of computational complexity covering Turing machines, Karp and Turing reducibility, basic complexity classes, theory of NP-completeness, and approximation and optimization and algorithms.

Course Learning Outcomes (CLOs)

• Use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions, and integers.
• Synthesize finite automata with specific properties.
• Convert among multiple representations of finite automata.
• Use pigeon-holing arguments and closure properties to prove particular problems cannot be solved by finite automata.
• Calculate asymptotic estimates of the computational complexity of simple procedures from automata, language and Turing machines.
• Prove undecidability using diagonalization and reducibility methods.
• Use the relationship between recognizability and decidability to determine decidability properties of problems.
• Describe concrete examples of undecidable problems from different fields.
• Define, and explain the significance of, the "P = NP?" question and NP-completeness.
• Describe concrete examples of NP-complete problems from different fields.
• Prove lower bounds on time and space complexity using diagonalization and polynomial time reducibility methods.
• Define deterministic and nondeterministic computation time and space, and explain the relationships among them.
• Describe concrete examples of decidable problems that are known to be unsolvable in polynomial time.
• Evaluate approximation algorithms.
• Implement an optimization algorithm.

Textbooks

Required

John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley, 2006

ISBN-13: 978-0321455369

ISBN-10: 0321455363

Rodger, S. H. and Finley, T. H., (2006) JFLAP: An Interactive Formal Languages and Automata Package, Sudbury, MA, Jones and Bartlett Publishers. (FREE DOWNLOAD at the following: http://www.jflap.org)

ISBN-10: 0763738344

ISBN-13: 978-0763738341

Textbook information for this course is available online through the appropriate bookstore website: For online courses, search the MBS website at http://ep.jhu.edu/bookstore.

Optional

Sipser, M. (2013). Introduction to the theory of computation. (3rd ed.). Boston, MA: Cengage Learning.

ISBN-10: 113318779X ISBN-13: 978-1133187790

Required Software

JFLAP

You will need access to JFLAP. “JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems. In addition to constructing and testing examples for these, JFLAP allows one to experiment with construction proofs from one form to another, such as converting an NFA to a DFA to a minimal state DFA to a regular expression or regular grammar.” You can access JFLAP at the following website: www.jflap.org

Student Coursework Requirements

It is expected that each module will take approximately 7–10 hours per week to complete. Here is an approximate breakdown: reading the assigned sections of the texts (approximately 3–4 hours per week) as well as some outside reading, listening to the audio annotated slide presentations (approximately 2–3 hours per week), and writing assignments (approximately 2–3 hours per week).

This course will consist of the following basic student requirements:

Preparation and Participation (10% of Final Grade Calculation)

You are responsible for carefully reading all assigned material and being prepared for discussion. The majority of readings are from the course text. Additional reading may be assigned to supplement text readings.

Post your initial response to the discussion questions by the evening of day 4 for that module week. Posting a response to the discussion question is part one of your grade for module discussions (i.e., Timeliness).

Part two of your grade for module discussion is your interaction (i.e., responding to classmate postings with thoughtful responses) with at least two classmates (i.e., Critical Thinking). Just posting your response to a discussion question is not sufficient; we want you to interact with your classmates. Be detailed in your postings and in your responses to your classmates' postings. Feel free to agree or disagree with your classmates. Please ensure that your postings are civil and constructive.

I will monitor module discussions and will respond to some of the discussions as discussions are posted. In some instances, I will summarize the overall discussions and post the summary for the module.

Evaluation of preparation and participation is based on contribution to discussions. Preparation and participation is evaluated by the following grading elements:

Timeliness (50%)

Critical Thinking (50%)

Preparation and participation is graded as follows:

• 100–90 = A—Timeliness [regularly participates; all required postings; early in discussion; throughout the discussion]; Critical Thinking [rich in content; full of thoughts, insight, and analysis].
• 89–80 = B—Timeliness [frequently participates; all required postings; some not in time for others to read and respond]; Critical Thinking [substantial information; thought, insight, and analysis has taken place].
• 79–70 = C—Timeliness [infrequently participates; all required postings; most at the last minute without allowing for response time]; Critical Thinking [generally competent; information is thin and commonplace].
• <70 = F—Timeliness [rarely participates; some, or all required postings missing]; Critical Thinking [rudimentary and superficial; no analysis or insight is displayed].

Assignments (30% of Final Grade Calculation)

Assignments will include a mix of qualitative assignments (e.g. literature reviews, model summaries), quantitative problem sets, and case study updates. Include a cover sheet with your name and assignment identifier. Also include your name and a page number indicator (i.e., page x of y) on each page of your submissions. Each problem should have the problem statement, assumptions, computations, and conclusions/discussion delineated. All Figures and Tables should be captioned and labeled appropriately.

All assignments are due according to the dates in the Calendar.

Late submissions will be reduced by one letter grade for each week late (no exceptions without prior coordination with the instructors).

If, after submitting a written assignment you are not satisfied with the grade received, you are encouraged to redo the assignment and resubmit it. If the resubmission results in a better grade, that grade will be substituted for the previous grade.

Qualitative assignments are evaluated by the following grading elements:

1. Each part of question is answered (20%)
2. Writing quality and technical accuracy (30%) (Writing is expected to meet or exceed accepted graduate- level English and scholarship standards. That is, all assignments will be graded on grammar and style as well as content.)
3. Rationale for answer is provided (20%)
4. Examples are included to illustrate rationale (15%) (If you do not have direct experience related to a particular question, then you are to provide analogies versus examples.)
5. Outside references are included (15%)

Qualitative assignments are graded as follows:

• 100–90 = A—All parts of question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [rich in content; full of thought, insight, and analysis].
• 89–80 = B—All parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [substantial information; thought, insight, and analysis has taken place].
• 79–70=C—Majority of parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [generally competent; information is thin and commonplace].
• <70=F—Some parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [rudimentary and superficial; no analysis or insight displayed].

Quantitative assignments are evaluated by the following grading elements:

1. Each part of question is answered (20%)
2. Assumptions are clearly stated (20%)
3. Intermediate derivations and calculations are provided (25%)
4. Answer is technically correct and is clearly indicated (25%)
5. Answer precision and units are appropriate (10%) Quantitative assignments are graded as follows:
   • 100–90 = A—All parts of question are addressed; All assumptions are clearly stated; All intermediate derivations and calculations are provided; Answer is technically correct and is clearly indicated; Answer precision and units are appropriate.
   • 89–80 = B—All parts of question are addressed; All assumptions are clearly stated; Some intermediate derivations and calculations are provided; Answer is technically correct and is indicated; Answer precision and units are appropriate.
   • 79–70=C—Most parts of question are addressed; Assumptions are partially stated; Few intermediate derivations and calculations are provided; Answer is not technically correct but is indicated; Answer precision and units are indicated but inappropriate.
   • <70=F—Some parts of the question are addressed; Assumptions are not stated; Intermediate derivations and calculations are not provided; The answer is incorrect or missing; The answer precision and units are inappropriate or missing.

Course Project (30% of Final Grade Calculation)

A course project will be assigned several weeks into the course. The next-to-the-last week will be devoted to the course project.

The course project is evaluated by the following grading elements:

1. Student preparation and participation (as described in Course Project Description) (30%)
2. Student technical understanding of the course project topic (as related to individual role that the student assumes and described in the Course Project Description) (20%)
3. Team preparation and participation (as described in Course Project Description) (30%)
4. Team technical understanding of the course project topic (as related to the Customer Team roles assumed by the students and the Seller Team roles assumed by the students and described in the Course Project Description) (20%)

Course Project is graded as follows:

• 100–90 = A—Student Preparation and Participation/ Team Preparation and Participation [individual/ team roles and responsibilities well defined and understood; individual/ team well versed in use of Adobe Connect; individual/ team work product(s) agreed to, well prepared and available to all team members/ instructors]; Student Understanding/ Team Understanding [rich in content; full of thought, insight, and analysis].
• 89–80 = B—Student Preparation and Participation/ Team Preparation and Participation [individual/ team roles and responsibilities well defined and understood; individual/ team well versed in use of Adobe Connect; individual/ team work product(s) agreed to and prepared]; Student Understanding/ Team Understanding [substantial information; thought, insight, and analysis has taken place].
• 79–70 = C—Student Preparation and Participation/ Team Preparation and Participation [individual/ team roles and responsibilities agreed to; individual/ team well versed in use of Adobe Connect; individual/ team work product(s) prepared]; Student Understanding/ Team Understanding [generally competent; information is thin and commonplace].
• <70 = F—Student Preparation and Participation/ Team Preparation and Participation [individual/ team roles and responsibilities not well understood; individual/ team has difficult with use of Adobe Connect; individual/ team work product(s) partially prepared]; Student Understanding/ Team Understanding [rudimentary and superficial; no analysis or insight displayed].

Midterm Exam (30% of Final Grade Calculation)

The midterm exam will be available in Module 6 and the final exam will be available in the next-to-last Module. You will have one week to complete the exams and they will be due by 5PM exactly one week from their release. You may use the course text to complete the exams.

The exams are evaluated by the following grading elements:

1. Each part of question is answered (20%)
2. Writing quality and technical accuracy (30%) (Writing is expected to meet or exceed accepted graduate- level English and scholarship standards. That is, all assignments will be graded on grammar and style as well as content.)
3. Rationale for answer is provided (20%)
4. Examples are included to illustrate rationale (15%) (If a student does not have direct experience related to a particular question, then the student is to provide analogies versus examples.)
5. Outside references are included (15%) Exams are graded as follows:
   • 100–90 = A—All parts of question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [rich in content; full of thought, insight, and analysis].
   • 89–80 = B—All parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [substantial information; thought, insight, and analysis has taken place].
   • 79–70 = C—Majority of parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [generally competent; information is thin and commonplace].
   • <70 = F—Some parts of the question are addressed; Writing Quality/ Rationale/ Examples/ Outside References [rudimentary and superficial; no analysis or insight displayed].

Grading Policy

Assignments are due according to the dates posted in your Blackboard course site. You may check these due dates in the Course Calendar or the Assignments in the corresponding modules. I will post grades one week after assignment due dates.

We generally do not directly grade spelling and grammar. However, egregious violations of the rules of the English language will be noted without comment. Consistently poor performance in either spelling or grammar is taken as an indication of poor written communication ability that may detract from your grade.

A grade of A indicates achievement of consistent excellence and distinction throughout the course—that is, conspicuous excellence in all aspects of assignments and discussion in every week.

A grade of B indicates work that meets all course requirements on a level appropriate for graduate academic work. These criteria apply to both undergraduates and graduate students taking the course.

EP uses a +/- grading system (see “Grading System”, Graduate Programs catalog, p. 10). 100-98 = A+

97-94 = A

93-90 = A−

89-87 = B+

86-83 = B

82-80 = B−

79-77 = C+

76-73 = C

72-70 = C−

69-67 = D+

66-63 = D

<63 = F

Final grades will be determined by the following weighting:

Academic Policies

Deadlines for Adding, Dropping and Withdrawing from Courses

Students may add a course up to one week after the start of the term for that particular course. Students may drop courses according to the drop deadlines outlined in the EP academic calendar (https://ep.jhu.edu/student-services/academic-calendar/). Between the 6th week of the class and prior to the final withdrawal deadline, a student may withdraw from a course with a W on their academic record. A record of the course will remain on the academic record with a W appearing in the grade column to indicate that the student registered and withdrew from the course.

Academic Misconduct Policy

All students are required to read, know, and comply with the Johns Hopkins University Krieger School of Arts and Sciences (KSAS) / Whiting School of Engineering (WSE) Procedures for Handling Allegations of Misconduct by Full-Time and Part-Time Graduate Students.

This policy prohibits academic misconduct, including but not limited to the following: cheating or facilitating cheating; plagiarism; reuse of assignments; unauthorized collaboration; alteration of graded assignments; and unfair competition. Course materials (old assignments, texts, or examinations, etc.) should not be shared unless authorized by the course instructor. Any questions related to this policy should be directed to EP’s academic integrity officer at ep-academic-integrity@jhu.edu.

Students with Disabilities - Accommodations and Accessibility

Johns Hopkins University values diversity and inclusion. We are committed to providing welcoming, equitable, and accessible educational experiences for all students. Students with disabilities (including those with psychological conditions, medical conditions and temporary disabilities) can request accommodations for this course by providing an Accommodation Letter issued by Student Disability Services (SDS). Please request accommodations for this course as early as possible to provide time for effective communication and arrangements.

For further information or to start the process of requesting accommodations, please contact Student Disability Services at Engineering for Professionals, ep-disability-svcs@jhu.edu.

Student Conduct Code

The fundamental purpose of the JHU regulation of student conduct is to promote and to protect the health, safety, welfare, property, and rights of all members of the University community as well as to promote the orderly operation of the University and to safeguard its property and facilities. As members of the University community, students accept certain responsibilities which support the educational mission and create an environment in which all students are afforded the same opportunity to succeed academically. 

For a full description of the code please visit the following website: https://studentaffairs.jhu.edu/policies-guidelines/student-code/

Classroom Climate

JHU is committed to creating a classroom environment that values the diversity of experiences and perspectives that all students bring. Everyone has the right to be treated with dignity and respect. Fostering an inclusive climate is important. Research and experience show that students who interact with peers who are different from themselves learn new things and experience tangible educational outcomes. At no time in this learning process should someone be singled out or treated unequally on the basis of any seen or unseen part of their identity. 
 
If you have concerns in this course about harassment, discrimination, or any unequal treatment, or if you seek accommodations or resources, please reach out to the course instructor directly. Reporting will never impact your course grade. You may also share concerns with your program chair, the Assistant Dean for Diversity and Inclusion, or the Office of Institutional Equity. In handling reports, people will protect your privacy as much as possible, but faculty and staff are required to officially report information for some cases (e.g. sexual harassment).

Course Auditing

When a student enrolls in an EP course with “audit” status, the student must reach an understanding with the instructor as to what is required to earn the “audit.” If the student does not meet those expectations, the instructor must notify the EP Registration Team [EP-Registration@exchange.johnshopkins.edu] in order for the student to be retroactively dropped or withdrawn from the course (depending on when the "audit" was requested and in accordance with EP registration deadlines). All lecture content will remain accessible to auditing students, but access to all other course material is left to the discretion of the instructor.