Recitation 4: Working with Abstract Classes, Problem Solving
Goals: The goals of this lab are to learn how to design and use abstract classes, and to solve problems with the use of accumulators.
1 Abstract Classes
The following class diagram represents a library system that records the books that have been borrowed. There are three kinds of books: regular books, reference books, and audio books.
Reference books can be taken out for just two days, while other kinds of books may be borrowed for two weeks. The overdue fees are 10 cents per day for reference books and regular books, and 20 cents per day for audio books.
Audio books and regular books have both authors and titles; reference books only have titles.
The day when the book is taken out and the day due are counted as days since the library opened on New Year’s Day in 2001. So, for example, an audio book taken out recently would be recorded as taken out on the day 8368 with due date on the day 8382.
+-------+
| IBook |
+-------+
/ \
---
|
---------------------------------------
| | |
+---------------+ +---------------+ +---------------+
| Book | | RefBook | | AudioBook |
+---------------+ +---------------+ +---------------+
| String title | | String title | | String title |
| String author | | int dayTaken | | String author |
| int dayTaken | +---------------+ | int dayTaken |
+---------------+ +---------------+Design the interfaces and classes that represent the library borrowing system.
Define the abstract class ABook and lift those fields that can be lifted to this class.
Design the method daysOverdue that consumes the number that represents today in the library date-recording system and produces the number of days this book is overdue. If the number is negative, the book can still be out for that many days.
Design the method isOverdue that produces a boolean value that informs us whether the book is overdue on the given day.
Design the method computeFine that computes the fine for this book, if the book is returned on the given day.
For all methods, think carefully whether they should be designed being implemented solely in the abstract class, implemented solely in the concrete classes, or implemented in the abstract class and then overridden in some of the concrete classes.
2 Problem Solving Practice
The rest of the lab will be dedicated to strengthening problem solving skills, in particular the use of accumulators. It will require you to create new classes as well as determine what helper methods would be appropriate.
Recall [Maybe X] from last semester; that is, a [Maybe X] is either an X or false. Design a [Maybe Int] interface and the relevant classes. Note that false is somewhat of a red herring here, as it just represents an absent value. Think about what kind of class would represent an absent value well.
Design a method on a list of integers which produces the integer (or a value indicating the list was empty) that appears in the longest consecutive sublist. For example, the list of 1,1,5,5,5,4,3,4,4,4 would produce 5 (note that ties are broken by the sublist that appears earlier in the list).
Design a class for a task. A task has an id (an integer) and a (possibly empty) list of prerequisites, represented as the ids of the tasks that need to be completed before that task is.
Design a method on a list of tasks which produces the list of the tasks one can complete from these tasks. You can assume all task ids are unique.
Before beginning to program, sketch the helpers you’ll need to solve this problem, and ask yourself some questions: can task dependencies be cyclic? Are any tasks guaranteed to be completable? Be sure to understand these questions and what they imply for your program, as well as your examples and test cases. Your method should be able to terminate no matter what list it is operating on.
Note that in the problem definition alone a list of tasks can represent two different things: the tasks the method is being called on, and the subset of those tasks that can actually be completed. Keeping track of what list of tasks means what as you complete the problem is essential.
Once you’ve finished the above problem, refine it so that the list produced is in the order that one would need to complete the tasks in if this is not already the case.