Appendix F — Assignment F

Instructions

1. You may talk to a friend, discuss the questions and potential directions for solving them. However, you need to write your own solutions and code separately, and not as a group activity.

2. Do not write your name on the assignment.

3. Make R code chunks to insert code and type your answer outside the code chunks. Ensure that the solution is written neatly enough to understand and grade.

4. Render the file as HTML to submit.

5. There are 10 points for cleanliness and organization. The breakdown is as follows:

• Must be an HTML file rendered using Quarto (2 pts).

• The table of contents appears in the file (2)

• There aren’t excessively long outputs of extraneous information (e.g. no printouts of unnecessary results without good reason, there aren’t long printouts of which iteration a loop is on, there aren’t long sections of commented-out code, etc.). There is no piece of unnecessary / redundant code, and no unnecessary / redundant text (2 pt)

• The code follows the tidyverse style guide for naming variables, spaces, curly braces, etc. (2 pt)

• The code should be commented and clearly written with intuitive variable names. For example, use variable names such as number_input, factor, hours, instead of a,b, xyz, etc. For repetitive code chunks, either copy the comments or just leave a comment mentioning that the comment is the same as in the previous occurrace of the code chunk (2 pts)

• 2 points will be deducted for every question, where you have not printed out the final answer, and the grader needs to execute your code to check the answer.

• 2 points will be deducted for every question, where you have hard-coded the final answer. For example, if the final answer is 10, then you can’t say, print(10). Your code must execute correctly to print out the final answer.

6. The assignment is worth 100 points, and is due on 5th March 2024 at 11:59 pm.

7. You are not allowed to use a for loop in this assignment, except in the last question on Sudoku.

F.1 TED Talks

Execute the following code to get the object ted_talks, which contains information about TED talks.

Note that you are not allowed to use a for loop or any other kind of loop in all the questions below.

library(rjson)
ted_talks <- fromJSON(file = 'TED_Talks.json')

F.1.1 Number of talks

How many TED talks are there in the data?

(1 point)

F.1.2 Average number of views

What is the mean number of views of the TED talks?

(3 points)

F.1.3 Highest number of views

Find the headline, year_filmed, and number of views of the top five talks with the highest number of views.

Reminder: Do not use a for loop or any other kind of loop.

(9 points)

F.1.4 Most Funny votes

Find the headline, year_filmed and count of Funny votes of the top five talks with the highest number of Funny votes

Reminder: Do not use a for loop or any other kind of loop.

(12 points)

F.1.5 Highest proportion of Inspiring votes

Find the headline, year_filmed, and proportion of Inspiring votes from among all the votes for the talk, of the top five talks with the highest proportion of Inspiring votes.

Reminder: Do not use a for loop or any other kind of loop.

(12 points)

F.1.6 Most popular voting category

Add the votes of all TED talks for each category. Which category has received the most votes? What proportion of the total votes have been received by this category?

Reminder: Do not use a for loop or any other kind of loop.

(10 points)

F.2 Binary search

Execute the code below to get the object wordlist_global, which contains a vector of words. Write a recursive function that accepts a word, say word_to_search and a vector of words, say wordlist as arguments, and finds if the word_to_search occurs in wordlist_global or not. This is very simple to do with the code word_to_search %in% tuple_of_words. However, this code is unfortunately very slow.

As the words in wordlist_global are already sorted in alphabetical order, we can search using a faster way, called binary search. To implement binary search in a function, start by comparing word_to_search with the middle entry in the wordlist_global. If they are equal, then you are done and the function should return TRUE. On the other hand, if the word_to_search comes before the middle entry, then the function must call itself to search the first half of wordlist_global. If it comes after the middle entry, then the function must call itself to search the second half of wordlist_global. In every recursive call, the function must repeat the process on the appropriate half of the wordlist and continue until the word is found or there is nothing left to search, in which case the function should return FALSE. The < and > operators can be used to alphabetically compare two character objects.

Note that your function must use recursion.

F.2.1 Word search check

Check your function if the word_to_search is:

1. 'agreement'

2. 'aghast'

3. 'qualifier'

wordlist_global<-unlist(read.table('wordlist.txt', header = FALSE, sep = "", dec = "."))

Reminder: Do not use a for loop or any other kind of loop.

(15 points)

F.2.2 Number of iterations

Update the function to also print the number of iterations it took to find the word_to_search or fail in finding the word_to_search.

Check your function if the word_to_search is:

1. 'agreement'

2. 'tiring'

3. 'qualifier'

Hint: You can update a global variable inside the function using the <<- operator.

Reminder: Do not use a for loop or any other kind of loop.

(3 points)

F.2.3 Index of word_to_search

Update the function in the previous question to also print the index of word_to_search in wordlist_global if the word is found. For example, the index of ‘abacus’ is 1, the index of ‘abdomen’ is 2, and so on.

Check your function if the word_to_search is:

1. 'agreement'

2. 'tiring'

3. 'qualifier'

Reminder: Do not use a for loop or any other kind of loop.

(6 points)

F.3 Sudoku

This question is about solving the Sudoku puzzle with recursion. Read about Sudoku here. Think about how to solve the Sudoku puzzle with recursion.

This blog provides a recursive function solve_sudoku() to solve the Sudoku puzzle. Read the blog and understand the recursive function. You will need to add some lines in the function to answer some of the questions below.

F.3.1 Base case & recursive case

What are the base and recursive cases of the function solve_sudoku()? Cite the relevant lines of code, and explain.

(2 points)

F.3.2 Solving sudoku

Use the function to solve the following Sudoku puzzle. Execute the following lines of code to see the puzzle.

# Plotting the Sudoku puzzle (without solution). 

board <- matrix(c(rep(0, 4), 3, rep(0, 3), 1, 9, 8, rep(0, 4), 6, rep(0, 5), 8, 0, 7, rep(0, 5), 6, 2, 0, 4, 0, 7, 0, 0, 4, rep(0, 4), 9, 6, 0, 0, 7, 0, 5, 0, 3, 4, 8, rep(0, 6), 1, rep(0, 5), 7, rep(0, 4), 5, 9, 5, rep(0, 3), 7, rep(0, 4)), 9, 9)

plot(c(0, 9), c(0, 9), type = "n", xlab = "", ylab = "", main = "Sudoku puzzle",
     xaxt = "n", yaxt = "n", bty = "n", asp = 1)

for (i in 1:9) {
  for (j in 1:9) {
    rect(i - 1, j - 1, i, j)
    if (board[10 - j, i] != 0) {
      text((i - 1) + 0.5, (j - 1) + 0.5, (((board[10 - j, i]))))
    }
  }
}

for (i in 1:3) {
  for (j in 1:3) rect((i - 1) * 3,(j - 1) * 3,3 * i,3 * j, lwd = 2)
}

After using the function to solve the puzzle, execute the following lines of code to print the solution:

# Plotting the Sudoku puzzle with solution. 
# The matrix 'result' must contain the solution

plot(c(0,9), c(0,9), type = "n", xlab = "", ylab = "", main = "Sudoku solved",
     xaxt = "n", yaxt = "n", bty = "n", asp = 1)

for (i in 1:9) {
  for (j in 1:9) {
    rect(i - 1, j - 1, i, j)
    if (board[10 - j, i] != 0) {
      text((i - 1) + 0.5, (j - 1) + 0.5, (((board[10 - j, i]))))
    } else {
    text((i - 1) + 0.5, (j - 1) + 0.5, (((result[10 - j, i]))), col = 2, cex = 1.25)
    }
  }
}

for (i in 1:3) {
  for (j in 1:3) rect((i - 1) * 3, (j - 1) * 3, 3 * i, 3 * j, lwd = 2)
}

(4 points)

F.3.3 Number of recursive calls

How many times does the function solve_sudoku call itself to solve the puzzle?

(3 points)

F.3.4 Number of calls for each cell

Create and print a \(9 \times 9\) matrix that contains the number of times the function calls itself to try a digit for the respective cell in the puzzle.

(5 points)

F.3.5 Reducing recursive calls

Analyze the matrix created in the previous question. Edit the function to reduce the number of recursive calls it takes to solve the puzzle. Your approach must be general and not specific to this particular puzzle. However, you will demonstrate your approach on this puzzle.

Find the number of times the functions calls itself with the improved sudoku solver to solve the given puzzle.

(8 points)

F.3.6 Benefit of recursion

What challenges will you face if you try to solve this problem without recursion?

(2 points)