Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP20007 – Ed Lessons 2 Z
Question 2: Colourful Study Notes
Assignment 2
General
Question 1: Quasi-
balanced Search Trees
Question 2: Colourful
Study Notes
Assignment Submission
Academic Honesty
Late Policy and Protected
Industrial Action
Requirements: C
Programming
Programming Style
Mark Breakdown
Additional Support
Question 2: Colourful Study Notes
Tala is studying very hard for COMP20007. They read the corresponding book chapters every week to consolidate
their understanding of the subject material.
To help with their studying. Tala likes to use highlighters of dierent colours. Here is an example, taken from the
chapter on Brute Force methods:
In this example, Tala used blue to highlight the words "brute force", yellow to highlight the word "problem" and
green to highlight "problem statement".
After doing this manually for years, Tala had the idea to write a program that automatically highlights terms. To do
this, they used a program to read their past notes and check, for each word, how many times it was highlighted.
This led to a collection of tables, one per word, with scores relative to how frequent that word was highlighted and
which colour. For example, for the word "problem", the table looks like this:
In this example, yellow has a larger score because it is the most frequent colour the word "problem" appears in
Tala's notes. Note there is also a row for no colour, meaning the word is not highlighted. After using the program
to read their notes, Tala ends up with a set of tables like the one above, one per word.
Part A (code)
For the rst automatic highlighter program, you should implement a C program that reads as input:
- A sentence. This is just a sequence of words split by whitespace, with no punctuation marks.
- A set of word tables. The set will only contain tables for words that appear in the sentence. You can assume
there are only 4 colours and they are represented as integers from 0 to 3: 0 is "no colour", 1 is "green", 2 is
"yellow" and 3 is "blue".
Then, it generates as the output:
- A sequence of colours, one per word. This should be a sequence of integer values, where each integer represent
a colour, as above.
The output sequence of colours should follow an optimisation criterion: it is the sequence with the highest total
score. For Part A, the total score is the sum of individual scores per word. Formally speaking, assume a sentence
has n words, with each word w numbered from 1 to n. Assume F(n) gives the maximum score for a sentence, which
we dene as
F n =( ) WC w , c =
C=c ...c 1 n
max
i=1
∑
n
( i i) WC w , c
i=1
∑
n
c
max ( i )
where WC(w,c) corresponds to the score for colour c in word table w. The rst term states that our goal is to the
maximise the score given a sequence of words/colours The second term then simplies this to maximise the
score for each individual word/colour.
The equation above only gives the maximum score: your code should generate the sequence of colours that gives
this maximum score.
Part B (code)
Following testing of the previous program, Tala is a bit frustrated because it would always pick the same colour for
each term. But as show in the example above with the word "problem", sometimes the same word can be
highlighted with dierent colours, depending on the sentence.
To solve this problem, Tala introduces an extra colour transition table. This table gives scores for colours given
the previous colour. Here is an example:
In this example table, if the previous word is highlighted in blue and the current word is also blue (as in the "brute
force" example above), this transition gives a score of 10.