## CS 462/662 Formal Languages and Parsing Winter 2020

### Homework Assignments

Be sure to prepare your solutions using a document preparation system like LaTeX or Word. Do not handwrite solutions! For diagrams only, feel free to draw by hand and scan. If you do not follow this requirement, marks will be deducted.

1. Problem Set 1: handed out Wednesday, January 8; due Friday January 17 by 5 PM sharp. Submit to LEARN.

2. Problem Set 2: handed out Friday, January 17; due Friday January 24 by 5 PM sharp. Submit to LEARN.

3. Problem Set 3: handed out Friday, January 24; due Friday January 31 by 5 PM sharp. Submit to LEARN.

4. Problem Set 4: handed out Friday, January 31; due Friday February 7 by 5 PM sharp. Submit to LEARN.

5. Problem Set 5: handed out Friday, February 7; due Friday February 14 by 5 PM sharp. Submit to LEARN.

6. Problem Set 6: handed out Friday, February 14; due Friday February 28 by 5 PM sharp. Submit to LEARN.

7. Problem Set 7: handed out Friday, February 28; due Friday March 6 by 5 PM sharp. Submit to LEARN.

8. Problem Set 8: handed out Friday, March 6; due Friday March 13 by 5 PM sharp. Submit to LEARN.

9. Problem Set 9: cancelled due to Covid-19.

10. Problem Set 10: handed out Monday, March 23; due Friday March 27 by 5 PM sharp. Submit to LEARN.

11. Problem Set 11: handed out Friday, March 27; due Friday April 3 by 5 PM sharp. Submit to LEARN. Revised:, 5:00 AM Saturday March 28. In problem 1 the inequality should be K(xy) ≤ K(x) + K(y) + O(1) and not K(xy) = K(x) + K(y) + O(1).

### Handouts

• Different Proof of Theorems 2.3.2 and 2.3.3
• In pdf format
• Different proof of Theorem 2.5.1
• In pdf format
• Info about the shuffle operation
• In pdf format
• Revised proof of Theorem 3.10.2
• In pdf format
• Revised proof of Theorem 4.2.1
• In pdf format

### Group Problem Solving

See the page here for problems and solutions.

### Final Exam

See here.

A discussion of the possibilities is here. Due dates: one-page proposal, due February 12 2020. Project due, April 3 2020.

## Mental Health Resources

Mental Health: If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.

On-campus Resources

Off-campus Resources

• Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454
• Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247
• OK2BME: set of support services for lesbian, gay, bisexual, transgender or questioning teens in Waterloo. Phone: 519-884-0000 extension 213

Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students' learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

• We will gladly honour your request to address you by an alternate/preferred name or gender pronoun. Please advise us of this preference early in the semester so we may make appropriate changes to our records.
• We will honour your religious holidays and celebrations. Please inform of us these at the start of the course.
• We will follow AccessAbility Services guidelines and protocols on how to best support students with different learning needs.

Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check https://uwaterloo.ca/academic-integrity/ for more information.]

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.

Discipline: A student is expected to know what constitutes academic integrity [check https://uwaterloo.ca/academic-integrity/] to avoid committing an academic offence, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about 'rules' for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate Associate Dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.

Appeals: A decision made or penalty imposed under Policy 70 (Student Petitions and Grievances) (other than a petition) or Policy 71 (Student Discipline) may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.

MOSS (Measure of Software Similarities) is used in this course as a means of comparing students' assignments to ensure academic integrity. We will report suspicious activity, and penalties for plagiarism/cheating are severe. Please read the available information about academic integrity very carefully.

Discipline cases involving any automated marking system such as Marmoset or MarkUs include, but are not limited to, printing or returning values in order to match expected test results rather than making an actual reasonable attempt to solve the problem as required in the assignment question specification.

Note for Students with Disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:

• Lecture content, spoken and written (and any audio/video recording thereof);
• Lecture handouts, presentations, and other materials prepared for the course (e.g., PowerPoint slides);
• Questions or solution sets from various types of assessments (e.g., assignments, quizzes, tests, final exams); and
• Work protected by copyright (e.g., any work authored by the instructor or TA or used by the instructor or TA with permission of the copyright owner).

Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).

Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).

Nearly everything in this file is already above, but the University requires me to link to it anyway.