Ritsumeikan University Graduate
AY2022 Entrance Examination

Master's Program
Graduate School ofInformation Science and Engineering
Advanced Information Science and Engineering Major
Major Subjects（Common Subjects・Specialized
Subjects）
Admissions

CourseExamination
Page

Regular Admissions（English-based Program）

AugustP.1～

February

P.22～

February（September 2023
Enrollment)

P.22～

Notes

July
（September 2022
Enrollment)International Student Admissions（English-based Program）

Information
Science andEngineering

AugustDecember
July（September 2022
Enrollment)

In-University Advancement Admissions（English-based Program）

July
February（September 2023
Enrollment)

Accelerated Learners (Grade Skippers)（English-based Program）

February

P.22～【How to read the front cover page】
×…Those for which the entrance examination questions were not created due to reasons such as the entrance
examination not being conducted, or those for which the examination questions are not disclosed.
Diagonal line…The test designed by each couse(a written test) has not been conducted.

Ritsumeikan University Graduate School

AY2022 Entrance Examination

Doctoral Program
Graduate School ofInformation Science and Engineering
Advanced Information Science and Engineering Major

Written Examination is not conducted for the Doctoral Program.

公開用 P.1

August 2022 Admissions

AY2023 Examination Questions for the Graduate School ofInformation Science and Engineering, Ritsumeikan University(Master’s Program)

Major in Information Science and Engineering
Information Science and Engineering Course【 How to answer questions】
Please follow the instructions below and answer the questions.
Choose two questions from the common subjects and choose either the Computer Science sectionor the Human Information Science section.
In case choosing the Computer Science sectio n, answer three questions from question ④ ~⑨ .
In case choosing the Human Information Science section, choose one question either ⑩ or ⑪ .
There will be two blank answer sheets in case choosing the Human Information Science section.

CommonSubjects① Linear Algebra② Probability and Statistics③ Data Structure and Algorithms④ Computer Architecture⑤ Operating System⑥ Software Engineering
Computer Science

Specialized⑦ Computer Networks⑧ Databases

Subjects⑨ Artificial Intelligence
Human Information Science⑩ Image Processing⑪ Artificial Intelligence【 Examination time】
9:30-11:30 (120minutes)※ Leaving the examination venue is not allowed during the examination time.
※ In case you feel sick or need to go to the bathroom, let examination supervisors know
by raising your hand.

【 Notes】(1) Use one answer sheet for one question.
(2) Fill out your examination number and name for all the answer sheets. Also, make sureto fill out all the other necessary sections such as the questions number column.
(3) Do not remove the staple of your answer sheets.
(4) Answer sheets with no names will be invalid. Do not take the question sheets andanswer sheets with you after the examination.

公開用 P.2

Common Subjects①Linear Algebra②Probability and Statistics③ Data Structure and Algorithms

Choose two questions from the above.

公開用 P.3

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects① Linear Algebra
Answer all the questions below.
Question 1. Given the following matrix, findthat satisfies | |

1.

1 3
5 3 1
0 0 1
0 0 2

4
0
1
1

Question 2. Solve the following system of equations.

2
3
Question 3. Given the following matrices
Note that

and

and

3
2

2

9
2

2

3

3
2
11

, diagonalize matrix

are the eigenvectors for the eigenvalues
3 1
2 2

by

.
and

(

) of matrix, respectively.

公開用 P.4

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects②

Probability and Statistics

Answer all of the following questions with all calculation processes and concepts.
or probability density functions

Question 1. For each of the following probability functions

,
0,

(2)

!

exp

(3)
(4)

,

.
2| | .

exp.

Point A is initially at the origin-axis by Δ , determined by each fair die roll, from its current position.

0. After the dice rolls once, if the roll is 1 or 2, point A is not moved (Δroll is 3, 4, 5, or 6, point A is moved by Δ

1. Letbe the probability that point A is at0), else if theafter repeating the above

times.

(1)Find an expression for

(2)

Find

in terms of.

.

(3) Find the mean and standard deviation of.

Question 3. Suppose that a lottery has winning probability

and losing probability 1

draw the lottery 100 times and win 5 times.
(1) Find the log-likelihood function(2), find the2, 1,0,1,2.
the other integers

Question 2. Consider a point A that is moved along theoperation,

1,2,3,4 . Furthermore, for (1)-(3), find the values of the mean and variance.

value of the constant(1),

Find the parameter.

that maximizes the log-likelihood function.

(thought of as a Bernoulli trial). You公開用 P.5

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects③

Data Structure and Algorithms

This question consists of 2 pages. Answer all the questions below.
Question 1.
Figure 1 is pseudocode of an insertion sort that sorts an array A in ascending order. The number of elements in the array A is n,
A[k] represents the kth element of the array A, and the range of index is 1 to n. Answer all the questions below.
(1) Fill up (a) and (b) in the pseudocode shown in Figure 1.
(2) Assume that the contents of the array A are as follows:
48, 73, 36, 5, 22, 17.
At this time, illustrate the process of changing the value of array A when performing InsertionSort(A, 6) of Figure 1.
(3) The time complexity of insertion sort can be evaluated by counting the number of loop iterations. In the insertion sort, thetime complexity changes depending on how the array A (input series) is arranged. Explain what kind of input series makes
the sorting end earliest, and calculate the corresponding time complexity.
(4) Calculate the total number of iterations when the inner “while” loop is repeated (i -1) / 2 times on average during the i-th
iteration in the outer “for” loop. In addition, calculate the average time complexity in that case.

InsertionSort(A, n) {for (i = 2; i <= n; i++) {temp = A[i]j = iwhile (j > 1 && A[j-1] > temp) {(a)
j = j-1}(b)}}
Figure 1 Pseudcode of an insertion sort

公開用 P.6

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
Question 2.
Searching is an operation to find a record with a specific value (key) from a table. When considering a search algorithm, it iscommon to think about the following three operations.
- Insertion: Register a record in the table- Search: Find a record that has a given value as a key.
- Deletion: Delete a record with a given value as a key from the table.
Answer the following questions.
(1) There are algorithms called the linear search (sequential search) and the binary search. When realizing a table using an array,enter the complexity of each operation of these algorithms in the blanks [ (a) ] to [ (f) ] in Table 1 using big O notation, where
the number of data registered in the table is n.
Table 1 The complexity of each operation of linear search and binary searchLinear search

Binary search

The complexity of “Insertion” (one time)[ (a) ]

[ (b) ]

The complexity of “Search” (one time)[ (c) ]

[ (d) ]

The complexity of “Deletion” (one time)[ (e) ]

[ (f) ]

(2) Hashing is a search algorithm that can perform the operations of insertion, search, and deletion on average with thecomputational complexity of O(1). The principle of hashing is to directly associate the key value with the position where thedata is stored (the value of the index of the array is used as a table). An array that stores data is called a hash table, and we
consider a hash function h(x) that maps the key value x to the index of the array. The position to store the data is determinedby the hash value returned by the hash function h(x). However, sometimes the hash function may return the same value fortwo different keys.
① Answer the name of such a situation.
② Suppose that the numerical sequence {an} = {20, 6, 56, 74, 3, 45, 12, 85, 46, 30} is given. Let y be the size of the arrayused as the hash table, and the remainder of dividing an by y (an mod y) is used as the hash function. In addition, thesituation ① will be solved by the chaining (direct chain method).
Write the length of the longest list (chain) if y = 3 is used.
Also, write the minimum y where the length of the longest list is 2 or less.
③ Explain when the complexity of each operation of hashing cannot be regarded as O(1).

公開用 P.7

Specialized Subjects
Computer Science④Computer Architecture⑤Operating System⑥Software Engineering⑦Computer Networks⑧Databases⑨Artificial IntelligenceIn case choosing the Computer Science
section, answer three questions fromquestion ④～⑨

公開用 P.8

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science④

Computer Architecture

Answer all the questions below.
Question.
Answer the following questions about a RISC processor. In the following questions, ISE2022 is a fictitious RISC processor.
ISE2022 has general-purpose registers R1 to R15, and its instruction set is equipped with an Execute addition instruction ADD.
The ADD instruction has three register operands. For example, the assembly notation of the instruction word that stores the
Execute addition result of R1 and R2 in R3 is “ADD R3, R1, R2”. Here we assume that the values have already been written in
R1 to R8 at the start of the execution of the program.
(1) Briefly describe the functionality of the program given by the assembly code of ISE2022

I1:

ADD R9, R1, R2

shown in Fig. 1. Here, the inputs and the output of the program are R1 to R8 and R15,I2:

ADD R10, R3, R4

respectively. Assume that no overflow occurs during the calculation.

I3:

ADD R11, R5, R6

I4:

ADD R12, R7, R8(2) ISE2022 fetches one instruction every clock cycle and performs instruction pipeline

I5:

ADD R13, R9, R10

processing consisting of four stages. In the case of the ADD instruction, the instruction-

I6:

ADD R14, R11, R12

fetch, register-read, Execute addition, and register-write-back are performed in the first,

I7:

ADD R15, R13, R14

second, third, and fourth cycles, respectively. How many clock cycles are required for the

Figure 1

program in Fig. 1 from the start of instruction fetch of instruction I1 to the end of register
write back of instruction I4?
(3) The register file that retains the values of R1 to R15 in ISE2022 can read the values written in the same cycle when writing
and reading the same register occur in the same clock cycle. The ISE2022 is also equipped with a forwarding mechanism
in case data hazards still occur. Answer whether the forwarding mechanism operates if ISE2022 runs the program shown in
Fig. 1.

Also, if the forwarding mechanism operates, answer which register value is forwarded between which instruction

and which instruction.

公開用 P.9

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑤ Operating System
Answer all the questions below.
Question. The table below shows the set of processes for the performance evaluation of CPU scheduling algorithms. There are
four processes, A through D. The table shows each process's arrival time, response start time, and burst time. Draw Gannt charts
illustrating the execution of the processes, and give waiting time, response time, and turnaround time for each process, for thetwo algorithms, FCFS and Round Robin (time slice = 3).

Process

Arrival Time

Response Start

Burst Time

Time
A

0

4

7

B

2

2

4

C

5

1

3

D

8

1

6

公開用 P.10

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑥ Software Engineering
Answer all the questions below.
Question 1.
Explain a benefit of introducing encapsulation in object-oriented modeling.
Question 2.
Describe what the difference is between functional requirements and non-functional requirements.
Question 3.
Describe an example in which trade-offs occur in software architecture design.
Question 4.
There are two types of software reuse: black-box and white-box. Explain pros and cons of them.

公開用 P.11

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑦ Computer Networks
Answer all the questions below.

1
A

Question 1. The figure on the right shows a network. The letter inside the circle denotes a node andDdenotes the distance (or the cost to pass) for the link.

C

2
4

2

its name. The line between two nodes denotes a link between the nodes. The number near the link

4

B

3

1
E

(1) Describe the Dijkstra's algorithm by demonstrating all procedures on the network for determining all the shortest distancesfrom node “A” to other nodes. Skipping any step or omitting the explanation of each step is not allowed.
(2) Show the order of nodes where the shortest distance is determined by the Dijkstra's algorithm in the sub-problem (1). The
order should be denoted as the list of node names separated by comma “,”. For example, if you want to answer that the nodes
A, D, C, and B are the order of shortest distance to be determined, answer that the order of determination is A, D, C, B.
Also show all shortest paths from node “A” to other nodes in this setting. The shortest path should be denoted as the list of node
names separated by dash “-” proceeded by the destination node name and colon “:” followed by colon and its distance. If you
want to answer that the path from node “A” via node G to node E is at a distance of 10, denote it as E:A-G-E:10 for example.
Note that the shortest distance from node “A” to node “A” is determined to be zero at the beginning the steps of the Dijkstra's
algorithm, so A:A-A:0 is self-evident. However, you should also clearly state it in your answer without omission.
Question 2. For the descriptions regarding computer networks from (1) to (8) below, complete each description by selecting acorrect answer from the options inside rectangles if any exists. Or you can answer by writing a suitable keyword or phrase if
you find no suitable options.
(1) The acronyms of the organization that formulates standards for technologies used on the Internet and stores and publishes
technical specifications in a format called RFCs (Request for Comments) is
Q(a) ① ITU ② IETF ③ IEEE ④ IrDA in English.
(2) The maximum throughput of the media access control scheme ALOHA (or Pure ALOHA) is denoted as

Q(b)

using

the natural logarithm of the base (or Napier’s constant) e.
(3) In the OSI Basic Reference Model (or OSI Reference Model), the layer that transfers bits using a transmission medium
such as electrical signals or light is theQ(c)layer. On the other hand,Q(d) ① administrating session check-pointing and recovery ② converting from abstract syntax data to transfer syntax ones ③ definitions of standard specs
for optical fibers ④ routing control(4) In a local area network (LAN),is one of the major functions of the session layer.

Q(e) ① a repeater ② a router ③ a bridge ④ an ONU

is a device that relays

frames in the middle of a transmission path to extend the transmission distance and only transfers at the data link layer.
(5) For an IPv4 (Internet Protocol version 4) address that is denoted as 10.11.23.58 in dotted decimal notation, the addressingof this IP network is a class

Q(f) ① A ② B ③ C ④ D ⑤ E. Assuming a dotted decimal subnet mask of

255.255.255.192, the broadcast address used in this IP network would beQ(g)① 10.255.255.255 ② 10.11.255.255 ③ 10.11.23.63 ④ 10.11.23.255.

(6) The first four bits of the IP header indicate the IP version number. This means that the field is
Q(h) ① 0001 ② 0100 ③ 0110 ④ 1001
(7) Among IP, TCP and UDP in IPv4,

in binary for IPv6 (Internet Protocol version 6) header.

Q(i) ① only TCP has a fixed length header ② only UDP has a fixed length header③ only TCP and UDP have fixed length headers ④ only IP has a fixed length header ⑤ only IP and TCP have fixed
length headers ⑥ only IP and UDP have fixed length headers ⑦ all of them have fixed length headers .
(8)Q(j) ① Return-to-zero ② NRZ(L) ③ Manchester code ④ MLT-3

is a line code in which the encoding of eachdata bit is either low then high, or high then low, for equal time and was adopted for Ethernet standards such as 10BASE-T.

公開用 P.12

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑧ Databases
This question consists of 2 pages. Answer all the questions below.
Question. For the following explanations on Databases from (i) to (iii), choose the most appropriate word or equation for theboxes (1) to (15) from the options and answer with the symbols shown in the alphabets. Note that some unrelated options areincluded, and some of the alphabets are omitted. Assume that the same word is enclosed in the box with the same number.
（i） In relational algebra,(1)

is an operator to combine tuples from two relations that satisfy the combination

condition. The particular type of(1)

whose combination is equality is(2). Moreover, an operator to remove duplicated attributes from the results of(3)

operator is called

(4)

(2)

by

.

（ii） Normal forms in a relational database are a property of relations normalized to prevent inconsistency. The third normal
form is a relation in the second normal form where all attributes except for
the

(5)

(5)

do not have a

(6)

on

. Consider the following relation Order in the second normal form. The underline indicates the primary

key. Customers are assumed to be uniquely specified by the customer number.
Order (order_no, price, customer_no, customer_name, customer_affiliation)
In order to express this relation in the third normal form, it is necessary to split it into the following two relations.
(7)

Order1 (order_no,
Customer(

(8)

)

)

To calculate the total price of orders from customers whose affiliation is a university, the SQL statement is as below.
SELECT(9)

FROM Order1
WHERE customer_no(10)(SELECT customer_no
FROM Customer(11)

WHERE customer_affiliation（iii） There are two operations to restore the database from a system failure:database from the current state to some previous state, and

(13)

(12)

'%University');, an operation that returns the, an operation that returns the database fromthe checkpoint to the state just before the system failure. When the system failure occurs in the following time-lapse,(13)

can restore the transaction

(14)

and

(15)

.

公開用 P.13

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
[Options]arollback

b

RAID

c

equijoindforeign keye

AVG(price)ffull functionalgcandidate keyhroll forward

dependency
jnatural join

k

IN

l

feedbackmselectionn superkeyoSUM(price)

p

LIKE

q

join

r

s

transitive

Cartesian productu

ADD(price)

TOTAL(price)functional t

dependency
v projection

w

=

x

multivalued dependencyy

OUTER JOINz

A

price, customer_nameBprice, customer_no

Dprice, customer_no,

pricecustomer_name
E customer_no,

Gcustomer_namecustomer_name，H

customer_affiliation

customer_no,Jcustomer_affiliation

customer_no,
customer_name,customer_affiliation

L T1

M

T2

Q

T3

R

T4

公開用 P.14

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑨ Artificial IntelligenceThis question consists of 2 pages. Answer all the questions below.
Question. For the following explanations of Artificial Intelligence (AI) from (i) to (v), choose the most suitable word or number
for the boxes (1) to (15) from the options shown below. Note that some unrelated options are included. Assume that the sameword is enclosed in the box with the same number.
(i) In graphFor graph

shown in Fig.1, the numbers along edges are the actual costs and ones in parentheses are the estimated costs.
, the path from node S to G obtained using the Dijkstra algorithm is

to G obtained using the A* algorithm is(2). Also, the A* algorithm(1), and the path from node S(3)that "the optimal path isalways obtained".

Fig.1 Graph(The numbers along edges are the actual costs and ones in parentheses are the estimated costs)【Options for (i)】aguaranteesbdoes not guaranteec

S A C F G

d S A F GeS B D E H Gf

S B D F Gg

S B E H G

h S B E D F G(ii) Fig.2 shows the game tree of a game where two players make decisions in turn, with □ nodes representing the board of thefirst mover and ○ nodes representing the board of the second mover. The alphabet in each node is the name of each board,and the numbers under the leaf nodes denote the evaluation values of the nodes. If the first mover takes the min-max strategy,
the evaluation value of node A is(4)

. When the αβ method is applied to avoid unnecessary search where theboard evaluation proceeds from left to right in the game tree shown in Fig. 2, the set of nodes to be pruned by α-cut is(5), and the set of nodes to be pruned by β-cut is(6)

Fig.2 Game tree.

公開用 P.15

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
【Options for (ii)】
a

3

b

4

c

5

d {K, L}e

{K, L, O}f{L, N, Q}g{G}

h {E, G}(iii) Bayesian filter is a method for estimating self-location based on observed information and previous action history, and it is(7)

assumed to be ain which the observed information

at timedepends only on the location information

at time . However, Bayesian filters must always maintain existence probabilities for all locations. In contrast, the(8)is an approximation method that applies(9)

to the Bayesian filter update formula to obtain theexistence probability of each location from the distribution of a finite number of sample points.
【Options for (iii)】
a

Bayes' theorembPosterior probabilityceLinearityfPartially observable Markov gNormality

d Monte Carlo approximationNaïve Bayes filterh Particle filter

decision process(iv) One of the features of neural networks is that the feature extractor part is optimized, and thus what are called
Neural networks have an input layer,
function is performed in

(11)

(11)

(10)

.

, and an output layer, and nonlinear transformation using an activation. For learning by gradient descent method and error back propagation algorithm, it

is important that the activation function is(12), and sigmoidal functions and ReLU functions are often used as

the functions.
【Options for (iv)】aDifferentiableb

End-to-End learningc

A transformation layerdReinforcement learninge

A convolution layerfLinearg

An intermediate layerh Supervised learning(v) To deal with documents written in natural language by computers, we consider the information representation of words
contained in the documents. An analysis that divides a sentence into the smallest meaningful units and estimates the part ofspeech is called(13). Furthermore, a(14)

is a vector that represents the k-th word with only the k-th

dimension being 1 and the remaining dimensions being 0 when all words in the target document are assigned an index. A(15)

is a representation of a feature of a document by counting the frequency of words contained in the document,

and is used for topic analysis and information recommendation.
【Options for (v)】aBERTb Syntactic analysiscn-gram modeld Distributed representationeOne-hot vectorfgSemantic analysis

h Morphological analysis

Bag-of-Words representation

公開用 P.16

Specialized Subjects
Human Information Science⑩Image Processing⑪Artificial IntelligenceIncasechoosing
the
Human
Information Science section, choose
one question either ⑩ or ⑪

公開用 P.17

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Human Information Science⑩ Image Processing
This question consists of 3 pages. Answer all the questions below.
Question 1. Choose the best answers from the given options (a) to (m).
(1) The Second-Order Derivative methods for Edge Detection(2) Filter used to restore blurred images(3) A geometric transformation that preserves lines and parallelism but not necessarily distances and angles.
(4) Distribution of pixel values(5) Method for corner detection(6) Methods for transformation of data from a high-dimensional space into a low-dimensional space which retain somemeaningful properties of the original data.

(a). Fourier transform (b). Gaussian filter (c). Laplacian filter (d). Wiener filter(e). Hough transform (f). Affine transformation (g). Sobel filter (h). Pseudo color transformation(i). Harris operator (j). Histogram (k). Template matching (l). Homography (m). Principal component analysis

公開用 P.18

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 3 pages.
Question 2. In the image f x, y , the density values at coordinates 1,1 , 1,2 , 2,1 , 2,2 are
2,1

145,

2,2

90 . Calculate the values of

1,1

80,

1,2

160,

1.3, 1.6 using the nearest neighbor and bilinear interpolation

methods.

Question 3．Any coordinates,

can be transformed into,

using the linear transformation. Similarly, an image

can be transformed performing a linear transformation on its all pixel points.
1
When the image is rotated by 30 degrees in the clockwise direction and is moved 15 units to the x direction and -8 units
to the y direction. What are the values of~ .

公開用 P.19

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 3 pages.
Question 4. Choose the best answer for the following two questions, and select the answers from the options.
(1) In the given figures, two normalized histograms
intersection(Figure 1) and(Figure 2) are shown for two images. The similarity

can be calculated using Equation ①.

Select the value offor the similarity intersection.

， ＝

Figure １ Normalized histogram

min

,

①

Figure 2 Normalized histogram【Options】(a) 0.0(b) 0.4(c) 0.5(d) 0.6(e) 0.8(2) Sum of Squared Difference (SSD) can be used for Template matching. Figure 3 represents the target image I(x,y). Template
T(x,y) is shown in Figure 4. SSD can be defined as R(x,y) by Equation ②. This shows the degree of difference between thetemplate and part of the target image (part: area covered by the template). We can assume the size of the template is M x N.
The origin (0,0) is considered at the upper-left corner both in the image and template. On the x-axis, positive values are in theright direction while positive values are downward direction on the y-axis. Figure 5 shows the resulted values of degree ofthe difference for the given target image. Please calculate the value of A.

Figure 3 Target image

Figure 4 Template,,

Figure 5 Degree of difference,②【Options】
(a) 0

(b) 1

(c) 2

(d) 6

(e) 9

公開用 P.20

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Human Information Science⑪ Artificial IntelligenceThis section consists of 2 pages. Answer all the questions below.
Question 1.
Answer the words or phrases suitable for blanks (1) and (2) in the breadth-first search algorithm below.
Line 1 Insert the initial state to the open list and initialize the closed list to empty.
Line 2 while (1)doLine 3

Remove the first element s from the open list. Add s to the closed list.

Line 4

If s is the target state, the search ends because a solution was found.

Line 5

Add all the states that are connected from s but have not been inserted in any lists yet to (2)of the open list.

Line 6 end while

Question 2.
Let B be the event that an undergraduate student in computer science browses the homepage of this graduate school to decide if
they should apply, where the information to be collected related to event A consisting of the following four mutually exclusive
elements is considered.
A1：International efforts
A2：Research ability
A3：Curriculum
A4：Others
Here, let each of the prior probabilities Ai be
P(A1) = 0.25, P(A2) =0.10, P(A3) = 0.45, P(A4) = 0.20
In addition, let each conditional probability of browsing the homepage of this graduate school to collect each element, from theaccess history so far, etc., is as follows:
P(B|A1) = 0.35
P(B|A2) = 0.10
P(B|A3) = 0.10
P(B|A4) = 0.30
(1) Find P(B) using the total probability theorem.
(Choose the most appropriate answer from
①

0.20

②

0.30

③

0.40

④

0.50

to

below.)

公開用 P.21

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This section consists of 2 pages.
(2) Next, find the posterior probability P(A3|B) using Bayes' theorem.
(Choose the most appropriate answer from
①

0.03

②

0.06

③

0.11

④

0.22

to

below.)

Question 3.
Explain the processing flow of one of the typical clustering methods by giving a concrete example.

公開用 P.22

February 2023 Admissions

AY2023 Examination Questions for the Graduate School ofInformation Science and Engineering, Ritsumeikan University(Master’s Program)

Major in Information Science and Engineering
Information Science and Engineering Course【 How to answer questions】
Please follow the instructions below and answer the questions.
Choose two questions from the common subjects and choose either the Computer Science sectionor the Human Information Science section.
In case choosing the Computer Science sectio n, answer three questions from question ④ ~⑨ .
In case choosing the Human Information Science section, choose one question either ⑩ or ⑪ .
There will be two blank answer sheets in case choosing the Human Information Science section.

CommonSubjects① Linear Algebra② Probability and Statistics③ Data Structure and Algorithms④ Computer Architecture⑤ Operating System⑥ Software Engineering
Computer Science

Specialized⑦ Computer Networks⑧ Databases

Subjects⑨ Artificial Intelligence
Human Information Science⑩ Image Processing⑪ Artificial Intelligence【 Examination time】
9:30-11:30 (120minutes)※ Leaving the examination venue is not allowed during the examination time.
※ In case you feel sick or need to go to the bathroom, let examination supervisors know
by raising your hand.

【 Notes】(1) Use one answer sheet for one question.
(2) Fill out your examination number and name for all the answer sheets. Also, make sureto fill out all the other necessary sections such as the questions number column.
(3) Do not remove the staple of your answer sheets.
(4) Answer sheets with no names will be invalid. Do not take the question sheets andanswer sheets with you after the examination.

公開用 P.23

Common Subjects①Linear Algebra②Probability and Statistics③ Data Structure and Algorithms

Choose two questions from the above.

公開用 P.24

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects① Linear Algebra
Answer all the questions below with the derivation process.
Question 1. Given the following matrices

and
1
6
4
2

that satisfies | |, find
0
3
2
1

0
4
2
1

1
4 ,
3
2

3
4
6

| |.

4
2
2
3

3
1
2
2

5
2
3
4

Question 2. Find the orthonormal basis for the following sequence of vectors by Gram–Schmidt orthonormalization.
1
1
2
2 ,
1 ,
2
1
0
1

Question 3. Given the following matrices

and, find

1 1
2 3

.
3

1

,

1
2

1
1

1
1

公開用 P.25

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects②

Probability and Statistics

Answer all of the following questions with all calculation processes and ideas.
,

Question 1. For each of the following simultaneous probability density of the functions
variablesand, determine the values of the positive constants,,

Furthermore, find the peripheral probability density functions
andare independent of each other or not.

(1)

,

(2)

,

(3)

,

,

0 and
0
otherwise0,| | | |of two continuous random

.

of

and

of

, and answer whether

.

.
.

1, 2,

Question 2. Suppose 10 samples, 10 are obtained from a population following a normal distribution

with parameters of mean

(1) Find the log-likelihood function

and precision (inverse of variance),,(3) If the parameter

follows a gamma distribution| ,where Γ

is

| , ,

.
/

| ,

, show that the peripheral distribution

1

of

,

is the gamma function.

(4) Answer which kind of distribution the peripheral distribution(3), approaches, as,that maximizes the log-likelihood function

| ,

.

.

(2) Find the parameter

| , ,

| ,

.

| , ,

1

, derived in公開用 P.26

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Common Subjects③ Data Structure and Algorithms
This question consists of 2 pages. Answer all the questions below.
Question 1.
The quicksort procedure for an array, whose length is n, is as follows.
1. Pick a reference value p, called a pivot, within the specified range.
2. Partition the range. Reorder its elements, while determining a point of division, so that all elements with values less than thepivot p come before the point of division, while all elements with their values greater than or equal to the pivot p come after
the division.
3. Recursively apply the quicksort to both the subrange up to the point of division and to the subrange after it, until there is only
one element in the division.
Please answer the following questions.
(1) Answer the name of a sorting algorithm that uses recursion as same as quicksort.
(2) Write appropriate words or formulas in the blanks [ (a) ] to [ (d) ] in the following text regarding the maximum timecomplexity of quicksort.
The worst case for quicksort is when the [ (a) ] results in n-1 elements remaining in one set and an empty set in the other.
This happens when the [ (b) ] or [ (c) ] element is chosen as the pivot p.
Assume that such a situation occurs every [ (a) ],Qn = [ (d) ],where Qn is the number of comparisons to sort the entire array whose length is n.
(3) For the range specified by left and right of the array x to be sorted{ x[left], x[left +1], …, x[right - 1], x[right] },the function that performs quicksort is defined as follows:
quicksort (x, left, right).

quicksort (x, left, right) {if (left < right) {pivot and returns the position where the pivot falls is defined asp ← partition (x, left, right) ;quicksort (x, left, p - 1) ;follows:

quicksort (x, p + 1, right) ;The function that partitions the range of the array into two parts by}partition (x, left, right).
The quicksort algorithm can be written using these functions as}shown in Figure 1.
Using this as a reference, write the following function that

Figure 1 The pseudocode of quicksort

recursively finds the K-th smallest value in an array with lesscomputation than quicksort.
selectKth (x, left, right, K),
where x is an array with n elements. K must be a value within the range of the subscripts of the array x, and the array subscripts
start from 1. Also, the order of the array elements may be changed, and this function should be called as follows:
selectKth (x, 1, n, K).
Note that this function returns a value using the return statement.

公開用 P.27

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
Question 2.
Suppose that a singly-linked list which stores integers as data is represented as Figure 2. Answer the following questions about
this list.

Figure 2 A diagram of a singly-linked list

(1) Table 1 below shows the list in Figure 2 in tabular form. When the value of top, which indicates the address of the top elementof the list, is 1008, write the appropriate numbers in blanks [ (a) ] to [ (f) ] of table 1.
Table 1 The list in Figure 2 in tabular format
address

data

next

[

10

1032

(a) ]

1008

[

[

16

[

(d) ]

1024

78

[

(e) ]

1032

[

1040

22

(c) ]

(b) ]

1000

(f) ]

1016
null

(2) Figure 3 is the pseudocode of the function searchMax() which returns the position where the maximum value is stored in thegiven list. The position where the maximum value is stored is to be stored in variable m. The data can be referenced byadding .data to the element it points to, like top.data, and the next element can be referenced by adding .next to the element
it points to, like top.next.
Write pseudocode that applies to (g) and (h) in the pseudocode shown in Figure 3.

searchMax (top) {x ← top ;m ← top ;while ( x != null ) {if ((g)
m ← x;}> x.data ) {(h)}return (m) ;}Figure 3 The pseudocode for searching for the maximum value

公開用 P.28

Specialized Subjects
Computer Science④Computer Architecture⑤Operating System⑥Software Engineering⑦Computer Networks⑧Databases⑨Artificial IntelligenceIn case choosing the Computer Science
section, answer three questions fromquestion ④～⑨

公開用 P.29

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science④ Computer Architecture
Answer all the questions below.
Question 1.
Explain the differences between a direct-mapped cache, a fully associative cache, and a set associative cache.
Question 2.
Answer the number of tag, index, and offset bits of the following three caches when the size of the address space is 232 bytes, thecash memory size is 32K bytes, and the cache block size is 32 bytes. Also, show the calculation process.
A) A direct-mapped cacheB) A fully associative cacheC) A 2-way set associative cache公開用 P.30

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑤ Operating System
Answer all the questions below.
Question 1. Explain the words "process" and "thread" of the process-thread model.
Question 2. Most memory management techniques are based on the concept of locality of reference. It can be classified into
temporal locality and spatial locality. Explain their characteristics.
Question 3. Thrashing may occur on operating systems adopting virtual memory. Explain this phenomenon and the circumstancesin which it occurs.

公開用 P.31

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑥ Software Engineering
Answer all the questions below.
Question 1.
What do the following technical terms mean in software testing?
(1) Unit testing(2) Integration testing(3) Acceptance testing
Question 2.
What are relationships between a class and its instance in object-oriented programming?
Question 3.
What is the purpose of adaptive maintenance for software systems?
Question 4.
Consider a decision table derived from the Cause-Effect graph as shown below. Answer the following questions:(1) What is the minimum number of test cases generated by a column of the decision table?
(2) How many test cases of the generated ones should be executed when checking if effect E1 can be true in the decision table?
(3) How many test cases of the generated ones should be executed when checking if effect E2 can be true in the decision table?
Note that “E” connected by dotted lines means the exclusive constraint in the Cause-Effect graph.

C1

E

E1

C2
M
C3

N

Cause‐Effect graph

E2

公開用 P.32

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑦ Computer Networks
This question consists of 2 pages. Answer all the questions below.
Question 1. For the descriptions regarding computer networks from (1) to (6) below, complete each description by selecting
correct answers from options inside rectangles if one exists. Or if you find no suitable options, you may answer by writing
suitable keywords or phrases. Assume that the same term will be placed in all enclosures with the same problem symbol.
(1)

Q(a) ① ITU ② IETF ③ IEEE ④ IrDA is the abbreviation for the organization, headquartered in the United Statesof America, which is a society for electrical and electronic engineering and is engaged in standardization activities related
to communications, electronics, and information engineering and related fields in English.

(2) SlottedQ(b) ① CDMA ② CSMA/CA ③ CSMA/CD ④ ALOHA , a media control method, improves throughput

by introducing discrete time slots to Pure

Q(b). The theoretical maximum throughput of Slottedwith three digits of precision, is about 36.8%, while that of Pure
Q(c) ① 7.90 ② 12.2 ③ 16.3 ④ 18.4

Q(b)

Q(b)

, expressed, expressed with the same precision, is about%.

(3) In the OSI Basic Reference Model (or the OSI Reference Model), the top layer provided by an intermediate open system(or an intermediate system) is theQ(d) ① physical ② data link ③ network ④ transportlayer. In an IP (Internet

Protocol) network, the device corresponding to an intermediate open system is called an IP
Q(e) ① switching hub ② router ③ bridge ④ repeater.

(4) For an IPv4 (Internet Protocol version 4) address that is denoted as 10.162.42.254 in dotted decimal notation, theaddressing of this IP network is a class

Q(f) ① A ② B ③ C ④ D ⑤ E. Assuming a dotted decimal subnet maskof 255.255.252.0, the maximum number of unique IP addresses for unicast communication in this network would be
Q(g) ① 162 ② 1022 ③ 1624 ④ 2254.

(5) The first four bits of the IP header indicate the IP version number. This means that the field is
Q(h) ① 0001 ② 0100 ③ 0110 ④ 1001

in binary for IPv4 header. Of the respective IP headers, an IPv4 header

and an IPv6 (Internet Protocol version 6) fixed header, the checksum field is present
Q(i) ① in IPv4 one only ② in IPv6 one only ③ both in IPv4 one and in IPv6 one(6) The communication protocol

Q(j) ① RSVP ② RTP ③ RTSP ④ RTCP.

is used to guarantee the quality ofcommunication paths on IP networks by reserving bandwidth from the source to the destination in advance.

公開用 P.33

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
Question 2. The figure in the right side shows a network named “N.”I
B

The letter inside the circle denotes a node and its name. The line between
two nodes denotes a link between the nodes. The specifications of eachlink are denoted in the figure legend. You can suppose that the delay
time for interlink transfer at a node may be ignored in this question Q2.

A

C

H

E
F

Legend: bps: Bit per Second, ms: milli second
D

G

Bandwidth: 1G[bps], Delay: 100 [ms]Bandwidth : 1G[bps], Delay : 10[ms]Bandwidth : 100M[bps], Delay : 100[ms]Bandwidth : 100M[bps], Delay : 10[ms](1) Define the reasonable inter-node link cost as positive distance metric to minimize the delay time and show the value of thecosts for the network “N.”(2) - Describe the Dijkstra's algorithm by demonstrating all procedures on the network “N” with the link costs calculated in theprevious problem (1) for determining all shortest path from node “A” to other nodes. Skipping any step or omitting the
explanation of each step is not allowed. The shortest paths of multiple nodes that have the same cost from node “A” may beobtained in a single step (this means that, as long as you do not violate the algorithm, you do not have to restrict the shortest
path to be obtained in a single step to a single node).
- Also, answer which node(s) have the maximum delay in these settings and indicate their delays.
(3) Using the same procedures from (1) through (2),- find a single path to each node from node “A” on the network “N” that maximizes the communication bandwidth of thatpath and also find the delay time and the communication bandwidth for each path. If there are multiple links with the same
bandwidth, choose the link with the lowest delay.
- Also, find all path(s) that have the maximum delay in these settings and indicate their delays.

公開用 P.34

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑧ Databases
This question consists of 2 pages. Answer all the questions below.
Question .
For the following explanations on Databases from (i) to (iii), choose the most appropriate word for the boxes
(13)
for

(1)

to

from the options and answer with the symbols shown in alphabetic letters. Moreover, answer with numerical values
(14)

and

(15)

. Note that some unrelated options are included, and some of the letters are omitted. Assume thatthe same word is enclosed in the box with the same number.
（i） In designing a database for express bus schedule management, the following diagram created fromuser requirements as a conceptual schema is called

(1)
(3)

. The (1) consists of rectangles

representing(2)and diamonds representing. Also, the diagram includes

ellipses named(4)

to describe the properties of (1) and (2).

公開用 P.35

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
(5)（ii） The above diagram creates relation ① andof the following items. Note that departureand arrival time may vary according to service dates even on the same route.
① Bus_Stop (Stop_ID, Stop_Name)② Express_Bus (Route_ID, Service_Date)③ Express_Bus (Route_ID, Service_Date, Departure_Stop_ID, Arrival_Stop_ID)④ Express_Bus (Route_ID, Service_Date, Departure_Stop_Name, Arrival_Stop_Name)⑤ Express_Bus (Route_ID, Service_Date, Departure_Stop_ID, Departure_Time, Arrival_Stop_ID,
Arrival_Time)⑥ Schedule (Departure_Time, Arrival_Time)⑦ Schedule (Service_Date, Departure_Time, Arrival_Time)⑧ Schedule (Route_ID, Departure_Time, Arrival_Time)⑨ Schedule (Departure_Stop_ID, Arrival_Stop_ID, Departure_Time, Arrival_Time)
The created relations are not second-normal forms because there are attributes that are not(6)functional dependent on the(7). To satisfy the second-normal form, therelations are transformed as follows.
Bus_Stop (Stop_ID, Stop_Name)
Express_Bus1 (Route_ID,
Schedule1(

(9)

(8)

)

, Departure_Time, Arrival_Time)To calculate the total number of express buses that depart on the morning of April 1st in 2023,
the SQL statement is as follows.
SELECT(10)

FROM Schedule1
WHERE Departure_Time(11)'2023-04-01 00:00:00' AND '2023-04-01 12:00:00');（iii） There are two evaluation criteria for information retrieval:
documents among retrieval results, and

(13)

(12)

, a fraction of correct, a fraction of retrieved results among all

the correct documents. For example, in retrieving a product at the online shop storing 100 products,
it returns 30 products, 15 of which match the query, and stores 10 correct products other than
the retrieval results. In this case, (12) is(14), and (13) is

(15)

.

[Options]a entity typesb

precisionc

CODASYL modeldforeign key

e LIKE

f

fully

g

candidate keyhaccuracy

j partiallykrecalll

set typesmattributesn super keyobachman diagramp

BETWEENq

weak entity types

r TOTAL(*)

stransitivelytrecord typesusensitivity

v relationshipw

COUNT(*)

x

ER diagramyRoute_IDA

Route_ID,

B

Departure_Stop_Name,D

Departure_Stop_ID,

types
z Service_Date

Service_Date

Arrival_Stop_Name

Arrival_Stop_ID

E ② and ⑨G③ and ⑨H

③ and ⑧J

③ and ⑦

L ③ and ⑥M④ and ⑦Q

④ and ⑧R⑤

公開用 P.36

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Computer Science⑨ Artificial IntelligenceThis question consists of 2 pages. Answer all the questions below.
Question. For the following explanations of Artificial Intelligence (AI) from (i) to (v), choose the most suitable word or number
for the boxes (1) to (15) from the options shown below each explanation and answer with the symbols shown in alphabetic letters.
Note that some unrelated options are included. Assume that the same word is enclosed in boxes with the same number.
(i) The method of decomposing the entire given problem into multiple subproblems and finding a solution to the entire problem(1)

while memorizing the solution to each subproblem is called、. In graphin Fig.1, the nodes are states、

at time , and the numbers along edges are the evaluation values (gain) obtained when performing that statetransition. In this graphedges is found by, the path from node

(1)

to

that maximizes the sum of the evaluation values of the traversed. Then, the evaluation value to be memoized to node

the evaluation values of the edges in the obtained path is

(3)

is

(2)

, and the sum of.

Fig.1 Graph【Options for (i)】
a

3

b

4

c

8

d 10

e

11

f

A* AlgorithmgDynamic Programing

h mini-max method(ii) A certain product X is produced in two factories, and 80% of its total output is produced in factory A and 20% in factory B.
However, 2% of the products from Factory A are defective and 3% of the products from Factory B are defective. Note that
products that are not defective must be considered good products. Then, answer the following questions. Notice that theoptions are shown as values to three decimal places.
1.

The probability that a product X is good and produced at factory B is

2.

The probability that a product X is defective is3.

Given that a product X is defective, the probability that it is produced in factory A is

(5)

(4)

.

.
(6)

【Options for (ii)】
a

0.006

b

0.016

c

0.022

d 0.050

e

0.194

f

0.273

g

0.727

h 0.970.

公開用 P.37

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
(iii) Consider a normal form game represented by the payoff matrix in Table 1. In the payoff matrix, the left value of each cell is
the payoff of Player A, and the right one is the payoff of Player B. Assume that each player acts rationally. When a pair of(7)

Players' actions are optimal responses to each other's actions, the pair is called(7)

is when the actions of Player A and Player B are(8). In the game in Table 1,, respectively. Also, when each Player takes theaction with the highest payoff regardless of the other' s action, the pair of the actions is called(9).

Table 1 Payoff matrix【Options for (iii)】adominant strategy equilibriumbnational equilibriumcmini-max equilibriume

a1, b1f

a1, b2

g a2, b1

d Nash equilibrium
h a2, b2(iv) Machine learning methods in which the relationship between inputs and outputs is learned from training data given a teacher(10)signal, which is the correct output, are called. Among the problems handled by

(10)

, the

problem of learning a continuous functional relationship that returns a real value for a vector representing the input data is(11)called. Also,(12)

is the method used to evaluate the generalization performance of the learner.

For example, there is a method in which the data set is divided into K pieces, K-1 of which are training data and the remaining
one set is test data, and the evaluation is repeated K times so that all K pieces become test data one by one, and the overall
evaluation value is obtained by averaging the obtained K evaluation values.
【Options for (iv)】aclassification problembregression problemcclusteringdetransfer learningfcross-validationg

one-hot vector

h supervised learning(v) Consider converting a logical formula to clause form. When removing the implication sign,(13). Also, applying de Morgan's law to

P

gives

(15)

gives

(14)

reinforcement learning

is replaced by, and applying the distributive law to.

【Options for (v)】
a

P

Q

b

e

P

Q

f

P
P

Q

Q

c

P

g

P

P

Q

d

Q

P

h

P
P

Q
Q

公開用 P.38

Specialized Subjects
Human Information Science⑩Image Processing⑪Artificial IntelligenceIncasechoosing
the
Human
Information Science section, choose
one question either ⑩ or ⑪

公開用 P.39

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Human Information Science⑩ Image Processing
This question consists of 2 pages. Answer all the questions below.
Question 1.

100

105

100

95

75

50

45

50

55

is a 3 by 3 image. The horizontal direction points to the right and the vertical direction points downward. For the center pixel,(1) Compute the horizontal derivative and the vertical derivative, where Ix(0,0)=(I(1,0)-I(-1,0))/2 and Iy(0,0)=(I(0,1)-I(0,-1))/2.
(2) Compute the second derivative for the horizontal direction, where Ixx(0,0)= I(1,0)-2I(0,0)+I(-1,0)(3) compute the second derivative for the vertical direction, which is defined in the same manner as the horizontal direction.
(4) compute the second derivative for both the horizontal and vertical directions,which is defined as Ixy(0,0)=(Ix(0,1)-Ix(0,-1))/2= (I(1,1)-I(-1,1)-I(1,-1)+I(-1,-1))/4

Question 2.
Suppose we create a 2D Gaussian filter from the 2D Gaussian function G(x,y)=A*exp(-(x*x+y*y)/2) using only 8 bits for each value
in the filter. Determine A first. Suppose that the filter is B×B pixels. Determine B. For your convenience, exp(-1/2)≒0.6, exp(-2)≒
0.135 , exp(-4.5)≒0.0111, exp(-8)≒0.0003.

Question 3.
The figure shows a parallel stereo, where the distance between the two cameras is b, and the point on the left image (u,v) corresponds
to the point on the right image (u’,v). Determine X, Y and Z. It is known that in parallel stereo, axis u and axis u’ are collinear andparallel to axis X, and axis v and axis v’ are parallel to axis Y. The origin of (u,v) coordinates is on the Z axis, and two cameras haveexactly the same intrinsic parameters. We also assume that f is known and given in pixels.

公開用 P.40

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University* This question consists of 2 pages.
Question 4.
As shown in the figure, after rotating the image clockwise by 30 degrees, it is further translated by 10 in horizontal direction and 20
in the vertical direction. The new coordinates can be expressed by

Determine a, b, c, d, e and f.

公開用 P.41

Master’s Program, Information Science and Engineering Course,
Graduate School of Information Science and Engineering,
Ritsumeikan University

Human Information Science⑪ Artificial Intelligence
Answer all the questions below.
Question .
(1) Consider two strings, “xyzxyz” and “xyxzyz”. Calculate the edit distance between these two strings using dynamic
programming. The values determined in memoization to perform dynamic programming (i.e., edit distances between substrings)
should all be shown in a matrix form.

(2) Consider a symbolic artificial intelligence (AI) system that proves a logical inference problem in propositional logic. Show
that the conclusion R∨S is obtained when the AI system has knowledge that P ∧ Q, P →R, and Q →S using a resolution

refutation proof, i.e., a proof by contradiction using resolution. In addition, please show a proof tree.

(3) Answer the following questions.
(3-1) Probability theory is important in machine learning. Please explain "marginalization" and the "multiplication theorem" inprobability theory with equations and text descriptions.
(3-2) What is context analysis in natural language processing? Please explain it with example sentences.
(3-3) What is an activation function in neural networks? Please explain it with equations and text descriptions.
(3-4) Most reinforcement learning methods are developed based on the assumption of a Markov decision process (MDP). Whatis a MDP? Please explain it with a probabilistic graphical model, equations, and text descriptions.