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