1 Learning Outcomes

2 The Story...

Figure 1: An interaction with ChatGPT

Researchers have spent decades of efforts on developing more and more powerful language models, to reach the large language models that we are now using today. In this assignment, we won’t drill into language models, and you don’t need to be an expert of AI to complete the assignment, as these are beyond the scope of this subject. Instead, we will study how a sentence is formed based on the probabilities of next words predicted by language models.

3 Input Data

There are three sections in the input data:

2. A total of n lines of word records representing the vocabulary of the language model. Each line repre sents a word, which contains an unique English word and a real number representing the probability of the word (e.g., from counting the word frequency of a collection of web documents – you don’t need to worry about where these numbers came from), separated by a white space.

There are two special “words” <start> (can think of it as “to capitalise” the first word in a sentence) and <end> (can think of it as period ‘.’), representing the start and the end of a sentence, respectively. These two special words are included in all input data, although their exact probabilities may vary across different input. Except for these two special words, you may assume that each English word contains at least 1 and up to 20 lower case letters.

3. An n x n matrix of transition probabilities which are non-negative real numbers. The number at row i, column j (0 ≤ i, j < n) represents the transition probability from word i (of the input list of words above, counting from 0; same below) to word j, that is, the probability of word j appearing right after word i in a sentence. Such transition probabilities again can be calculated (in practice, “learned” by an advanced machine learning model) from a collection of web documents.

In the sample input, the first 0.2 in row 1 (column 2) represents the transition probability from <start> (word 1) to “a” (word 2) – this means there is a 20% chance that a sentence starts with word “a’. Similarly, the 0.6 at row 2, column 7 means that, when “a” (word 2) appears in a sentence, there is a 60% chance that the next word in the sentence is “dog” (word 7).

Note: The transition probabilities in each row sum up to 1 (think about why), except for those in row 0 (representing transition probabilities from <end> to each word) which are all 0’s – we include this row in the input regardless, for ease of discussion. Similarly, all transition probabilities in column 1 are 0’s.

You may assume that the test data always follows the format above. No input validity checking is needed.

4 Your Task

4.1 Stage 1: Read the Words and Their Probabilities (5 Marks)

Given the word probabilities, a naive approach to generate texts is just to generate a sentence formed by the words of the highest probabilities. Your next step is to identify the top-10 words (excluding the specialwords <start> and <end>) with the highest probabilities. Then, output a “sentence” starting with <start>, followed by the top-10 words identified (by descending order of their probabilities), and ending with <end>. If the input has fewer than 10 words, your program output should include all words from the input.

For simplicity, you may assume that the word probabilities are all unique, except for those of <start> and <end> which do not need to be examined. You may create a copy of the array of words for sorting, since the subsequent tasks rely on the list of words in their original dictionary order.

The output for this stage given the above sample input is as follows (where “mac:” is the command prompt).

Like in Assignment 1, we will again use input redirection to feed test data into your program. Thus, you should still use the standard input functions such as scanf or getchar to read the data. You do not need to (and should not) use any file operation functions such as fopen or fread. Your program should not print anything except for the data requested to be output (as shown in the output example).

Hint: Note the newline character ‘\n’ at the end of a line if you use getchar to read the input. To sort the words, your may adapt the insertion sort code given on Ed (https://edstem.org/au/courses/19957/ lessons/72882/slides/487112), or use the qsort function given in stdlib.h (see https://people.eng. unimelb.edu.au/ammoffat/ppsaa/c/callqsort.c for an example).

You can also modify the stage_one function to read all input in one go. You can (and should) create further functions to complete the tasks when opportunities arise.

4.2 Stage 2: Read the Transition Probabilities (6 Marks)

The output for this stage given the above sample input should be:

Here, for word 1, that is, <start>, we examine row 1 of the transition probability matrix. The largest transition probability in this row is 0.4 (at column 16, counting from column 0), which corresponds to word 16 (“the”) in the input list of words. Thus, the most likely next word of <start> is “the”, outputted in the form of <start> -> the.

Hint: You should use double type to store the transition probabilities for best accuracy. Consider modifyingthe word_record_t structure to store the most likely next word for each word. This will simplify Stage 3.

4.3 Stage 3: Generate a Sentence with the Transition Probabilities (6 Marks)

The linked list should start with a node representing the special word <start>. Then, your function should iteratively add more words (that is, nodes) to the end of the linked list. In each iteration, the most likely next word (according to the transition probabilities read in Stage 2) of the current last word in the linked list should be added to the linked list. Following the sample input above:

Yes this stage can be done without using a linked list. However, we’d like you to practise using it. If youcomplete the stage without a linked list, a 2-mark penalty applies.

4.4 Stage 4 (For a Challenge): Generate a Sentence with the Transition Probabilities Using an Advanced Algorithm (3 Marks)

For example, suppose sentence = “<start> the answer to”. Then, last = 17, as the last word in sentence is “to”, which is word 17 in the input list of words. This variable will help us access the transition probabilities of the next words to be added to the sentence, that is, row 17 of the transition matrix. Variable probability = 0.4 × 0.6 × 1.0 = 0.24. Here, 0.4, 0.6, and 1,0 are the transition probabilities from <start> to “the”, “the” to “answer”, and “answer” to “to”, respectively.

2. Create two arrays of the sent_t type. Let us name these two arrays sents and new_sents. Array sents has a size of 2 – we only keep the top-2 best partial sentences generated at each iteration (detailed next), to reduce the computational costs. Array new_sents has a size of 2n – recall that n is the number of words in the input list. This array stores intermediate results in the generation process.

3. At start, sents has only one partial sentence (a sent_t record), where sentence = “<start>”, last = 1, and probability = 1.0 (so we can calculate products later), while new_sents is empty. We iteratively expand each partial sentence record in sents as follows.

4. At each iteration, for each partial sentence in sents:

(b) Otherwise, for each next word of word last with a non-zero transition probability, we create a new partial sentence record by adding the next word to the end of the partial sentence, and weadd the record to new_sents.

For example, given sentence = “<start> the answer to”, word last is “to”. There are three next words of “to”: “answer”, “life”, and “the” with transition probabilities of 0.1, 0.4, and 0.5, respectively. We create three partial sentence records for “<start> the answer to answer”, “<start> the answer to life”, and “<start> the answer to the”, with probabilities 0.24× 0.1 = 0.024, 0.24 × 0.4 = 0.096, and 0.24 × 0.5 = 0.12, respectively.

5. After all partial sentences in sents are processed, we take the two records in new_sents with the largest sentence probabilities and copy them back to sents, that is, these two are the partial sentences to be used for the next iteration. If there is a tie, the record added to new_sents earlier should be used. If there is only one record in new_sents, just copy the record to sent[0]. The algorithm then empties new_sents and goes back to Step 4. See Figue 2 next page for a running example of the algorithm. The process stops when both sentences in sents end with <end>, or 10 iterations have been completed.

The output of this stage is the sentence in sents[0] when the algorithm stops. If the sentence does not contain <end>, your program should output an <end> at the end.

Given the sample input above, the output of this stage is as follows.

At the end of your submission file, you need to add a comment that states the worst-case time complexity to run your Stage 4 algorithm, assuming N words in the vocabulary, maximum L words in the final output sentence, and top-K partial sentences to be kept after each iteration (these are considered variables and not constants; they cannot be omitted in big-O terms). For simplicity, you may assume that assigning the value of a sent_t variable takes O(1) time.

Figure 2: An example run of the Stage 4 algorithm: numbers on arrow are transition probabilities; numbers in parenthesis are sentence probabilities; words in red form the top-2 candidate sentences after each iteration.

5 Submission and Assessment

Submitting your code. You should put all your code for the assignment into a single file named program.c. To submit your code, you will need to: (1) Log in to LMS subject site, (2) Navigate to “A2” in the “Assignments” page, (3) Click on “Load A2 in a new window”, and (4) follow the instructions on the Gradescope “A2” page and click on the “Submit” link to make a submission. You can submit as many times as you want to. Only the last submission made before the deadline will be marked. Submissions made after the deadline will be marked with late penalties as detailed at the end of this document. Do not submit after the deadline unless a late submission is intended. Two hidden tests will be run for marking purposes. Results of these tests will be released after the marking is done.

You can (and should) submit both early and often – to check that your program compiles correctly on our test system, which may have some different characteristics to your own machines.

Testing on your own computer. You will be given a sample test file test0.txt and the sample output test0-output.txt. You can test your code on your own machine with the following command and compare the output with test0-output.txt:

mac: ./program < test0.txt /* Here ‘<’ feeds the data from test0.txt into program */

gcc -Wall -Wextra -Werror -Wno-newline-eof -Wno-unused-parameter -std=c17 -o program program.c -lm

The flag “-std=c17” enables the compiler to use a modern standard of the C language – C17. To ensure that your submission works properly on the submission system, you should use this command to compile your code on your local machine as well.

You may discuss your work with others, but what gets typed into your program must be individual work,not from anyone else.

The best way to help your friends in this regard is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions in “compare every pair” mode. See https://academichonesty.unimelb.edu.au for more information.

Deadline: Programs not submitted by 4pm Tuesday 27 May 2025 will lose penalty marks at the rate of 3 marks per day or part day late. Late submissions after 4pm Friday 30 May 2025 will not be accepted.

6 Extension and Special Consideration

2. Extension between 2 and 3 working days: You must follow the steps below and submit your appli cation prior to the assessment deadline.

• Check your eligibility.
• Prepare your supporting documentation.
• Submit an application.
• Receive an outcome (via email)

4. Special consideration and extensions of more than 10 working days: Applications for all other adjustment requests should be submitted via the Special consideration portal.

Applications must be submitted within four working days of the assessment due date or exam date. You can apply before the assessment due date if you know it will be impacted.

You can still apply if you miss the deadline, but you will be prompted to include a late reason and need to provide documentation explaining what impacted your ability to apply on time.

Full instructions can be found in the Extensions and Special Consideration page of the Faculty of Engineering and Information Technology:

And remember, Algorithms are fun!