Due Friday, November 20 at 11:49 AM sharp.

Please read the preamble in Assignment 1.

In this assignment, you can only use the C language features introduced in **Sections 1–10**.

In your code, you do NOT have to check that the value returned from `malloc` (or `realloc`) is invalid (NULL).

You may assume that all C strings are null terminated: you do not have to assert this (and it's not possible to).

**Problem 0 is a "warm-up" question. You are allowed to collaborate with your fellow classmates and discuss the solution on piazza.**

Write a program `echo.c` that reads a sequence of non-negative `int`s from input, and prints the sequence three times -- forward, then reversed, then forward -- with one element per line. Your program must have O(`n`) running time and consume O(`n`) space, where `n` is the length of the input sequence. Include in a comment your argument showing that the time and space constraints are met.

You may use `getint.h`, `stdio.h` and `stdlib.h`, but you may not use `intpq.h`.

Sample Input

1 2 3

Correct output for sample input

1 2 3 3 2 1 1 2 3

Write a program `strecho.c` that reads a sequence of strings from input, and prints the sequence three times -- forward, then reversed, then forward -- with one element per line. A string is defined to be any sequence of non-whitespace characters; strings are separated in the input by one or more whitespace characters. Your program must have O(`n`) running time and consume O(`n`) space, where `n` is total number of characters in the input. You should not assume any limit on the number of elements in the input, or the size of any particular element. Include in a comment your argument showing that the time and space constraints are met.
You may use `getint.h`, `stdio.h`, `string.h`, `ctype.h`, and `stdlib.h`, but you may not use `intpq.h`.

Sample Input

fred betty wilma

Correct output for sample input

fred betty wilma wilma betty fred fred betty wilma

Write a program `sort.c` that reads a sequence of non-negative `int`s from input, and prints the sequence in ascending order, with one element per line. Your program must have O(`n` log `n`) running time and consume O(`n`) space, where `n` is the length of the input sequence. Include in a comment your argument showing that the time and space constraints are met.

You may use `getint.h`, `stdio.h` and `stdlib.h`, but not `intpq.h`.

Sample Input

3 2 1

Correct output for sample input

1 2 3

Write a program `strsort.c` that reads a sequence of strings from input, and prints the sequence in ascending lexicographic order (as defined by `strcmp`), with one element per line. A string is defined to be any sequence of non-whitespace characters; strings are separated in the input by one or more whitespace characters. Your program must have O(`n` log `n`) running time and consume O(`n`) space, where `n` is total number of characters in the input. You may make the simplifying [but not strictly true] assumption that the running time of `strcmp` is O(1). You should not assume any limit on the number of elements in the input, or the size of any particular element.

You may use `getint.h`, `stdio.h`, `string.h`, `ctype.h`, and `stdlib.h`, but not `intpq.h`.

Sample Input

fred betty wilma

Correct output for sample input

betty fred wilma