1. (15 pts) Bellatrix Lestrange is writing a secret message to Voldemort and wants to prevent it from being understood by meddlesome young wizards and Muggles. She decides to use Huffman encoding to encode the message. Magically, the symbol frequencies of the message are given by the Pell numbers, a famous sequence of integers known since antiquity and related to the Fibonacci numbers. The nth Pell number is defined as Pn = 2Pn−1 + Pn−2 for n 1 with base cases P0 = 0 and P1 = 1. (a) For an alphabet of Σ = {a,b,c,d,e,f,g,h} with frequencies given by the first |Σ| non-zero Pell numbers, give an optimal Huffman code and the corresponding encoding tree for Bellatrix to use. (b) Generalize your answer to (1a) and give the structure of an optimal code when the frequencies are the first n non-zero Pell numbers. 2. (30 pts) A good hash function h(x) behaves in practice very close to the uniform hashing assumption analyzed in class, but is a deterministic function. That is, h(x) = k each time x is used as an argument to h(). Designing good hash functions is hard, and a bad hash function can cause a hash table to quickly exit the sparse loading regime by overloading some buckets and under loading others. Good hash functions often rely on beautiful and complicated insights from number theory, and have deep connections to pseudorandom number generators and cryptographic functions. In practice, most hash functions are moderate to poor approximations of uniform hashing. Consider the following hash function. Let U be the universe of strings composed of the characters from the alphabet Σ = [A,…,Z], and let the function f(xi) return the index of a letter xi ∈ Σ, e.g., f(A) = 1 and f(Z) = 26. Finally, for an m-character string x ∈ Σm, define h(x) = ([Pm i=1 f(xi)] mod `), where ` is the number of buckets in the hash table. That is, our hash function sums up the index values of the characters of a string x and maps that value onto one of the ` buckets. (a) The following list contains US Census derived last names: https://www2.census.gov/topics/genealogy/1990surnames/dist.all.last Using these names as input strings, first choose a uniformly random 50% of these name strings and then hash them using h(x). Produce a histogram showing the corresponding distribution of hash locations when ` = 200. Label the axes of your figure. Briefly describe what the figure shows about h(x), and justify your results in terms of the behavior of h(x). Do not forget to append your code. Hint: the raw file includes information other than name strings, which will need to be removed; and, think about how you can count hash locations without building or using a real hash table. 1 CSCI 3104 Problem Set 5 (b) Enumerate at least 4 reasons why h(x) is a bad hash function relative to the ideal behavior of uniform hashing. (c) Produce a plot showing (i) the length of the longest chain (were we to use chaining for resolving collisions under h(x)) as a function of the number n of these strings that we hash into a table with ` = 200 buckets, (ii) the exact upper bound on the depth of a red-black tree with n items stored, and (iii) the length of the longest chain were we to use a uniform hash instead of h(x). Include a guide of cn Then, comment (i) on how much shorter the longest chain would be under a uniform hash than under h(x), and (ii) on the value of n at which the red-black tree becomes a more efficient data structure than h(x) and separately a uniform hash. 3. (15 pts) Draco Malfoy is struggling with the problem of making change for n cents using the smallest number of coins. Malfoy has coin values of v1 < v2 < ··· < vr for r coins types, where each coin’s value vi is a positive integer. His goal is to obtain a set of counts{di}, one for each coin type, such thatPr i=1 di = k and where k is minimized. (a) A greedy algorithm for making change is the cashier’s algorithm, which all young wizards learn. Malfoy writes the following pseudocode on the whiteboard to illustrate it, where n is the amount of money to make change for and v is a vector of the coin denominations: wizardChange(n,v,r) : d[1 .. r] = 0 // initial histogram of coin types in solution while n 0 { k = 1 while ( k < r and v[k] n ) { k++ } if k==r { return ’no solution’ } else { n = n – v[k] } } return d Hermione snorts and says Malfoy’s code has bugs. Identify the bugs and explain why each would cause the algorithm to fail. (b) Sometimes the goblins at Gringotts Wizarding Bank run out of coins,1 and make change using whatever is left on hand. Identify a set of U.S. coin denominations for which the greedy algorithm does not yield an optimal solution. Justify your 1It’s a little known secret, but goblins like to eat the coins. It isn’t pretty for the coins, in the end. 2 CSCI 3104 Problem Set 5 answer in terms of optimal substructure and the greedy-choice property. (The set should include a penny so that there is a solution for every value of n.) (c) (8 pts extra credit) On the advice of computer scientists, Gringotts has announced that they will be changing all wizard coin denominations into a new set of coins denominated in powers of c, i.e., denominations of c0,c1,…,c` for some integers c 1 and ` ≥ 1. (This will be done by a spell that will magically transmute old coins into new coins, before your very eyes.) Prove that the cashier’s algorithm will always yield an optimal solution in this case. Hint: first consider the special case of c = 2.
1. (20 pts total) Solve the following recurrence relations using any of the following methods: unrolling, tail recursion, recurrence tree (include tree diagram), or expansion. Each each case, show your work. (a) T(n) = T(n−2) + C n if n 1, and T(n) = C otherwise (b) T(n) = 3T(n−1) + 1 if n 1, and T(1) = 3 (c) T(n) = T(n−1) + 3n if n 1, and T(1) = 3 (d) T(n) = T(n1/4) + 1 if n 2 , and T(n) = 0 otherwise 2. (10 pts) Consider the following function: def foo(n) { if (n 1) { print( ’’hello’’ ) foo(n/3) foo(n/3) }} In terms of the input n, determine how many times is “hello” printed. Write down a recurrence and solve using the Master method. 3. (30 pts) Professor McGonagall asks you to help her with some arrays that are raludominular. A raludominular array has the property that the subarray A[1..i] has the property that A[j] A[j + 1] for 1 ≤ j < i, and the subarray A[i..n] has the property that A[j] < A[j + 1] for i ≤ j < n. Using her wand, McGonagall writes the following raludominular array on the board A = [7,6,4,−1,−2,−9,−5,−3,10,13], as an example. (a) Write a recursive algorithm that takes asymptotically sub-linear time to find the minimum element of A. 1 (b) Prove that your algorithm is correct. (Hint: prove that your algorithm’s correctness follows from the correctness of another correct algorithm we already know.) (c) Now consider the multi-raludominular generalization, in which the array contains k local minima, i.e., it contains k subarrays, each of which is itself a raludominular array. Let k = 2 and prove that your algorithm can fail on such an input. (d) Suppose that k = 2 and we can guarantee that neither local minimum is closer than n/3 positions to the middle of the array, and that the “joining point” of the two singly-raludominular subarrays lays in the middle third of the array. Now write an algorithm that returns the minimum element of A in sublinear time. Prove that your algorithm is correct, give a recurrence relation for its running time, and solve for its asymptotic behavior. 4. (15 pts extra credit) Asymptotic relations like O, Ω, and Θ represent relationships between functions, and these relationships are transitive. That is, if some f(n) = Ω(g(n)), and g(n) = Ω(h(n)), then it is also true that f(n) = Ω(h(n)). This means that we can sort functions by their asymptotic growth.1 Sort the following functions by order of asymptotic growth such that the final arrangement of functions g1,g2,…,g12 satisfies the ordering constraint g1 = Ω(g2), g2 = Ω(g3), …, g11 = Ω(g12). n n1.5 8lgn 4lg∗ n n! (lgn)! 5 4n n1/lgn nlgn lg(n!) en 42 Give the final sorted list and identify which pair(s) functions f(n),g(n), if any, are in the same equivalence class, i.e., f(n) = Θ(g(n)). 1The notion of sorting is entirely general: so long as you can define a pairwise comparison operator for a set of objects S that is transitive, then you can sort the things in S. For instance, for strings, we use a comparison based on lexical ordering to sort them. Furthermore, we can use any sorting algorithm to sort S, by simply changing the comparison operators ,
1. (10 pts total) For each of the following claims, determine whether they are true or false. Justify your determination (show your work). If the claim is false, state the correct asymptotic relationship as O, Θ, or Ω. (a) n + 1 = O(n4) (b) 22n = O(2n) (c) 2n = Θ(2n+7) (d) 1 = O(1/n) (e) ln2 n = Θ(lg2 n) (f) n2 + 2n−4 = Ω(n2) (g) 33n = Θ(9n) (h) 2n+1 = Θ(2nlgn) (i) √n = O(lgn) (j) 10100 = Θ(1) 2. (15 pts) Professor Dumbledore needs your help optimizing the Hogwarts budget. You’ll be given an array A of exchange rates for muggle money and wizard coins, expressed at integers. Your task is help Dumbledore maximize the payoff by buying at some time i and selling at a future time j i, such that both A[j] A[i] and the corresponding difference of A[j]−A[i] is as large as possible. For example, let A = [8,9,3,4,14,12,15,19,7,8,12,11]. If we buy stock at time i = 2 with A[i] = 3 and sell at time j = 7 with A[j] = 19, Hogwarts gets in income of 19−3 = 16 coins. (a) Consider the pseudocode below that takes as input an array A of size n: makeWizardMoney(A) : maxCoinsSoFar = 0 for i = 0 to length(A)-1 { for j = i+1 to length(A) { 1 CSCI 3104, Algorithms Problem Set 1 coins = A[j] – A[i] if (coins maxCoinsSoFar) { maxCoinsSoFar = coins } }} return maxCoinsSoFar What is the running time complexity of the procedure above? Write your answer as a Θ bound in terms of n. (b) Explain (1–2 sentences) under what conditions on the contents of A the makeWizardMoney algorithm will return 0 coins. (c) Dumbledore knows you know that makeWizardMoney is wildly inefficient. With a wink, he suggests writing a function to make a new array M of size n such that M[i] = min 0≤j≤i A[j] . That is, M[i] gives the minimum value in the subarray of A[0..i]. What is the running time complexity of the pseudocode to create the array M? Write your answer as a Θ bound in terms of n. (d) Use the array M computed from (2c) to compute the maximum coin return in time Θ(n). (e) Give Dumbledore what he wants: rewrite the original algorithm in a way that combine parts (2b)–(2d) to avoid creating a new array M. 3. (15 pts) Consider the problem of linear search. The input is a sequence of n numbers A = ha1,a2,…,ani and a target value v. The output is an index i such that v = A[i] or the special value NIL if v does not appear in A. (a) Write pseudocode for a simple linear search algorithm, which will scan through the input sequence A, looking for v. (b) Using a loop invariant, prove that your algorithm is correct. Be sure that your loop invariant and proof covers the initialization, maintenance, and termination conditions. 4. (15 pts) Crabbe and Goyle are arguing about binary search. Goyle writes the following pseudocode on the board, which he claims implements a binary search for a target value v within input array A containing n elements. 2 CSCI 3104, Algorithms Problem Set 1 bSearch(A, v) { return binarySearch(A, 1, n-1, v) } binarySearch(A, l, r, v) { if l
Q1 The data in the file enzyme.csv gives the initial rate of reaction of an enzyme (y) and the substrate concentration (x). Consider the following nonlinear regression model: y = θ1x θ2 + x + ϵ where ϵi iid∼ N0, σ2 , θ1 > 0, and θ2 > 0. Assume noninformative priors for θ1, θ2, and σ 2 . You can choose appropriate prior distributions. (a) Plot the marginal posterior densities of θ1, θ2, and σ 2 . Use θ1 = 200, θ2 = 0.1, and σ 2 = 100 (equivalently, τ = 0.01) for initializing the MCMC chain. (b) Provide evidence that your model has converged, whether it is a trace plot, lack of divergences, the Gelman-Rubin statistic (Rhat), or something else. (c) Compute 95% credible intervals, the mean, and the standard deviation for each of the three parameters. (From now on, we will rarely specify which type of credible interval—you may use the default for your chosen software.) (d) Plot the posterior predictive distribution of y when x = 0.75 and provide the 95% credible intervals. Q2 Walpole et al. (2007)1 provide data from a study on the effect of magnesium ammonium phosphate on the height of chrysanthemums, which was conducted at George Mason University in order to determine a possible optimum level of fertilization, based on the enhanced vertical growth response of the chrysanthemums. Forty chrysanthemum seedlings were assigned to 4 groups, each containing 10 plants. Each was planted in a similar pot containing a uniform growth medium. An increasing concentration of MgNH4PO4, measured in grams per bushel, was added to each plant. The 4 groups of plants were grown under uniform conditions in a greenhouse for a period of 4 weeks. The treatments and the respective changes in heights, measured in centimeters, are given in the following table: 1Walpole, W. A., Myers, R. H., Myers, S. L., and Ye (2007). Probability and Statistics for Engineers and Scientists (9th ed.). Pearson Treatment 50 g/bu 100 g/bu 200 g/bu 400 g/bu 13.2 16.0 7.8 21.0 12.4 12.6 14.4 14.8 12.8 14.8 20.0 19.1 17.2 13.0 15.8 15.8 13.0 14.0 17.0 18.0 14.0 23.6 27.0 26.0 14.2 14.0 19.6 21.1 21.6 17.0 18.0 22.0 15.0 22.2 20.2 25.0 20.0 24.4 23.2 18.2 Solve the problem as a one-way ANOVA. Use STZ constraints on treatment effects. (a) Do different concentrations of MgNH4PO4 affect the average attained height of chrysanthemums? Look at the 95% credible sets for the differences between treatment effects. (b) Find the 95% credible set for the contrast µ1 − µ2 − µ3 + µ4. (c) In a standard one-way ANOVA, we assume constant variance σ 2 for each group. If you relax that assumption and put a prior on each group’s standard deviation (σi for i = 1, . . . , 4), do the results from (a) and (b) change? Do the contrasts between the posterior distributions of each σi show that they were significantly different? Q3 The data set (available as wolves.csv) described below provides skull morphometric measurements on wolves (Canis lupus L.) coming from two geographic locations: Rocky Mountain (0) and Arctic (1). The original source of the data is from Jolicoeur (1959)2 , and many authors have subsequently used this data to illustrate various multivariate statistical procedures. The goal of Jolicoeur’s study was to determine how location and gender affect skull shape among wolf populations. There were 9 predictor variables measured (see Table 1). 2Jolicoeur, P. (1959). Multivariate geographical variation in the wolf Canis lupus L. Evolution, 13(3), 283–299. Data here are given in inches. 2 Table 1: Wolf skull morphometric data (in inches) from Jolicoeur (1959)3 . Variable Description location 0 = Rocky Mountain, 1 = Arctic gender 0 = male, 1 = female x1 Palatal length x2 Postpalatal length x3 Zygomatic width x4 Palatal width (outside first upper molars) x5 Palatal width (inside second upper molars) x6 Width between postglenoid foramina x7 Interorbital width x8 Least width of the braincase x9 Crown length of the first upper molar (a) Try a frequentist logistic regression on the data (in Python, you can use the statsmodels package or sklearn). What are the results? (b) Set up a Bayesian logistic regression. Try at least three separate models, changing regression coefficient variance to increasingly informative values for each. What do you observe in the results? How do they differ from the frequentist model and from each other? (c) Re-sample the model with only three predictors: gender, x3, and x7. Give an estimate and credible interval of the probability that a female wolf with measures x3 = 5.28 and x7 = 1.78 comes from an Arctic habitat.
Q1 Pairs (Xi , Yi), i = 1, . . . , n consist of correlated standard normal random variables (mean 0, variance 1) forming a sample from a bivariate normal MVN 2(0, Σ) distribution, with covariance matrix Σ = 1 ρ ρ 1 . The density of (X, Y ) ∼ MVN 2(0, Σ) is1 f(x, y|ρ) = 1 2π p 1 − ρ 2 exp − 1 2(1 − ρ 2) (x 2 − 2ρxy + y 2 ) , with ρ as the only parameter. Take prior on ρ by assuming Jeffreys’ prior on Σ as π(Σ) = 1 |Σ| 3/2 = 1 (1−ρ2) 3/2 , since the determinant of Σ is 1 − ρ 2 . Thus π(ρ) = 1 (1 − ρ 2) 3/2 1(−1 ≤ ρ ≤ 1). (a) If (Xi , Yi), i = 1, . . . , n are observed, write down the likelihood for ρ. Write down the expression for the posterior, up to the proportionality constant (that is, un-normalized posterior as the product of likelihood and prior). (b) Since the posterior for ρ is complicated, develop a Metropolis-Hastings algorithm to sample from the posterior. Assume that n = 100 observed pairs (Xi , Yi) gave the following summaries: X 100 i=1 x 2 i = 113.5602, X 100 i=1 y 2 i = 101.6489, and X 100 i=1 xiyi = 75.1491. In forming a Metropolis-Hastings chain take the following proposal distribution for ρ: At step i generate a candidate ρ ′ from the uniform U(ρi−1 − 0.1, ρi−1 + 0.1) distribution. Why does the proposal distribution cancel in the acceptance ratio expression? (c) Simulate 51000 samples from the posterior of ρ and discard the first 1000 samples (burn in). Plot two figures: the histogram of ρs and the realizations of the chain for the last 1000 simulations (known as a trace plot). What is the Bayes estimator and 90% equitailed credible set of ρ based on the simulated chain? (d) Replace the proposal distribution from (b) by the uniform U(−1, 1) (independence proposal). Comment on the results. 1See (6.1) on page 243 in http://statbook.gatech.edu. Q2 Imagine your statistics professor made you watch him flip a coin one hundred times and record the results. He then tells you that, at some point, he switched the coin. Both of the coins had different biases for the probability of landing on heads. He challenges you to use a Bayesian change point model to estimate at which flip he started using the second coin. You should assume that there were exactly two coins used and that the change point was equally likely to have happened at any flip. The results of the coin flips can be found in flips.csv, where a value of 1 means heads and 0 means tails. (a) Set up a Gibbs sampler for your model. Put Beta(2, 2) priors on the probability of each coin coming up heads. What likelihood is appropriate? (b) In your report, include a point estimate, the 94% HPD credible set, and a density plot for the probability of each coin coming up heads and for the change point. (c) The professor then says that he actually can’t remember if he switched the coin or not. Use the posterior odds ratio for the change point to help evaluate whether the professor actually switched the coin. Based on this information, was the coin likely switched or not? Q3 In a study of mating calls in the gray tree frogs Hyla hrysoscelis and Hyla versicolor, Gerhart (1994)2 reports that in a location in Lousiana the following data on the length of male advertisement calls have been collected: Sample Average SD of size duration duration Hyla chrysoscelis 43 0.65 0.18 Hyla versicolor 12 0.54 0.14 The two species cannot be distinguished by external morphology, but H. chrysoscelis (Fig. 1) are diploids while H. versicolor are tetraploids. The triploid crosses exhibit high mortality in larval stages, and if they attain sexual maturity, they are sterile. Females responding to the mating calls try to avoid mismatches. Assume that duration observations are normally distributed with means µ1 and µ2, and precisions τ1 and τ2, for the two species respectively. For i = 1, 2, assume normal priors on µi ’s as N (0.6, 1) and gamma priors on τi ’s as Ga(20, 0.5), where 0.5 is a rate hyperparameter. (a) Based on observations and given priors, in the same loop construct two Gibbs samplers, one for (µ1, τ1) and the other for (µ2, τ2). (b) Form a sequence of differences µ1,j −µ2,j , j = 1, . . . , 11000, and after rejecting the initial 1000 differences, from the remaining simulations estimate 95% equitailed credible set for µ1 − µ2. Does this set contain zero? What can you say about the hypothesis H0 : µ1 = µ2 based on this credible set? Elaborate on whether the 2Gerhardt, H. C. (1994). Reproductive character displacement of female mate choice in the grey treefrog, Hyla chrysoscelis. Anim. Behav., 47, 959–969. 2 Figure 1: Hyla chrysoscelis length of call is a discriminatory characteristic. Hint: When no raw data are given, that is, when data are summarized via sample size, sample mean, and sample standard deviation, the following identity may be useful: Xn i=1 (yi − µ) 2 = (n − 1)s 2 + n(y − µ) 2 , where n, y, and s are sample size, sample mean, and sample standard deviation, respectively.
Q1 Marietta Traffic Authority is concerned about the repeated accidents at the intersection of Canton and Piedmont Roads. Bayes-inclined city-engineer would like to estimate the accident rate, even better, find a credible set. A well-known model for modeling the number of road accidents in a particular location/time window is the Poisson distribution. Assume that X represents the number of accidents in a 3 month period at the intersection of Canton and Piedmont Roads. Assume that [X | θ] ∼ Poi(θ). Nothing is known a priori about θ, so it is reasonable to assume the Jeffreys prior π(θ) = 1 √ θ 1(0 < θ < ∞) In the four most recent three-month periods the following realizations for X are observed: 1, 2, 0, and 2 . (a) Compare the Bayes estimator for θ with the MLE (For Poisson, recall, ˆθMLE = X¯ ). (b) Compute the 95% equitailed credible set. (c) Compute (numerically) the 95% HPD credible set. Use an optimization method, not a sampling method. (d) Numerically find the mode of the posterior, that is, MAP estimator of θ. Make sure it matches the result of the known equation for the posterior mode. (e) If you test the hypotheses H0 : θ ≥ 1 vs H1 : θ < 1 based on the posterior, which hypothesis will be favored? (f) Derive the posterior predictive distribution. Based on this, how many accidents do you predict for the next year? Q2 Waiting time. The waiting time for a bus at a given corner at a certain time of day is known to have a U(0, θ) distribution. It is desired to test H0 : 0 ≤ θ ≤ 15 versus H1 : θ > 15. From other similar routes, it is known that θ has a Pareto (5, 3) distribution. If waiting times of 10, 8, 10, 5, and 14 are observed at the given corner, calculate the posterior odds ratio and the Bayes factor. Which hypothesis would you favor? Note: the density of a Pareto distribution with parameters (c, α) is given by αcα θ α+1 1(θ > c) Q3 The Maxwell distribution with parameter α > 0, has a probability density function for x > 0 given by p(x | α) = r 2 π α 3/2x 2 exp − 1 2 αx2 (a) Find the Jeffreys prior for α. (b) Find a transformation of this parameter in which the corresponding prior is uniform. (Hint: See Section 5.7 of Engineering Biostatistics). (c) Find the posterior distribution for n independent and identically distributed datapoints x1, . . . , xn from the Maxwell distribution, assuming the Jeffreys prior on α from part (a).
Q1 Suppose data is generated from the model yi | µ iid∼ N(µ, 1) for i = 1, . . . , n. Consider a mixture normal prior: µ ∼ .5N(−1, 1) + .5N(1, 1) that is, p(µ) = .5 √ 2π e − 1 2 (µ+1)2 + .5 √ 2π e − 1 2 (µ−1)2 Suppose we have observed y = 1. Find the posterior distribution of µ. 1. Start by using Bayes theorem: p(µ | y) ∝ p(y | µ)p(µ) = p(y | µ){.5ϕ(µ; −1, 1) + .5ϕ(µ; 1, 1)} and simplify the two components using the following result. ϕx; µ1, σ2 1 ϕx; µ2, σ2 2 = ϕ x; µ1/σ2 1 + µ2/σ2 2 1/σ2 1 + 1/σ2 2 , 1 1/σ2 1 + 1/σ2 2 ϕµ1 − µ2; 0, σ2 1 + σ 2 2 where ϕx; µ, σ2 is the density of a normal distribution with mean µ and variance σ 2 . 2. The posterior is going to be a mixture of two normal distributions. So you will only need to identify the two mean and variance parameters as well as the weights for the two normal distributions. Q2 Engineering system of type k-out-of-n is operational if at least k out of n components are operational. Otherwise, the system fails. Suppose that a k-out-of-n system consists of n identical and independent elements for which the lifetime has Weibull distribution with parameters r and λ. More precisely, if T is a lifetime of a component, P(T ≥ t) = e −λtr , t ≥ 0. Time t is in units of months, and consequently, rate parameter λ is in units (month) −1 . Parameter r is dimensionless. Assume that n = 10, k = 7, r = 1.3 and λ = 1/20. 1. Find the probability that a k-out-of-n system is still operational when checked at time t 2. At the check up at time t = 6 the system was found operational. What is the probability that at that time exactly 7 components were operational? 3. At the check up at time t = 6, the system was found operational. What is the probability that the system would still be operational at the time t = 9? Hint: The probability that a k-out-of-n system is operational corresponds to the tail probability of binomial distribution: P(X ≥ k), where X is the number of components working. You can do exact binomial calculations or use binocdf in Octave/MATLAB (or dbinom in R, or scipy.stats.binom.cdf in Python). Be careful with ≤ and ui) = θ −351(θ > M) where 1(A) is 1 if A is true, and 0 if A is false. Assume noninformative (Jeffreys’) prior on θ, π(θ) = 1 θ 1(θ > 0) 2 Figure 1: First page of RAND’s book. Posterior depends on data via the maximum M and belongs to the Pareto family, Pa(c, α), with a density αcα θ α+1 1(θ > c) 1. What are α and c? 2. Estimate θ in Bayesian fashion. Then calculate the 95% equi-tailed credible set. Is the true value of parameter (0.7) in the credible set? 3. Plot the posterior PDF, adding marks for the regions bound by the above credible set, along with your point estimate, for each plot. 4. Experiment by replacing the Jeffrey’s prior with increasingly informative Pareto priors. Start with c < M and very small α. Report what happens to the posterior when varying the Pareto prior parameters and compare them to the Jeffrey’s prior model.
Q1 A student answers a multiple choice examination with two questions that have four possible answers each. Suppose that the probability that the student knows the answer to a question is 0.65 and the probability that the student guesses is 0.35. If the student guesses, the probability of guessing the correct answer is 0.25. The questions are independent, that is, knowing the answer on one question is not influenced by the other question. a) What is the probability that both questions will be answered correctly? b) Suppose both questions were answered correctly. What is the probability that the student really knew the correct answer to both questions? c) How would you generalize the above from 2 to n questions, that is, what are answers to (a) and (b) if the test has n independent questions? What happens to probabilities in (a) and (b) if n → ∞. Q2 A circuit S consisting of seven independent elements E1, . . . , E7 is connected as shown: The elements are operational during time interval T with probabilities E1 E2 E3 E4 E5 E6 E7 Probability of working (p) 0.5 0.4 0.1 0.6 0.9 0.8 0.7 a) Find the probability that the circuit is operational during time interval T. b) If the circuit was found operational at the time T, what is the probability that the element E6 was operational. Q3 A machine has four independent components, three of which fail with probability q = 1 − p, and one with probability 0.5. The machine is operational as long as at least three components are working. a) What is the probability that the machine will fail? Evaluate this probability for p = 0.75. b) If the machine failed, what is the probability that the component which fails with probability 0.5 actually failed? c) Suppose that after the machine fails, a diagnostic test is performed to determine whether the component which fails with probability 0.5 actually failed. The test is 90% accurate when this component fails (sensitivity) and 80% accurate when it does not fail (specificity). Compute the posterior probability that this component failed, given that the diagnostic test indicates a failure.
Task: Train a word2vec model using the skip-gram architecture and negative sampling. • The corpus data being trained on is the full text of 《论语》. • Use the code from Lab 4 to help you. Submit: • A modified notebook file A2_w2v.ipynb • A text file of word embeddings (.txt format) • Any other Python files your notebook depends on. • Write up the results for requirement 3 and 5 in a Word/PDF document. Requirements: 1) (10 points) Implement the data loading and processing pipeline. You should re-use and augment the code for generate_data and batchify functions. 2) (15 points) Implement the SkipGram class. The key is to implement the computation for loss in forward function. Make sure the inputs to this function are tensors in correct dimensions. 3) (10 points) Implement the train function that runs correctly. a) Print the loss every # intervals (determine the # by your own observation). Include a screenshot of loss change in your write-up. b) Briefly describe how you determine the training epochs needed by observing when the loss stops decreasing significantly. 4) (10 points) Run training with different hyper-parameters. a) Train with emb_size = 50, 100 respectively b) Train with negative sample number k = 2, 5 respectively c) Train with window_size = 1, 3 respectively Therefore, there are in total 2 × 2 × 2 = 8 experiment groups, resulting in 8 embedding files. Record the computation time. 5) (5 points) Plot and compare the embeddings. a) Use Truncated SVD to reduce the dimension of embeddings from the target words provided ([‘学’, ‘习’, ‘曰’, ‘子’, ‘人’, ‘仁’]). Plot all 8 embedding results and include the plots in your report. You may use other words instead, if they you find interesting patterns. b) Pick one embedding plot, and compare it from the plot from Lab 4 (LSA). Observe if there are differences and briefly describe. c) Save one version of word embeddings to .txt format
Task: Train a neural network-based text classification model on the Chinese humor detection dataset. The dataset is collected by this project: https://github.com/LaVi-Lab/CLEVA. Submit: The modified notebook file A1_nn.ipynb and any dependent Python files. 1. Data Processing (15 points) The original dataset (train.jsonl and test.jsonl) properly so that they can be loaded with torch.utils.data.DataLoader. The raw jsonl data looks like this: {“sentence”: “和平说：你不挨屋儿做功课你跟这儿晃悠什么呢你”, “choices”: [“0”, “1”], “label”: [0], “id”: “dev_292”} This is a negative (0) example (not humor) {“sentence”: “季春生说：你还别说，就剩这部分机能还正常”, “choices”: [“0”, “1”], “label”: [1], “id”: “dev_78”} This is a positive (1) example (humor) Requirement: a) First, use a basic tokenizer that treats each single Chinese character (字) as a token, and discard all the non-Chinese tokens (English letters, numbers, punctuations). b) Improve your tokenizer by recognizing special patterns, including consecutive digits, English words, and punctuations. 2. Build the Model (15 points) Build the neural network model using torch.nn module. Requirement: a) Use the bag-of-words method provided by nn.EmbeddingBag. b) Use at least 2 hidden layers when defining the fully-connected component. You can use the torch.nn.Sequential module for convenient implementation. 3. Train and Evaluate (10 points) Make sure your train and evaluate code can run correctly and print the accuracy information properly. Requirement: a) Train with sufficient epoch numbers (for example, 10) until you observe a good performance. b) Report the final test accuracy, precision, recall, and F-1 score. (no requirement on performance) 4. Explore Word Segmentation (10 points) Include word segmentation program to the processing step and observe how that will affect the classification performance. You can think of word segmentation as a more advanced tokenizer, which can group multiple characters (字) to a word (词). Note that the vocabulary needs be re-built once segmentation is applied, whose size will get smaller. Requirement: a) Install a word segmentation package, such as jieba: https://github.com/fxsjy/jieba. Use it to process the data and save as the new segmented data. b) Run through the train/evaluate process on the segmented data and compare the performance (accuracy and F1) with the original data. (no requirement on performance)
Q.1 Show that a subset of an antisymmetric relation is also antisymmetric. Q.2 Define a relation R on R, the set of real numbers, as follows: For all x and y in R, (x, y) ∈ R if and only if x − y is rational. Answer the followings, and explain your answers. (1) Is R reflexive? (2) Is R symmetric? (3) Is R antisymmetric? (4) Is R transitive? Q.3 How many relations are there on a set with n elements that are (a) symmetric? (b) antisymmetric? (c) irreflexive? (d) both reflexive and symmetric? (e) neither reflexive nor irreflexive? (f) both reflexive and antisymmetric? (g) symmetric, antisymmetric and transitive? Q.4 Suppose that the relation R is symmetric. Show that R∗ is symmetric. Q.5 Prove or give a counterexample to the following: For a set A and a binary relation R on A, if R is reflexive and symmetric, then R must be transitive as well. Q.6 Let R be a reflexive relation on a set A. Show that R ⊆ R2 . 1 Q.7 Let R and S both be transitive relations on a set A. For each of the relations below, either prove that it is transitive, or give a counterexample, showing that it may not be transitive. (1) R ∩ S (2) R ∪ S (3) R ◦ S Q.8 (1) Give an example to show that the transitive closure of the symmetric closure of a relation is not necessarily the same as the symmetric closure of the transitive closure of this relation. (2) Show that the transitive closure of the symmetric closure of a relation must contain the symmetric closure of the transitive closure of this relation. Q.9 Let R be the relation on Z, the set of integers, as follows: For all m and n in Z, (m, n) ∈ R if and only if 3 divides (m2 − n 2 ). (1) Prove that R is an equivalence relation. (2) Describe the equivalence classes of R. Q.10 Let S be a finite set and T be a subset of S. We define a binary relation R on the power set P(S) of set S: for subsets A and B of S, (A, B) ∈ R if and only if (A∪B)(A∩B) ⊆ T. Prove that the relation R is an equivalence relation. Q.11 Show that the relation R on Z × Z defined on (a, b)R(c, d) if and only if a + d = b + c is an equivalence relation. Q.12 Let ∼ be a relation defined on N by the rule that x ∼ y if x = 2k y or y = 2kx for some k ∈ N. Show that ∼ is an equivalence relation. 2 Q.13 Which of these are posets? (a) (Z, =) (b) (Z, ̸=) (c) (Z, ≥) (d) (Z, ̸ |) Q.14 Consider a relation ∝ on the set of functions from N + to R, such that f ∝ g if and only if f = O(g). (a) Is ∝ an equivalence relation? (b) Is ∝ a partial ordering? (c) Is ∝ a total ordering? Q.15 The relation R on the set X = {(a, b, c) : a, b, c ∈ N} with (a1, b1, c1)R(a2, b2, c2) if and only if 2a1 3 b1 5 c1 ≤ 2 a2 3 b2 5 c2 . (1) Prove that R is a partial ordering. (2) Write two comparable and two incomparable elements if they exist. (3) Find the least upper bound and the greatest lower bound of the two elements (5, 0, 1) and (1, 1, 2). (4) List a minimal and a maximal element if they exist. Q.16 Define the relation ≼ on Z × Z according to (a, b) ≼ (c, d) ⇔ (a, b) = (c, d) or a 2 + b 2 < c2 + d 2 . Show that (Z×Z, ≼) is a poset; Construct the Hasse diagram for the subposet (B, ≼), where B = {0, 1, 2} × {0, 1, 2}. 3 Q.17 We consider partially ordered sets whose elements are sets of natural numbers, and for which the ordering is given by ⊆. For each such partially ordered set, we can ask if it has a minimal or maximal element. For example, the set {{0}, {0, 1}, {2}}, has minimal elements {0}, {2}, and maximal elements {0, 1}, {2}. (a) Prove or disprove: there exists a nonempty R ⊆ P(N) with no maximal element. (b) Prove or disprove: there exists a nonempty R ⊆ P(N) with no minimal element. (c) Prove or disprove: there exists a nonempty T ⊆ P(N) that has neither minimal nor maximal elements. Q.18 Answer these questions for the poset ({3, 5, 9, 15, 24, 45}, |). (1) Find the maximal elements. (2) Find the minimal elements. (3) Is there a greatest element? (4) Is there a least element? (5) Find all upper bounds of {3, 5}. (6) Find the least upper bound of {3, 5}, if it exists. (7) Find all lower bounds of {15, 45}. (8) Find the greatest lower bound of {15, 45}, if it exists.
Q.1 Use induction to prove that 3 divides n 3 + 2n whenever n is a positive integer. Q.2 Suppose that a and b are real numbers with 0 < b < a. Prove that if n is a positive integer, then a n − b n ≤ nan−1 (a − b). Q.3 A store gives out gift certificates in the amounts of $10 and $25. What amounts of money can you make using gift certificates from the store? Prove your answer using strong induction. Q.4 Show that the principle of mathematical induction and strong induction are equivalent; that is, each can be shown to be valid from the other. Q.5 Devise a recursive algorithm to find a 2 n , where a is a real number and n is a positive integer. (use the equality 22 n+1 = (a 2 n ) 2 ) Q.6 Suppose that the function f satisfies the recurrence relation f(n) = 2f( √ n) + log n whenever n is a perfect square greater than 1 and f(2) = 1. (a) Find f(16) (b) Find a big-O estimate for f(n). [Hint: make the substitution m = log n.] Q.7 The running time of an algorithm A is described by the following recurrence relation: S(n) = { b n = 1 9S(n/2) + n 2 n > 1 where b is a positive constant and n is a power of 2. The running time of a competing algorithm B is described by the following recurrence relation: T(n) = { c n = 1 aT(n/4) + n 2 n > 1 1 where a and c are positive constants and n is a power of 4. For the rest of this problem, you may assume that n is always a power of 4. You should also assume that a > 16. (Hint: you may use the equation a log2 n = n log2 a ) (a) Find a solution for S(n). Your solution should be in closed form (in terms of b if necessary) and should not use summation. (b) Find a solution for T(n). Your solution should be in closed form (in terms of a and c if necessary) and should not use summation. (c) For what range of values of a > 16 is Algorithm B at least as efficient as Algorithm A asymptotically (T(n) = O(S(n)))? Q.8 How many bit strings of length 6 have at least one of the following properties: • start with 010 • start with 11 • end with 00 State clearly how you count and get your answer. Q.9 Suppose that n ≥ 1 is an integer. (a) How many functions are there from the set {1, 2, . . . , n} to the set {1, 2, 3}? (b) How many of the functions in part (a) are one-to-one functions? (c) How many of the functions in part (a) are onto functions? Q.10 How many 6-card poker hands consist of exactly 2 pairs? That is two of one rank of card, two of another rank of card, one of a third rank, and one of a fourth rank of card? Recall that a deck of cards consists of 4 suits each with one card of each of the 13 ranks. You should leave your answer as an equation. Q.11 How many bit strings of length 10 contain either five consecutive 0s or five consecutive 1s? 2 Q.12 Consider the equation x1 + x2 + x3 + x4 + x5 = 10. with five variables. (1) Count the number of integer solutions, with x1 ≥ 3, x2 ≥ 0, x3 ≥ −2, x4 ≥ 0, and x5 ≥ 0. (2) Count the number of integer solutions, with 0 ≤ x1 ≤ 5 and x2, x3, x4, x5 ≥ 0. Q.13 How many ordered pairs of integers (a, b) are needed to guarantee that there are two ordered pairs (a1, b1) and (a2, b2) such that a1 mod 5 = a2 mod 5 and b1 mod 5 = b2 mod 5. Q.14 Show that if p is a prime and k is an integer such that 1 ≤ k ≤ p − 1, then p divides ( p k ) . Q.15 Prove the hockeystick identity ∑r k=0 ( n + k k ) = ( n + r + 1 r ) whenever n and r are positive integers, (a) using a combinatorial argument (b) using Pascal’s identity. Q.16 For 0 ≤ k ≤ n, show that ∑n r=k ( n r )(r k ) = ( n k ) 2 n−k . Your proof may be either combinatorial or algebraic. Q.17 Find the solution to an = 2an−1 + an−2 − 2an−3 for n = 3, 4, 5, . . ., with a0 = 3, a1 = 6, and a2 = 0. 3 Q.18 A computer system considers a string of decimal digits (0, 1, . . . , 9) to be a valid code word if and only if it contains an odd number of zero digits. For example, 12030 and 11111 are not valid, but 29046 is. Let V (n) denote the number of valid n-digit code words. Find a recurrence relation for V (n) with initial cases, and give a closed-form solution to this recurrence relation. Please explain how you find the recurrence relation. (Hint: notice that the number of non-valid code words is equal to 10n − V (n).) Q.19 Let An be the n × n matrix with 2’s on its main diagonal, 1’s in all positions next to a diagonal element, and 0’s everywhere else. Find a recurrence relation for dn, the determinant of An. Solve this recurrence relation to find a formula for dn. Q.20 Use generating functions to prove Pascal’s identity: C(n, r) = C(n − 1, r) + C(n − 1, r − 1) when n and r are positive integers with r < n. [Hint: Use the identity (1 + x) n = (1 + x) n−1 + x(1 + x) n−1 .] Q.21 Use generating functions to prove Vandermonde’s identity: C(m + n, r) = ∑r k=0 C(m, r − k)C(n, k), whenever m, n, and r are nonnegative integers with r not exceeding either m or n. [Hint: Look at the coefficient of x r in both sides of (1 + x) m+n = (1 + x) m(1 + x) n .] Q.22 Generating functions are very useful, for example, provide an approach to solving linear recurrence relations. Read pp. 537-548 of the textbook. [You do not need to write anything for this problem on your submitted assignment paper.]
Q.1 What are the prime factorizations of (a) 8085 (b) 10! Q.3 For three integers a, b, y, suppose that gcd(a, y) = d1 and gcd(b, y) = d2. Prove that gcd(gcd(a, b), y) = gcd(d1, d2). Q.4 Prove the following statement. If c|(a · b), then c|(a · gcd(b, c)). Q.5 Solve the following modular equation. 312x ≡ 3 (mod 97). Q.6 Find counterexamples to each of these statements about congruences. (a) If ac ≡ bc (mod m), where a, b, c, and m are integers with m ≥ 2, then a ≡ b (mod m). (b) If a ≡ b (mod m) and c ≡ d (mod m), where a, b, c, d, and m are integers with c and d positive and m ≥ 2, then a c ≡ b d (mod m). Q.7 Prove that if a and m are positive integer such that gcd(a, m) = 1 then the function f : {0, . . . , m − 1} → {0, . . . , m − 1} defined by f(x) = (a · x) mod m is a bijection. Q.8 Convert the decimal expansion of each of these integers to a binary expansion. (a) 231 (b) 4532 1 Q.9 Let the coefficients of the polynomial f(n) = a0 + a1n + a2n 2 + · · · + at−1n t−1+n t be integers. We now show that no non-constant polynomial can generate only prime numbers for integers n. In particular, let c = f(0) = a0 be the constant term of f. (1) Show that f(cm) is a multiple of c for all m ∈ Z. (2) Show that if f is non-constant and c > 1, then as n ranges over the nonnegative integers N, there are infinitely many f(n) ∈ Z that are not primes. [Hint: You may assume the fact that the magnitude of any non-constant polynomial f(n) grows unboundedly as n grows.] (3) Conclude that for every non-constant polynomial f there must be an n ∈ N such that f(n) is not prime. [Hint: Only one case remains.] Q.10 Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m. Q.11 Prove that there are infinitely many primes of the form 4k + 3, where k is a nonnegative integer. [Hint: Suppose that there are only finitely many such primes q1, q2, . . . , qn, and consider the number 4q1q2 · · · qn − 1.] Q.12 (1) Show that if n is an integer then n 2 ≡ 0 or 1 (mod 4). (2) Show that if m is a positive integer of the form 4k +3 for some nonnegative integer k, then m is not the sum of the squares of two integers. Q.13 (a) State Fermat’s little theorem. (b) Show that Fermat’s little theorem does not hold if p is not prime. (c) Compute 302302 (mod 11), 47625367 (mod 13), 239674 (mod 523). Q.14 Let m1, m2, . . . , mn be pairwise relatively prime integers greater than or equal to 2. Show that if a ≡ b (mod mi) for i = 1, 2, . . . , n, then a ≡ b (mod m), where m = m1m2 · · · mn. 2 Q.15 Solve the system of congruence x ≡ 3 (mod 6) and x ≡ 4 (mod 7) using the methods of Chinese Remainder Theorem or back substitution. Q.16 For a collection of balls, the number is not known. If we count them by 2’s, we have 1 left over; by 3’s, we have nothing left; by 4, we have 1 left over; by 5, we have 4 left over; by 6, we have 3 left over; by 7, we have nothing left; by 8, we have 1 left over; by 9, nothing is left. How many balls are there? Give the details of your calculation. Q.17 Recall how the linear congruential method works in generating pseudorandom numbers: Initially, four parameters are chosen, i.e., the modulus m, the multiplier a, the increment c, and the seed x0. Then a sequence of numbers x1, x2, . . . , xn, . . . are generated by the following congruence xn+1 = (axn + c) (mod m). Suppose that we know the generated numbers are in the range 0, 1, . . . , 10, which means the modulus m = 11. By observing three consecutive numbers 7, 4, 6, can you predict the next number? Explain your answer. Q.18 Recall that Euler’s totient function ϕ(n) counts the number of positive integers up to a given integer n that are coprime to n. Prove that for all integers n ≥ 3, ϕ(n) is even. Q.19 Recall the RSA public key cryptosystem: Bob posts a public key (n, e) and keeps a secret key d. When Alice wants to send a message 0 < M < n to Bob, she calculates C = Me (mod n) and sends C to Bob. Bob then decrypts this by calculating C d (mod n). In class we learnt that in order to make this scheme work, n, e, d must have special properties. For each of the three public/secret key pairs listed below, answer whether it is a valid set of RSA public/secret key pairs (whether the pair satisfies the required properties), and explain your answer. (a) (n, e) = (91, 25), d = 51 (b) (n, e) = (91, 25), d = 49 (c) (n, e) = (84, 25), d = 37 3 Q.20 Consider the RSA system. Let (e, d) be a key pair for the RSA. Define λ(n) = lcm(p − 1, q − 1) and compute d ′ = e −1 mod λ(n). Will decryption using d ′ instead of d still work? (prove C d ′ mod n = M) 4
Q.1 Suppose that A, B and C are three finite sets. For each of the following, determine whether or not it is true. Explain your answers. (a) (A → B = A) → (B ⊆ A) (b) (A ∩ B ∩ C) ⊆ (A ∪ B) (c) (A → B) ∩ (B → A) = B Q.2 Prove or disprove the following. (1) For any three sets A, B, C, C → (A ∩ B)=(C → A) ∩ (C → B). (2) For any two sets A, B, P(A) ∩ P(B) = P(A ∩ B), where P(A) denotes the power set of the set A. (3) For any two sets A, B, P(A) ∪ P(B) = P(A ∪ B), where P(A) denotes the power set of the set A. (4) For a function f : X → Y , f(A ∩ B) = f(A) ∩ f(B), for any two sets A, B ⊆ X. Q.3 The symmetric difference of A and B, denoted by A ⊕ B, is the set containing those elements in either A or B, but not in both A and B. (a) Determine whether the symmetric difference is associative; that is, if A, B and C are sets, does it follow that A ⊕ (B ⊕ C)=(A ⊕ B) ⊕ C? (b) Suppose that A, B and C are sets such that A ⊕ C = B ⊕ C. Must it be the case that A = B? Q.4 For each set defined below, determine whether the set is countable or uncountable. Explain your answers. Recall that N is the set of natural numbers and R denotes the set of real numbers. 1 (a) The set of all subsets of students in CS201 (b) {(a, b)|a, b ∈ N} (c) {(a, b)|a ∈ N, b ∈ R} Q.5 Give an example of two uncountable sets A and B such that the difference A → B is (a) finite, (b) countably infinite, (c) uncountable. Q.6 Prove that P(A) ⊆ P(B) if and only if A ⊆ B. Q.7 For each set A, the identity function 1A : A → A is defined by 1A(x) = x for all x in A. Let f : A → B and g : B → A be the functions such that g ◦ f = 1A. Show that f is one-to-one and g is onto. Q.8 Suppose that two functions g : A → B and f : B → C and f ◦ g denotes the composition function. (a) If f ◦g is one-to-one and g is one-to-one, must f be one-to-one? Explain your answer. (b) If f ◦g is one-to-one and f is one-to-one, must g be one-to-one? Explain your answer. (c) If f ◦ g is one-to-one, must g be one-to-one? Explain your answer. (d) If f ◦ g is onto, must f be onto? Explain your answer. (e) If f ◦ g is onto, must g be onto? Explain your answer. Q.9 Derive the formula for !n k=1 k2. Q.10 Derive the formula for !n k=1 k3. Q.11 Find a formula for !m k=0) √ k+, when m is a positive integer. 2 Q.12 Show that if A, B, C and D are sets with |A| = |B| and |C| = |D|, then |A × C| = |B × D|. Q.13 Show that if A and B are sets with the same cardinality, then |A| ≤ |B| and |B| ≤ |A|. Q.14 Suppose that A is a countable set. Show that the set B is also countable if there is an onto function from A to B. Q.15 Show that the set Z+ ×Z+ is countable by showing that the polynomial function f : Z+ × Z+ → Z+ with f(m, n)=(m + n → 2)(m + n → 1)/2 + m is one-to-one and onto. Q.16 By the Schr¨oder-Bernstein theorem, prove that (0, 1) and [0, 1] have the same cardinality. Q.17 Suppose that f(x), g(x) and h(x) are functions such that f(x) is Θ(g(x)) and g(x) is Θ(h(x)). Show that f(x) is Θ(h(x)). Q.18 If f1(x) and f1(x) are functions from the set of positive integers to the set of positive real numbers and f1(x) and f2(x) are both Θ(g(x)), is (f1 → f2)(x) also Θ(g(x))? Either prove that it is or give a counter example. Q.19 Show that if f(x) = anxn+an−1xn−1+···+a1x+a0, where a0, a1,…,an−1, and an are real numbers and an .= 0, then f(x) is Θ(xn). Q.20 Prove that for any a > 1, Θ(loga n) = Θ(log2 n). Q.21 The conventional algorithm for evaluating a polynomial anxn+an−1xn−1+ ··· a1x+a0 at x = c can be expressed in pseudocode by where the final value Algorithm 1 polynomial (c, a0, a1,…,an: real numbers) power := 1 y := a0 for i := 1 to n do power := power ∗ c y := y + ai ∗ power end for return y {y = ancn + an−1cn−1 + ··· + a1c + a0} of y is the value of the polynomial at x = c. Exactly how many multiplica3 tions and additions are used to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable). Q.22 There is a more efficient algorithm (in terms of the number of multiplications and additions used) for evaluating polynomials than the conventional algorithm described in the previous exercise. It is called Horner’s method. This pseudocode shows how to use this method to find the value of anxn + an−1xn−1 + ··· + a1x + a0 at x = c. Algorithm 2 Horner (c, a0, a1,…,an: real numbers) y := an for i := 1 to n do y := y ∗ c + an−i end for return y {y = ancn + an−1cn−1 + ··· + a1c + a0} Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.) Q.23 (1) Show that (log n)log log n = O(log(nn)), where the base of the logarithm is 2. (2) Order the following function by asymptotic growth rates. That is, list them as f1(n), f2(n),…,f9(n), such that fi(n) = O(fi+1(n)) for all i. You don’t have to explain your answer. n2 , log n, n log n, nlog n, (log n) n, (log n) log n, (log log n) log n, (log n) log log n, 3n/2 . Q.24 Aliens from another world come to the Earth and tell us that the 3SAT problem is solvable in O(n8) time. Which of the following statements follow as a consequence? A. All NP-Complete problems are solvable in polynomial time. B. All NP-Complete problems are solvable in O(n8) time. C. All problems in NP, even those that are not NP-Complete, are solvable in polynomial time. 4 D. No NP-Complete problem can be solved faster than in O(n8) in the worst case. E. P = NP. 5
Q.1 Let p, q and r be the following propositions p: You get an A on the final exam. q: You do every exercise in this book. r: You get an A in this class. Write these propositions using p, q, and r and logical connectives (including negations). (a) You get an A in this class, but you do not do every exercise in this book. (b) To get an A in this class, it is necessary for you to get an A on the final. (c) You get an A on the final, but you don’t do every exercise in this book; nevertheless, you get an A in this class. (d) Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class. (e) You will get an A in this class if and only if you either do every exercise in this book or you get an A on the final. Q.2 Use truth tables to decide whether or not the following two propositions are equivalent. (a) (p ⊕ q) → (p ∧ q) and (p ⊕ q) → (p ⊕ ¬q) (b) p ↔ q and (p ∧ q) ∨ (¬p ∧ ¬q) (c) (¬q ∧ ¬(p → q)) and ¬p (d) (p → ¬q) ↔ (r → (p ∨ ¬q)) and q ∨ (¬p ∧ ¬r) Q.3 Use logical equivalences to prove the following statements. (a) (p ∧ ¬q) → r and p → (q ∨ r) are equivalent. 1 (b) ((p → q) ∧ (q → r)) → (p → r) is a tautology. Q.4 Show that (p → q) → r and p → (q → r) are not logically equivalent. Q.5 Suppose that p, q, r, s are all propositions. You are given the following statement (q → (r ∨ p)) → ((¬r ∨ s) ∧ ¬s). Prove that this implies ¬r using logical equivalences and inference rules. Q.6 Let L(x, y) be the statement “x loves y”, where the domain for both x and y consists of all people in the world. Use quantifiers to express each of these statement. (a) Everybody loves somebody. (b) There is somebody whom everybody loves. (c) Nobody loves everybody. (d) There is somebody whom no one loves. (e) There is exactly one person whom every body loves. (f) There are exactly two people whom Lynn loves. (g) There is someone who loves no one besides himself or herself. Q.7 Suppose that variables x and y represent real numbers, and L(x, y) : x
1. Obtain the simplified input equations for a sequential circuit that uses T flip-flops and is specified by the state diagram below. Write down the necessary procedure. (No need to draw the logic diagram) 2. Design a FlipFlop with the function table described below. Apart of the clock input, the FlipFlop has two inputs G and In. Write down necessary design procedure as we learnt in class and then draw the block diagram. (Using DFF show in the graphic symbol with extra basic gates). 3. Design a sequence detector using JKFFs to recognize the occurrence of a particular sequence of bits (1101) (using Moore machine, non-overlapping mode), write down the necessary procedure for your design (No need to draw the logic diagram) 4. (25 points) Design a sequence generator to generate the sequence 1011110 (starting with MSB) with minimum number of Flip-flops. Write down all the steps and draw the logic diagram (Graphic symbol of DFF can be used). 5. (30 points) Design a counter with T flip-flops that goes through the following binary repeated sequence: 0, 1, 3, 7, 6, 4. Derive the input equations for the FFs. Show that when binary states 010 and 101 are considered as don’t care conditions, the counter may not operate properly. Find a way to correct the design.
1. A sequential circuit has two JK flip-flops A and B and one input x. The circuit is described by the following flip-flop input equations: JA = x, KA = B JB = x, KB = A’ a) Derive the state equations A(t + 1) and B (t + 1) by substituting the input equations for the J and K variables. b) Draw the state table and state diagram of the circuit. 2. Derive the input/state/output function, state table/diagram if applicable for the sequential circuit shown in the block diagram blow. Explain the function that the circuit performs. 3. For the block diagram below a) Derive the input/state/output function, state table/diagram of the sequential circuit if applicable. b) Is it a Mealy machine or a Moore machine? Why? c) Construct a timing diagram for the circuit for an input sequence X = 101100.(Assume that initially Q1 = Q2 = 0, X always change midway during the clock low level, Complete the following waveform for Q1, Q2 and F. 4. For the following state table a) Draw the corresponding state diagram. b) Minimize the state table, show your procedures, and then draw the reduced table and its corresponding state diagram. c) Determine the output sequence for input sequence 01010010111 (from left to right) with the original state table and the reduced state table, starting from a. 5. The following latch is constructed from OR, AND and NOT gate, P is always equal to Q’. a) Construct a function table for the latch and describe the behavior. Show the procedure. b) Draw a valid timing graph to represent the behavior of the latch by covering all the valid combination of R and H. Pay attention to the forbidden state.
1. (20 points 10+10) Simplify the following Boolean function F(A, B, C, D)= ∑(1, 2 , 4, 7, 8, 9, 11), together with the don’t-care conditions d(0, 3, 5), and express the simplified Boolean function using （注意：表达式和电路图均需要，只有电路图将仅酌情得分）: a) NAND gates only using algebraic method, and draw the logic diagram corresponding to your function b) NOR gates only using algebraic method, draw the logic diagram corresponding to your function 2. (24 points 12+12) Obtain the simplified Boolean expressions for output F1 and F2 in terms of the input variables in the following circuit. a) Derive the Boolean expressions for T1 through T4. Evaluate the outputs F1 and F2 as a function of the four inputs. b) List the truth table of the four input variables. Then list the binary values for T1 through T4 and outputs F1 and F2 in the table. 3. (18 points 8+5+5) Design a combinational circuit with three inputs, A, B, and C, and three outputs, F1, F2, and F3. When the binary input is 0, 1, or 2, the binary output is two greater than the input. When the binary input is 3, 4, 5, 6, or 7, the binary output is one less than the input. You need to provide: a) List the truth table b) K-map simplification c) Draw the logic diagram 4. (18 points 6+6+6) A combinational circuit is defined by the equations F1=AB+A’B’C’ F2=A+B+C’ F3=A’B+AB’ Design a circuit which implements these three equations using a decoder and NOR gates external to the decoder, and draw the block diagram. 5. (20 points 8+6+6) An 8:1 multiplexer has inputs A, B, and C connected to the selection inputs S2, S1, and S0, respectively. The data inputs I0 through I7 are as follows: I1=I2=0; I3=I5=I7=1; I0=I4=D; and I6=D’. Determine the Boolean function F(A, B, C, D) that the multiplexer implements. You need to: a) Write down the truth table b) Simplify the Boolean function with K-map c) Redesign the circuit with ONLY 4:1 multiplexers
