CS141 Lab 7

Class Webpage:  http://www.cs.ucr.edu/~jiang/141-homepage.html

For the labs of the seventh week:

• Go over some of the questions in the  midterm solutions

• Go over the  second programming assignment and a sample input. Here are three test files that you can use to test your programs, test0, test1, test2, and test3. The expected outputs for all these tests can be found here.

• Give some examples to illustrate the construction of AVL trees and 2-3 trees from an input sequence of integers, and show the consequence of a deletion operation. One could use Ex. 4 on p. 222 of Levitin.

• Review the data structure Heap, and give an example of the algorithm HeapBottomUp on p. 226 of Levitin and the algorithm Heapsort.

• In-lab exercise: Implement Heapsort in C++. You may assume that the input numbers are stored in an array of size n. Some more elaborate pseudo-code for Heapsort can be found in CLRS and other reference books.

TA: Provide some test data.

• For keen students:

  A linked list has a cycle if, starting from some node p, following a sequence of next links brings us back to p. Here p does not have to be the first node in the list. Write an O(n) time and O(1) (extra) space algorithm/C++ program to determine if a linked list is cyclic. Hint: move two pointers at different speeds. How do you argue that your algorithm runs in O(n) time?