CompSci 161 Homework Assignments - Fall, 2023 (Dillencourt)
The GradeScope code for this class is VBWXZD.
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
5n2 -2n +5 is O(n2).
Give an explicit value of C and a corresponding value of n0.
- [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 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 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:
- 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:
- 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.
- 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.
- 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.
Last modified: December 10, 2023