Assignment #1 Solution

$30.00

Description

Goal:

Understanding of merging and mergesort.

Requirements:

  1. Design, code, and test a C program to mergesort a set of intervals of positive rational numbers. The first line of the input will be n, the number of intervals in the remaining n input lines. Each input interval will have four non-zero integer

values: num _ left den _ left num _ right den _ right . If num _ left is positive, then the left end of the interval

is closed at

num _ left

, otherwise the left end of the interval is open at

num _ left

. Similarly, if

num _ right is

den _ left

den _ left

num _ right

positive, then the right end of the interval is closed at

, otherwise the right end of the interval is open at

den _ right

num _ right . den _ left and den _ right will always be positive, each fraction is in reduced form, and every

den _ right

interval includes at least one number.

The input should be read from standard input (which will be one of 1. keyboard typing, 2. a shell redirect (<) from a file, or 3. cut-and-paste. Do NOT prompt for a file name!).

The first line of the output is the number of intervals in the output. Each of the remaining output lines contains four integer values according to the input conventions. In addition to being sorted, adjacent intervals in the output should not overlap or “touch” since your merge routine is expected to clean up such situations. Your code should take Θ(n log n) time.

  1. Submit your C program on Blackboard by 1:45 p.m. on September 21. One of the comment lines should include the compilation command used on OMEGA.

Getting Started:

1. Sample input:

5

(

2

,

19

)

-2 3 -19 3

3

3

-7 1 81 10

(

7

,

81

]

1

10

1 30 -3 4

[

1

,

3

)

30

4

-1 50 -1 40

(

1

,

1

)

50

40

19 3 -7 1

[

19

,

7

)

3

1

Sample output:

3

(

1

,

1

)

-1 50 -1 40

50

40

1 30 -7 1

[

1

,

7

)

30

1

-7 1 81 10

(

7

,

81

]

1

10

  1. Your program should not use floating point values, i.e. do not use division!

  1. You can get started by using the mergesort code on the course webpage.

  1. All input integers will be in the range -32767 .. 32767, not including 0.