Assignment 2
Partial Order Graphs Data Structures and Algorithms
Change Log
We may make minor changes to the spec to address/clarify some outstanding issues. These may require minimal changes in your design/code, if at all. Students are strongly encouraged to check the change log regularly.?
18 September
Linked list ADT added to admissible ADTs.
16 September
Images modified to make clear which edges are included in a partial order graph.
Requirements for stages 1 & 2 clarified.
Version 1: Released on 14 September 2018
Objectives
The assignment aims to give you more independent, self-directed practice with
advanced data structures, especially graphs
graph algorithms
asymptotic runtime analysis
Admin
Marks 2 marks for stage 1 (correctness)?
3 marks for stage 2 (correctness)?
3 marks for stage 3 (correctness)?
4 marks for stage 4 (correctness)?
2 marks for complexity analysis?
1 mark for style?
———————?
Total: 15 marks
Due 23:59 on Monday 8 October (week 11)
Late 2.25 marks (15%) off the ceiling per day late?
(e.g. if you are 25 hours late, your maximum possible mark is 10.5)
Background
A partially ordered set?("poset") is a set S together with a partial order ? on the elements from?S.
A partial order graph?for a finite poset (S,?) is a directed graph ("digraph") with
the elements in S as vertices
a directional edge from s to t if, and only if, s ? t and s ≠ t
Example:
where
S = {1, 11, 13, 143}
s t iff s is a divisor of t
A?monotonically increasing sequence?of length?k?over a poset (S,?) is a sequence of elements from S,
s1 s2 … sk-1 sk
such that si?? si+1?and si?≠ si+1, for all i=1…k-1. Examples:
1 11 143 and 1 13 143 are monotonically increasing sequences of length 3 over the poset from above.
1 143??is a monotonically increasing sequence of length 2 over this poset.
Aim
Your task is to write a program?poG.c?for computing a partial order graph from a given specification and then find and output?all longest?monotonically increasing sequences that can be constructed over this poset.
Your program should:
accept a single positive number?p?on the command line;
compute the set Sp?of all (positive) divisors of?p;
Task A:
obuild and output the partial order graph over Sp?corresponding to a specific partial order (see below);
Task B:
ooutput all longest monotonically increasing sequences over this partial order.
Your program should include a time complexity analysis, in Big-Oh notation, for
1.your implementation for Task A, depending on the number?n?of divisors of?p?and the length?m?of the decimal?p;
2.your implementation for Task B, depending on the number?n?of divisors of?p.
Hints
You may assume that
the command line argument is correct (a number p ≥1);
p is at most 2,147,483,647 (the maximum 4-byte?int);
p will have no more than 1000 divisors.
If you find any of the following ADTs from the lectures useful, then you can, and indeed are encouraged to, use them with your program:
stack ADT : stack.h,?stack.c
ueue ADT : queue.h,?queue.c
list ADT : list.h,?list.c
graph ADT : Graph.h,?Graph.c
weighted graph ADT : ??WGraph.h,?WGraph.c
You are free to modify any of the four ADTs for the purpose of the assignment (but without changing the file names). If your program is using one or more of these ADTs, you should submit both the header and implementation file, even if you have not changed them.
Your main program file should start with a comment:?/* … */?that contains the time complexity of your solutions for Task A and Task B, together with an explanation.
Stage 1 (2 marks)
For stage 1, you should demonstrate that you can build the underlying graph correctly from all divisors of input?p?and the following partial order:
x ? y iff x is a divisor of y
All you need to do for Task B at this stage is to output all nodes of the graph in ascending order.
Here is an example to show the desired behaviour of your program for a stage 1 test:
./poG 121
Partial order:
1: 11 121
11: 121
121:
Longest monotonically increasing sequences:
1 < 11 < 121
Hint:?The only tests for this stage will be with numbers?p?for which the above order is identical to the stricter partial order for stages 2–4, and such that all of the divisors of?p?together form a monotonically increasing sequence.
Stage 2 (3 marks)
For stage 2, you should extend your program for stage 1 such that it puts an additional constraint on the partial order of the divisors of?p:
x ? y iff
?x is a divisor of y,?and
?all digits in x also occur in y
For example, 11 ? 143 since 1 is also contained in 143, but 16 ? 128 since 6 is not a digit in 128.
All you need to do for Task B at this stage is to find and oputput the path that starts in 1 and always selects the next neighbour in ascending order until you reach a node without outgoing edge.
Here is an example to show the desired behaviour of your program for a stage 2 test:
./poG 9481
Partial order:
1: 19 9481
19: 9481
499: 9481
9481: