Specialized Subjects
10:00-12:00, Monday, August 17, 2020
Instructions
1. This booklet contains five problems. The number of pages is six excluding this cover sheet.
2. Answer three problems. You can select any three out of the five. Your answer to each problem
should be written on a separate sheet. Answers to a single problem may be spread over several
answer sheets. However, answers to multiple problems must not be written on one answer sheet.
3. Write the problem number that you have chosen and your examinee number on top of eachanswer sheet.
4. Submit the answer sheets for three problems. Even if you have solved only one or two problems,
you must submit answer sheets with the examinee number and the problem number.
5. Answer either in Japanese or in English.
6. This booklet cannot be downloaded nor saved to your local computers.
7. This English translation is supplemental and provided for convenience of applicants. TheJapanese version is the formal one.

Problem 2
Suppose a data sequence (X0 X1 X2 X3 · · ·) where each binary digit Xk is synchronously input
with a clock. Let us design a binary digital synchronous sequential circuit whose output Z is
1 if and only if the number X(i) deﬁned by the following equation gets the remainder 3 when
X(i) is divided by 6; otherwise Z is 0. Answer the following questions.
X(i) =i∑(Xk × 2i−k )(X0 X1 X2 · · · Xi is regarded as a binary number.)

k=0(1) Describe what a sequential circuit is within 25 words.
(2) Design a state transition diagram in the form of a Mealy graph.
(3) Make the state transition diagram as simple as possible. If the diagram cannot be theoretically simpliﬁed from (2), this question does not require an answer.
(4) Make the state transition table.
(5) Draw Karnaugh maps from (4).
(6) Design the sequential circuit and draw it using MIL symbols (see the Figure). Simplify
the circuits as far as possible, using the Karnaugh maps in (5).

Problem 3
There are N objects moving on a ﬁeld. When two objects a and b come into contact witheach other at a time t, a triplet (t, a, b) is recorded. Once two objects have been in contact
they participate in an equivalence relation and belong to the same equivalence class. At thebeginning each equivalence class includes a single object. When its object is in contact with anobject in another class, these classes merge into one equivalence class.
Answer the following questions.
(1) The pseudo code in the next page shows an union-ﬁnd algorithm that keeps track of theequivalent class of each object. The function init initializes the array parant that records
the equivalence classes (ignore the array sizes in this question). Every time the above
mentioned triplet is recorded, the function union is executed and it updates the arrayparent. When N equals 6, show the content of the array parent after the following
triplets have been recorded.
(1, 0, 3), (2, 4, 2), (3, 1, 5), (4, 0, 1)(2) Describe the order of the worst-case time complexity of the function find and union withreasons.
(3) Consider recording the number of objects in each equivalence class using the array sizes.
Fill in (X) and (Y) in the pseudo code so that the function size returns the number ofobjects in the equivalence class including the designated object a. You can write multiplelines in (X) and (Y).
(4) The time complexity of the function find and union can be improved by modifying thefunction union using the array sizes. Modify and show the code (X) in the pseudo code.
Describe the order of the worst-case time complexity of the improved union function withreasons.
(5) Consider ﬁnding the time when the designated objects a and b became equivalent. Describe
how to modify the algorithm and explain the procedure of the function that ﬁnds the time.
Describe the order of the worst-case time complexity of the function with reasons.

Union-find algorithm:
int parent[N];int sizes[N];void init() {for (int i = 0; i < N; ++i) {parent[i] = i;sizes[i] = 1;}}
int find(int i) {while (parent[i] != i) {i = parent[i];}return i;}void union(int a, int b) {int i = find(a);int j = find(b);parent[i] = j;(X)}
int size(int a) {(Y)}Problem 4
Regarding the TCP/IP, answer the following questions.
(1) Describe an example which a bridge can do but a repeater cannot do at the data link layer.
(2) Describe the name of the protocol for retrieving the MAC address of the target host fromits IP address in a network segment.
(3) Find the number of IP addresses allowed for allocation in the network segment 192.168.10.16/28.
(4) Describe three kinds of information that DHCP may distribute along with the IP address
allocated for a host.
(5) Describe the role of the TTL ﬁeld contained in IP packet headers.
(6) Describe three typical functions that ICMP provides.
(7) Packet A (destination: 192.168.10.5) and packet B (destination: 192.168.10.12) will betransferred by a router based on the routing table shown below. Find the IP addresses
respectively that packet A and packet B will be transferred to.
Destination
192.168.10.8/29
192.168.10.0/26
192.168.10.0/24
0.0.0.0/0

Gateway
192.168.11.249
192.168.11.246
192.168.11.244
192.168.11.1(8) Describe the process when the size of a transferring IPv4 packet exceeds the maximum
transmission unit (MTU) at the data link layer.
(9) In the case of TCP, ﬁnd the best maximum segment size (MSS) of Source if the MTUs on
Source-to-Destination path are given below. MSS is the maximum payload length of TCP
segments. The IP header length is 20 octets and the TCP header length is 20 octets.

(10) Describe how the traceroute searches for a route.
(11) It is said that TCP provides reliable data delivery service. However, the use of TCP does
not always enable the communication with remote hosts. The data can be tampered withduring the delivery, too. Describe the reliability of TCP in this context.
(12) Describe the length of IPv6 addresses.
(13) Show an example of IPv6 addresses.
(14) Describe how the DNS resolves a name.

Problem 5Answer the following questions about the Fourier transform. Let

1 (−1 ≤ t < 0)x(t) =−2 (0 ≤ t < 2)
0 (otherwise){and f (t) =E (|t| ≤ τ /2)
0 (|t| > τ /2).

Here, τ > 0 and E > 0. Note that a(t) ∗ b(t) denotes the convolution of two signals a(t) andb(t).
(1) Sketch the graphs of xo (t) and xe (t) that satisfy x(t) = xo (t)+xe (t), where xo (−t) = −xo (t)and xe (−t) = xe (t).
(2) Let Xo (ω) be the Fourier transform of xo (t). Find Re(Xo (ω)) that is the real part ofXo (ω).
(3) Derive F (ω) that is the Fourier transform of f (t). And, ﬁnd all ω’s that satisfy F (ω) = 0.
(4) Let f2 (t) = f (t) ∗ f (t). Sketch the graph of f2 (t).
(5) Let f3 (t) = f2 (t) ∗ f (t). Using F (ω) of (3), ﬁnd F2 (ω) and F3 (ω) that are the Fouriertransforms of f2 (t) and f3 (t), respectively.
df2 (t). Sketch the graph of g(t), and express g(t) as a formula using f (t).
(6) Let g(t) = dt

(7) Derive G(ω) that is the Fourier transform of g(t).