Computer and Logic Essentials Assignment
Aim
This assessment task allows you to demonstrate your problem solving ability on problems covering algorithms, data representation and sets.
Part 1: Algorithms
a) A transport consultant has created a file of information about trips collected from individuals who have participated in a survey. This information includes start_time and end_time variables. One of the items contained in the file is the duration of each trip (that is, end_time - start_time) in minutes. The consultant is trying to work out how to calculate the number of trips with duration greater than 60 minutes (that is, how many trips take longer than an hour) and requires your assistance to develop an algorithm. You can assume that the durations are read one at a time and should only be read until EOF (end of file) is reached.
i. Develop a flowchart to show your algorithm, using the diagrammatic conventions described in the lecture notes/slides.
ii.Translate your flowchart into pseudocode, following the conventions described in the lecture notes/slides.
The remainder of part 1 deals with the following pseudocode:
procedure mystery: start
stop
read n
read list x1, x2, x3, ... xn myvar <- 0
do i <- 1 to n by 1
do j <- i+1 to n by 1 if xi > xj
myvar <- xi end if
end do end do
stop
b) Noting any assumptions on your part, what does this procedure do? Explain succinctly (that is, do not explain the pseudocode line by line) in no more than three well-written sentences.
c) Using big O notation, what is the likely complexity of this algorithm? d)
i. Taking into account what the algorithm should do, write an improved version of this algorithm in pseudocode.
ii. Briefly describe your changes using dot points.
iii. Provide the likely complexity of the improved version using big O notation (note it can stay the same, but should not get worse).
Part 2: Data representation
Your responses to the following questions must show your reasoning (or working out). No marks will be provided for correct answers alone. Non-decimal numbers have a prefix indicating their base.
a) Convert the following unsigned binary numbers to decimal and then to hexadecimal: i. 0b11110101
ii. 0b101110.101 iii. 0b1110001.01
b) Convert the following binary numbers to decimal, taking into account their representation as noted:
i. 0b11111010 (sign magnitude)
ii. 0b11001101 (two's complement representation)
c) Perform the binary addition of the unsigned values: 0b10101101 + 0b111000 + 0b1000000
and convert the result to decimal.
d) Obtain the decimal value of the following expression: 2(0x4FB) + 53 + 0x915
Part 3: Sets
Returning to the data file from question 1a), the survey data also contains information about combinations of transport modes that participants used throughout the day. For this question, we will focus only on walking (W), driving (D) and train (T) (apologies in advance to advocates of other modes).
Taking a sample of 4000 participants, the number of respondents who used each combination of these modes on their survey day are as follows:
|
Mode usage
|
Number of participants
|
|
Walking and driving
|
250
|
|
Driving and train
|
600
|
|
Walking and train
|
350
|
|
Walking
|
950
|
|
Train
|
1150
|
|
Driving
|
1100
|
|
Walking, driving and train
|
100
|
a) Draw a Venn diagram to represent this data.
b) Calculate the percentage results of the survey for each query. Show how your percentage was calculated.
i. Participants who walked only.
ii. Participants who drove or used the train.
iii. Participants who used only one mode of transport.
iv. Participants who used at least one of these modes.
v. Participants who used another mode not covered in this question or did not travel at all.
c) Provide the set notation for the following subsets:
i. Participants who drove or walked.
ii. Participants who both drove and used the train.
iii. Participants who didn't use the train nor drove.
iv. Participants who walked and used at least one other mode.
v. Participants who walked only.