CompSci 161 Homework Assignments - Fall, 2023 (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 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, October 11.

• 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.
  • Using the definition of "big Oh", show that 5n² -2n +5 is O(n²). Give an explicit value of C and a corresponding value of n₀.
  • [GT] Exercises 1.6.2 (see note), 1.6.3, 1.6.4, 1.6.5, 1.6.8.
    Note: The MaxsubSlow algorithm appears in the text as Figure 1.4.2 in Section 1.4.
  
  
• Homework 1: Due Wednesday, October 11, at 6:55PM.
  • [GT] Exercises 1.6.7; 1.6.9; 1.6.11 (see note below); 1.6.13; 1.6.15; 1.6.17; 1.6.36; 1.6.52; 1.6.59
  Note: 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 2: Due Wednesday, October 18, at 6:55PM.
  • Homework 2 Problems, problems 1 - 10.
  
  
• Homework 3: Due Wednesday, October 25, at 6:55PM.
  • Homework 3 Problems, problems 1 - 5.
    Note: Updated version posted October 21 at 6PM to clarify that Problem 3 is asking for a max-heap.
  
  
• Homework 4: Due Wednesday, November 1, at 6:55PM.
  • Homework 4 Problems, problems 1 - 4.
  
  
• Homework 5: Due Wednesday, November 8, at 6:55PM.
  • [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)
  • [GT] Exercise 11.6.1; (see Notes below)
  • Additional Homework 5 Problem, problem 1.
  • 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 class and in the class notes.
    • For 11.6.1:
      • "characterize" means give an asymptotic solution to the recurrence equation.
      • Even though the directions in the problem say "using the master method," it is fine to use the simplified method instead in the parts where it can be used.
  
  
• Homework 6: Due Wednesday, November 15, at 6:55PM.
  • The following problems are required, including the "additional problems."
    • 12.8.6 (see Note below)
    • Additional Homework 6 Problems.
    • Notes:
      1. For 12.8.6, the "telescope scheduling problem" in the text is the "weighted interval scheduling problem" in the notes. In the terminology of the class notes, each triplet represent an interval or task, and the three components of the triplet are the start time, the finishing time, and the value of the interval/task.
  
  
• Homework 7: These problems will not be collected and they will not be graded. The solutions will be posted sometime during the week of November 20, possibly during the long Thanksgiving weekend.

  Please note that while these problems are not being collected, it is important to work through them and understand the solutions. Some of the problems involve constructing a table. While it is probably not necessary to construct every entry in the table by hand to gain the full benefit of doing the problem, make sure that you understand the problem well enough that you could construct the entire table by hand if you spent enough time on it. As I said in class on Friday November 17, you are very likely to see test problems where you are given a partially filled table for some of these problems and asked to compute some of the missing missing entries.

  Here are the problems. Earlier I just posted the problems from the text and said that I would add a few more problems later. These problems have now been added.
  • 12.8.1; 12.8.5; 12.8.9 (see Notes below)
  • Additional Homework 7 Problems.
  • Notes:
    1. The ordering of the three problems in the text corresponds to the order in which the relevant topics are covered in the text. If you want to do the problems in the order in which we covered the relevant material in the lectures and the notes, the order to do them in would first 12.8.5 and 12.8.9, then 12.8.1.
    2. For 12.8.5, 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.
  
  
• Homework 8: Due Wednesday, November 29, at 6:55PM.
  • 13.7.1; 13.7.2; 13.7.4; 13.7.7; 13.7.10
  
  
• Practice problems for midterm 2. These problems will not be collected and they will not be graded. We recommend you do them before midterm 2. The solutions have been posted.
  • Problems.
  
  
• Practice problems for the final . These problems will not be collected and they will not be graded. We recommend you do them before the final. The solutions have been posted.
  • Problems.

Last modified: December 10, 2023