|
Quick Links
Calendar
Categories
Archives
Statistics
Total entries in this blog:
Total entries in this category: Published On: Apr 12, 2005 10:13 AM |
Tue - April 12, 2005Extra Review SessionsThere will be one additional review
session on Monday April 18 from 10:30 -12:00.
There will also be a review session run by Prof. Mary McCollom on Wednesday April 20 at 2:00-4:00. Both reviews will take place in Goodwin Hall room 254. Posted at 10:13 AM Tue - April 5, 2005Experience Using C++I have been asked to report back to the
Chair of the School's Curriculum Committee on the outcome of using C++ in
CISC-235. I would appreciate if you could provide me with some feedback on this.
If you have an opinion that you would like to be heard please send me an e-mail
message. Alternately you can hand me your comments on paper if you wish.
Posted at 05:06 PM Mon - March 28, 2005Study Questions for quiz #3Practice Questions for Quiz
#3.
Heap Questions: Text Chapter 21 questions: 21.1, 21.2, 21.3, 21.6, 21.8, 21.10, 21.11, 21.12 B-Trees Questions: Use the definition of a B-Tree given below for the next two questions. A B-tree of order M is a M-ary tree, M >= 2 with the following properties: 1. The root has at least two subtrees unless it's a leaf. 2. Each non-root holds k-1 keys, and each non-root and non-leaf also holds k pointers to subtrees, where the ceiling of m/2 <= k <= m. 3. All leaves are on the same level. 4. The keys in each node are in non-decreasing order. 5. The children are in order: the keys in the first i children are less than or equal to the ith key the keys in the last m-i children are greater than or equal to the ith key Question 1. What is the maximum number of keys that a B-Tree of order 6 (at most five keys per node) and of height 4 hold? How many disk accesses in the worst case would be required to find any key, assuming one block on disk can hold one node? How many keys can a B-Tree of order m and of height h hold? Question 2. Construct a B-Tree of order 3 (at most two keys per node) first for the insertion sequence 1, 5, 3, 7, 2, 4, 6 and then for the insertion sequence 1, 2, 3, 4, 5, 6, 7. Which sequence of insertions is preferable? Why? External Merge Sorting Suppose that there are 32 records to be sorted and the data is stored on external memory. Using an I/O model where reading or writing one record counts as one external memory access answer the following questions. a) How many external memory accesses (reads and writes) are used to sort the data using a 2-way merge sort? Assume that all you can do in internal memory is compare two numbers and output the smallest. b) How many external memory accesses (reads and writes) are used to sort the data using a 4-way merge sort? Assume that all you can do in internal memory is compare four numbers and output the smallest. c) What if we have enough internal memory to make initial runs of 8 sorted records. How many external memory accesses (reads and writes) are used to sort the data using a 2-way merge sort? 4-way merge sort? d) Illustrate how the 2-way and 4-way merge sorts of part c) would work using the following set of random integers. 41 40 35 6 74 8 87 89 99 24 2 8 44 19 93 23 63 91 4 5 70 57 38 59 3 4 83 83 46 18 53 17 Posted at 08:20 PM Fri - March 18, 2005Two classes cancelled for Easter.The university is closed on Good Friday,
March 25, so there will no class. The university is open on Easter Monday, March
28. However I have cancelled class. For students who have labs on Mondays it is
likely that your lab will be held at the usual time on March 28.
Posted at 09:55 PM Thu - February 24, 2005Study questions for quiz #2Here are some questions you can work on
to prepare for quiz #2.
These questions are also posted at the WebCT site for this course. Quiz 2 Study Questions.pdf Posted at 05:38 PM Wed - February 9, 2005COMPSA Computing Career WorkshopWhat: Career Services
Workshop
Topic: Work and Grad School Options for Computing Students Date: Thursday, February 10th, 2005 Time: 4:45pm to 6:30pm Registration: Please follow the link to register. It is a first come first serve basis, to a maximum of 24 people. If you do register kindly come out to the event. http://careers.queensu.ca/students/workshops/index.asp Description: Career Services in association with COMPSA brings to you a workshop on information and techniques to begin exploring your options in the work force and in available Graduate studies. Hope to see you all there! Posted at 11:18 AM Wed - January 26, 2005New quiz datesTo provide a week of tutorials in which you can obtain help from the TAs with studying for the first quiz, the quiz has been moved one week later. You will now take your first quiz in your tutorial in week 5 instead of in week 4. The second quiz will also be moved one week later for the same reason, but the last quiz will not, since it's in week 12. Work on the quiz questions prior to your tutorial next week and then bring your questions about the ones you found difficult to solve, and obtain help from your TA. Posted at 10:47 AM Wed - January 19, 2005New Readings CategoryI will keep a cumulative list of readings
in the new Readings category of this blog.
Posted at 02:02 PM Tue - January 4, 2005 |
||||||||||||||