CECS 329 Weekly Homework Assignments

Note: all starred (*) exercises represent practice problems for a particular core learning outcome. All other assigned exercises are considered "peripheral", and whose understanding may be assessed on an exam. Also, the range of exercises (a-b)* means that all exercises from a to b are core exercises. Exercises (including solutions) are located at the end of each lecture.

• Exercise Set 1: Turing Reducibility Lecture: 1-5, 7, (8-14)* Assessments: LO1, Exam 1
• Homework 1 (Due February 4th)
• Exercise Set 2: Mapping Reducibility Lecture: Exercises (1-7)*,8,10* Assessments: LO2, Exam 1
• Homework 2 (Due February 11th)
• Exercise Set 3: Complexity Theory Lecture: Exercises 1,2, (3-9)*, Assessments: LO3, Exam 1
• Homework 3 (Due February 18th)
• Exercise Set 4: Complexity Theory Lecture: Exercises (9-13)*, 18-23, Mapping Reducibility Lecture: Exercises (14-19)* Assessments: LO4, Exam 1
• Exercise Set 5: Finite Automata Lecture: Exercises (1-5)*, 6, (7-10)*, 11,12 Assessments: LO5, Exam 2
• Exercise Set 6: Finite Automata Lecture: Exercises (13-19)*, 20-27 Assessments: LO6, Exam 2
• Exercise Set 7: Finite Automata Lecture: Exercises 28*, 29* Assessments: LO7, Exam 2
• Homework 4 (Due March 25th)
• Exercise Set 8: Context Free Languages Lecture: 1*, 2*, Assessments: LO8, Exam 2
• Exercise Set 9: Turing Machines Lecture: Exercises (1-5)*, Computability Lecture: Exercises (1-3)*, 4-6 Assessments: LO9, Assessments: LO9, Final Exam
• Homework 5 (Due April 17th)
• Exercise Set 10: Computability Lecture: Exercise 7, (8-11)*, 14* Assessments: LO10, Final Exam
• Exercise Set 11: Computability Lecture: Exercises 12 and 13 on the S-M-N Theorem Assessments: Final Exam
• Homework 6 (Due May 8th)