CompSci 161 Homework Assignments - Winter, 2025 (Dillencourt)

Homework is to be submitted electronically, using GradeScope. Click here for detailed instructions for submitting the homework and signing up for GradeScope.

NOTE: Even if you are not yet enrolled in the class, you can submit homework to GradeScope by following the instructions for submitting the homework.

For full credit, the homework must be submitted by the specified date and time. There will be a short grace period of unspecified duration (typically 30 minutes to an hour) during which the homework may still be submitted, with a 50% penalty. Once the grace period has expired, homework will not be accepted.

Homework assignments will generally be due Wednesday afternoon, BEFORE THE BEGINNING OF THE FIRST DISCUSSION SECTION. They will be released on or before Friday afternoon of the previous week.

For the rules on doing the homework and a few thoughts on how to get the most value out of doing the homework problems, click here.

Unless otherwise stated, all problems are from the required online textbook, [GT], Zybook edition. Note that in the Zybook edition of [GT], the homework exercises for each chapter apear in a dedicated section of that chapter, and inherit their numbers from the section in which they appear. For example, all homework exercises for Chapter 1 appear in Section 1.6, and are numbered as 1.6.1, 1.6.2, etc.

The first homework assignment, Homework 0, will not be collected. Homework 1 will be assigned during week 1 and will be due on Wednesday, January 15 AT !2:55PM, RIGHT BEFORE THE FIRST DISCUSSION SECTION STARTS.

• Homework 0: These problems are recommended but will not be collected. The problems may be discussed in the discussion sections. Solutions will be posted sometime before the start of week 2.
  • [GT] Exercises 1.6.2 (see note below); 1.6.3; 1.6.4; 1.6.5; 1.6.8; 1.6.11 (see note below); 1.6.13; 1.6.15
  • Notes:
    1. The MaxsubSlow algorithm appears in the text as Figure 1.4.2 in Section 1.4.
    2. The references to "Algorithm 1.6.1" in exercises 1.6.11 - 1.6.15 refer to Figure 1.6.1, which appears between Exercise 1.6.14 and Exercise 1.6.15.
  • Homework 0 Additional Problems.
  
  
• Homework 1: Due Wednesday, January 15, at 12:55PM. Turn in solutions to all problems (the problems from the text and the additional problems).
  • [GT] Exercises 1.6.7; 1.6.9; 1.6.17; 1.6.36; 1.6.52.
  • Homework 1 Additional Problems.
  
  
• Homework 2: Due Wednesday, January 22, at 12:55PM. [***Updated January 17***] Turn in solutions to questions 1 through 5, and question 6(a). Question 6(b) and question 7 are deferred to the next homework assignment.
  • Homework 2 Problems.
  
  
• Homework 3: Due Wednesday, January 29, at 12:55PM. Turn in solutions to all questions.
  • Homework 3 Problems.
  
  
• Homework 4: Due Wednesday, February 5, at 12:55PM. [***Updated February 3***] Turn in solutions to questions 1 and 2. Question 3 and question 4 are deferred to the next homework assignment.
  • Homework 4 Problems.
  
  
• Homework 5: Due Wednesday, February 12, at 12:55PM. Turn in solutions to all problems (the problem from the text and the additional problems).
  • [GT] Exercises 10.5.1 (see Note below); 10.5.3 (see Note below); 10.5.4 (see Note below); 10.5.11 (see Note below)
  • Homework 5 Additional Problems.
  • Notes:
    • For 10.5.1, the first number in each pair is the value of the object (the "benefit" in the terminology used in the textbook) and the second number is the weight.
    • For 10.5.3, solve both of the task scheduling problems discussed in the lectures and the class notes:
      • Find the minimum number of machines required to do all of the tasks (part (a))
      • Find a maximum-cardinality set of tasks that can be done on a single machine (part (b))
    • For 10.5.4:
      • The string is "dogs do not spot hot pots or cats" and does not include the quotes.
      • Blank spaces should be treated as characters
    • For 10.5.11: Again, "benefit" in the terminology used in the textbook is the same as the value of the object as used in the lectures and in the class notes.
  
  
• Homework 6: Due Wednesday, February 19, at 12:55PM. Turn in solutions to the first six questions.
  • Homework 6 Problems.
  • NOTE:
    • Questions 1 through 6 are to be turned in.
    • Questions 7 and 8 are recommended but not required. They are not to be turned in.
  
  
• Homework 7: Homework 7 will not be collected or graded. The questions will be posted incrementally. The solutions will also be be posted incrementally. All solutions will be posted before the second midterm.

  Please note that while these problems are not being collected, it is important to work through them and understand the solutions. Some of the questions involve constructing a memoization table. This can be tedious, and if you are sure you understand the process it is not necessary to construct the entire table by hand. However, FOR EACH SUCH QUESTION BE SURE THAT YOU UNDERSTAND HOW TO CONSTRUCT THE TABLE ENTRIES AND CAN DO SO CORRECTLY. On the second midterm and/or the final you may be asked to add entries to a partially filled table.

  • Part 1: Homework 7 Questions part 1 (reposted February 22)
    • NOTE: On February 22, I changed the template table to reflect the fact that p(0) is not defined. This was the only change from the original posting on February 20.
  • Part 2: (posted February 21)
    • [GT] Exercises 12.9.5 (see Note below), 12.9.9.
    • Note: in Exercise 12.9.5, the first number in each pair is the value of the object (the "benefit" in the terminology used in the ZyBook) and the second number is the weight.
  • Part 3: (posted February 24)
    • [GT] Exercises 12.9.1
  
  
• Homework 8: Homework 8 will not be collected or graded. This would have been Homework 7 part 4 if there had been one more lecture before the second midterm. The second paragraph in the lead-in to homework 7 applies to homework 8 as well.
  • Homework 8 Questions (posted March 2)
  
  
• Homework 9: Due Wednesday, March 12, at 12:55PM. Turn in solutions to all problems (the problem from the text and the additional problems).
  • [GT] 13.8.1; [GT] 13.8.2; [GT] 13.8.4; [GT] 13.8.7; [GT] 13.8.10.
  • Additional Homework 9 Questions
  
  
• Homework 10: Homework 10 will not be collected or graded. It consists of a few practice problems for the final exam. All solutions will be posted before the final exam.
  • Homework 10 Questions

Last modified: March 12, 2025