CS 222   Fall 2005,  Instructor:  Jeffrey Horn

General Student Concerns:     Colloquia and Seminars      Local Events        NMU CS Employment

ANNOUNCEMENTS (Wednesday, November 30, 2005)

What's REALLY New:

• HW6 is officially assigned today.  See below.

• Added big file of URLs to test our algorithms....(thanks, Alex) here
  HW5 (prog4) written up, just as assigned in class. Due when you get back from Thanksgiving break
  HW4 (prog3) due date has been fixed: Friday, Oct. 21, 2005! That gives us two lab days. Get to it!
• Added HW4 (program 3) HASH TABLE.  See below.  Tentative.  Not officially assigned until Friday, Oct. 7, 2005!
• Added HW3 (program 2) BINARY SEARCH.  See below.
• Welcome to class!

CONTENTS

• Syllabus
• Lecture Notes
• Homeworks & Programs
• SUPPLEMENTAL (C++ Programming, etc.)
• Tests and Quizes

LECTURE NOTES
 

• Homework 1 (program 1):  Here is the handout.
• Homework 2: 
  • Answer questions 16 and 17 on page 109 of Carrano.
  • Assigned:  Monday, Sept. 12, 2005
  • Due:  Friday, Sept. 16, 2005
• Homework 3 (program 2):    BINARY SEARCH
  • Here is the handout
  • Due:  Friday, Sept. 30, 2005
• Homework 4 (program 3):    HASH TABLE
  • Here is the handout
  • Due:  Oct.
• Homework 5 (program 4):  HEAPSORT
  • Take the code from HW5, hash table, which implements a web cache using hashing, and instead use binary search on a sorted array, with HEAP SORT used to sort the array. 
  • Make this implementation as efficient as possible.  What does this mean?  This means:
    1. You read in a file of unsorted URLs from a file.  Then use heap sort to sort the array. 
    2. Then use binary search for the "member" method.
    3. For inserts and deletes (or "remove"s), use binary search to find the position in the array to insert or delete/remove. 
  • One other requirement:  Create a separate class for HEAP, with the usual Heap methods (empty, insert, deleteMax).  You do not need to write "heapify" but you should know what it is!  Of course, feel free to write "print", "sizeOf", and other useful methods that help you diagnose and test your code.  Realize that you are storing pointers to WebPage objects, which hold URLs that are your sort key.  Hardwire the Heap class to sotre WebPage pointers.  You do not have to write a destructor for this class.  Understand also that your actual sorting code goes in to a "heapsort" method in your "WebCache" class, or whatever you want to call it.  Thus the heap sorting code is in a separate class from the Heap code!
  • Due:  Tuesday after Thanksgiving break, NO LATER!  (that's Tuesday, Dec. 1, 2005)
• Homework 6:  BALANCED TREES
  • Assigned:  Wednesday, Nov. 30, 2005
  • Due:   Wednesday, Dec. 7, 2005
  • Refer to 12.1 of text.
  • Pages 722-723:  do #1, #2, #3, #5, #6

TESTS AND QUIZES
 

FINAL