﻿ CS 136 Assignment 8

# CS 136 Assignment 8

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

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

### Assignment 8 Problem 0. [10 Marks correctness]

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 ints 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```

### Assignment 8 Problem 1. [20 Marks correctness+efficiency; 10 Marks testing + hand mark]

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

### Assignment 8 Problem 2. [20 Marks correctness+efficiency; 10 Marks hand mark]

Write a program sort.c that reads a sequence of non-negative ints 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```

### Assignment 8 Problem 3. [20 Marks correctness+efficiency; 10 Marks hand mark]

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