Computer Science 269
Introduction to Data Structures
Summer 2002
Assignments

Revised August 14, 2002

United States Government Dictionary of Algorithms and Data Structures

• It is expected that students will discuss the assignments. But do not turn in code written by another person. If that happens, both persons are violating the ethics of this course.
  It is unadvisable for you to allow another student to have an electronic copy of your work, as then you would unwittingly be a party to a breach of ethics. Showing the other student a hard copy is far less dangerous.
  The above rule does not apply to copying files that I have made publicly available. I expect that you will use those in their original form or with appropriate modifications (made by just you, of course).
• Wednesday July 17, 2002. Homework due. Assignment 1 will be due in class today.
• Friday July 19, 2002. There will be a very short test in class today. It will be at the beginning of the class period, and will cover material we've discussed during the week. Lecture will continue as usual after the test.
• Monday July 22, 2002.
  Assignment 2 is due midnight today.
• Friday July 26, 2002.
  Today there will be two topics of discussion.
  The first part of the lecture will be on hashing.
  After the midlecture coffee and cakes, the topic will be heaps.
• Monday July 29, 2002.
  Today we will continue the discussion on hashing.
  We will also continue the discussion of the ADT Array.
  After the middle "break," we will begin discussion of sorting algorithms.
  We will define and analyze notorious Bubblesort.
  We then will define Selection Sort and Insertion Sort, and give old and improved versions of each.
  Assignment 3 is due midnight today.
• Tuesday July 30, 2002. Today We will continue discussion of sorting algorithms.
  We will define and analyze Mergesort and Quicksort.
  After the middle "break," we
• Wednesday July 31, 2002. Today We will continue discussion of sorting algorithms.
  We will discuss Quicksort in depth, and also define Polyphase Mergesort.
  Today we will discuss 2-3 trees.
  We will discuss Union/Find, and give an application: finding a minimum spanning tree.
• Thursday August 1, 2002.
  We also discuss Radix Sort, or Binsort.
  Assignment 4 is due midnight today.
• Friday August 2, 2002.
  Today we will continue the discussion of representation of graphs and directed graphs, and of graph algorithms.
  We will begin discussing dynamic programming.
• Monday August 5, 2002. There will be a test in class today. It will be at the beginning of the class period, and will cover material we've discussed so far.
• Tuesday August 6, 2002.
  Today we will review material that was on the test yesterday.
  Assignment 5 is due midnight today.
• Wednesday August 7, 2002.
  Today we will continue the review of material that was on the test Monday, as well as other material that we have covered so far this term.
• Wednesday August 14, 2002.
  Today we will discuss the Huffman algorithm for optimal prefix coding. This is a greedy algorithm.
  We will discuss some applications of dynamic programming, including a dynamic programming algorithm for optimal alphabetic prefix codes.
  If time permits, we shall discuss the Hu-Tucker algorithm, a greedy algorithm for optimal alphabetic prefix codes. It took me years to grasp why this algorithm is correct, and no one I've ever spoken to thinks it's easy to prove correctness, not even S.-T. Hu himself.
  But the algorithm itself is easy.
• Final Examination: Friday, August 16, 11:20 AM Old Exams.
  Assignment 6 due at midnight tonight.