CS140: Homework 9

  1. Go to the Big-O notes for March 1 and compute T(n) and the Big O running times of linear2.c, log.c, nlogn.c, and nsquared.c.

  2. Consider the following program:
    	main(int argc, char *argv[]) {
    	    IS input = new_inputstruct(argv[1]);
    	    Dllist words;
    	    Dllist words_ptr;
    	    int i;
    	    while (get_line(input) >= 0) {
    		for (i = 0; i < input->NF; i++)
    		    dll_prepend(words, input->fields[i]);
    	    dll_traverse(words_ptr, words) {
    		printf("%s\n", dll_val(words_ptr));

  3. Consider the following function:
    	void silly_print(int n) {
    	    int i, j;
    	    for (i = 0; i < n; i++) {
    		for (j = 1; j < i; j *= 2) {
    		    if ((j*i)%3 == 0) {
    			printf("%d*%d is divisible by 3\n", j, i);
    		    else {
    			printf("i = %d\n", i);
    			printf("j = %d\n", j);
    			printf("i * j = %d\n", i*j);

  4. Write a function called init_array that takes two parameters, an integer that denotes the size of the array and a pointer that will be a pointer to the elements of an integer array. init_array should read the size of the array from stdin and assign the size to the size parameter. It should then malloc an array of integers of the desired size and assign the pointer to the array pointer. The trick to this problem is that init_array should modify the memory locations of the arguments that are passed to it. For example, suppose I have the following mini-program:
    	main() {
    	    int array_size;
    	    int *int_array;
    	    // the ? mark constitutes part of the question
    	    init_array(&array_size, ?int_array);
    When init_array returns, array_size should contain the size of the array and int_array should point to the malloc'ed block of integers.

    1. Write the init_array function, including the header. Normally I would give you the header but in this case part of the problem involves figuring out how the parameters should be declared.

    2. Write down what the ? in front of int_array should be. You should choose among &, *, and nothing (i.e., between &int_array, *int_array, or int_array).

  5. Consider the following function:
    	void read_items(int *age, float *pay, char *name) {
    	    scanf("%d", age);
    	    scanf("%f", pay);
    	    scanf("%s", name);
    and the following mini-program:
    	typedef struct {
    	    int age;
    	    float salary;
    	    char name[20];
    	} person;
    	main() {
    	    person *p;
    	    p = (person *)malloc(sizeof(person));
    	    read_items(                                    );
    Fill in the argument list for read_items so that age, pay, and name get assigned to the corresponding fields in the person struct associated with the pointer p.

  6. Write a program that prints out a list of the longest words in a file that is read from stdin. Your program should use the fields and dllist libraries. You do not need to compile or execute the program. As an example, given the input:
    	The swift, red fox leaped
    	the purple fence
    your program would output:
    since the longest word in the file is six characters. You should be able to write your program without reading the file twice.