|
CS241 - Summer 2006 |
Syllabus (download) | Syllabus (view)
Homework 1 - Chapter 1
Due: Tues 30 May 06
1. R-1.2
2. R-1.10
3. R-1.12
4. C-1.8
5. P-1.3
Homework 2 - Chapter 2
Due: Mon 5 June 06
1. R-2.4
2. R-2.8
3. R-2.9
4. R-2.10
5. C-2.2
6. C-2.9
7. Program CALab
Homework 3 - Chapter 3
Due: Mon 12 June 06
1. R3.8
2. R3.9
3. R3.25
4. R3.26
5. R3.27
6. R3.28
7. R3.29
8. C3.1
9. C3.13
Homework 4 - Chapter 4
Due: Mon 19 June 06
1. R-4.8
2. R-4.9
3. C-4.2
4. C-4.5 (prep for problem 5)
5. P-4.1 (Submit .java files providing solutions to the puzzles for P-4.1)
Homework 5 - Chapter 4
Due: Mon 26 June 06 (or as soon as you can after that)
1. R-4.13
2. R-4.15
3. R-4.16
4. C-4.12
5. C-4.13
6. C-4.14
7. C-4.18
8. Implement a generic doubly-linked list (see Chapter 5 for a doubly-linked list ADT). The nodes of the list can store the one particular type of reference variable specified for the list.
9. Implement a multi-sort list. (I suggest you use the DLL from program 8 above to obtain the building blocks for your algorithms for adding and removing nodes from a doubly-linkid list.)
The concept is that we wish to have a list whose elements are sorted in 4 different ways: alphabetical, by most recently accessed node, by most frequently accessed node, and by assigned priority.
NOTE: "accessed" means a stored value (string datum or priority datum) was changed by a setter method.
So: we have one set of nodes, but a reference to the next node is made in such a way that you can go through the list
- alphabetically
- by encountering the most recently accessed node first, the next most recently accessed node second, the next third, etc.
- by accessing the most frequently accessed node first, the next most frequently accessed node second, etc.
- by accessing the highest priority node first, then next highest priority node second, etc.
Where there is a tie in the criteria, the new member of that sub-list is place after the existing member of that sub-list.
The key to setting it up is to make a proper node class. You can get the start of an idea from: MS_Node.java
So each node can set its nextAlphabetic reference to the next node in alphabetical order, its nextInPriority reference to the next node according the assigned priority values of the nodes, and so on.
In keeping with the indispensible principle of incremental implementation: I suggest solving the alphabetical part first, then add the state for a priority list and solve that. Then the "frequently" and "recently" aspects should be relatively straightforward to handle.
(Ask questions about this one in the lab. And a memory-box picture is very helpful in this project.)
Homework 6 - Chapter 5
Due: Wed 5 July 06
1. R-5.4
2. R-5.5
3. R-5.17
4. C-5.8
5. C-5.12
Homework 7 - Chapter 6
Due: Wed 12 July 06
1. R-6.4
2. R-6.10
3. R-6.12
4. R-6.14
5. R-6.17
6. C-6.3
7. C-6.4
8. C-6.8
9. C-6.28
Hint: the alternative to recursion is a loop, obviously. One possible loop body involves references to left-child and right-child; another involves the iterator in C-6.3; and another involves simulating recursion by using a stack the way the operating system uses the activation-record stack to manage method calls.
Homework 8 - Chapters 7, 8, 9
Due: Wed 26 July 06
1. R-7.10
2. R-7.11
3. C-7.16
4. R-8.4
5. R-8.5
6. R-8.6
7. R-8.7
8. C-8.2
9. C-8.7
10. R-9.1
11. R-9.3