CECS 329 Weekly Exercises and Homework Assignments

• Exercise Set 5: Finite Automata: Core Exercises 1-10, Additional Exercises A and B
• Homework 3 (Due March 11th)
• Exercise Set 4: NP-Complete Problems: Core Exercises 1-13
• Exercise Set 3: Computational Complexity Theory Core Exercises: 1-10. For problems 3-9, first provide the size parameters and appropriate certificate for an instance of the decision problem, and compare your answers with those provided in the solution. Then study the verifier program provided in the solution and provide a big-O expression for the number of algorithms steps as a function of the problem's size parameters. Check your answer with the big-O answer provided in the solution.
• Exercise Set 2: Mapping Reducibility Core Exercises: 1-10
• Homework 1 (Due February 7th)
• Exercise Set 1: Logic Lecture Core Exercises: 1-11, Additional Exercises: A and B
• Homework 2 (Due February 24th)