CS140: Homework 9

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.
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));
	    }
	}
	
```
- Identify and correct the bugs in this program. You only need to correct the lines that are incorrect. Hint: there are two lines with buggy code on them.
- If we are trying to compute T(n) for this program, what constitutes n?
- What is the Big O running time of this program? Assume that get_line, dll_prepend, printf, and dll_traverse each require a single time unit each time they are called.

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);
		    }
		}
	    }
	}

What is T(n) for silly_print? Remember to assume the worst case for j.
What is Big O for silly_print?

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).

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.

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:
```
	swift,
	leaped
	purple
	
```
since the longest word in the file is six characters. You should be able to write your program without reading the file twice.