1. A nonstandard C++ extension adds syntax that allows a switch statement to work with the string type (instead of the primitive integer types). Explain how hash tables can be used by the compiler to implement this language addition.

2. An (old-style) BASIC program consists of a series of statements numbered in ascending order. Control is passed by use of a goto or gosub and a statement number. Write a program that reads in a legal BASIC program and renumbers the statements so that the ?rst starts at number F and each statement has a number D higher than the previous statement. You may assume an upper limit of N statements, but the statement numbers in the input might be as large as a 32-bit integer. Your program must run in linear time.