Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
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
Marks2 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
Due23:59 on?Monday?8 October (week 11)
Late2.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.cfor 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 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 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
queue 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.