Entrance Exam

Today I had my written entrance exam. I was scared I'd fail like a kanji tattoo, but it seems like it's going to be fine. For those I haven't bored to tears yet, the exam I took had two sections (T and A, I kid you not!). The T section had 5 questions, and the A section had 6. T is mostly basics (maths, computing, physics), while A has some more specialised topics (Internet protocols, programming, logic circuits, GIS...). I had to choose 2 questions from the T group, and one more question from anywhere. However, despite always having been partial to T's, I chose 2 T's and 1 A instead of all three T's. Three T's is just too weird. Anyway, here are the questions, as far as I can recall them, after my 2-hour trial and/or tribulation:

1. {a_n} is a sequence of the form: a_n = a_n-1 + a_n-2, a₀ = x, a₁ = y
   
   
   
   1. There is a recursive algorithm to calculate a_n. Explain it, and show its complexity.
   
   
   2. [a_n, a_n-1]^T can be expressed as a product of Q and [a_n-1, a_n-2]^T, where Q = [ q₁₁, q₁₂ | q₂₁, q₂₂]. Calculate Q.
   
   
   3. Show an optimised algorithm for calculating a_n by using Q. Show its complexity.
   
   
   4. For x=1 and y=3, calculate a₄₈
   
   
   5. {a_n,m} is a sequence where a_n,m = a_n-2,m + a_n-1,m mod m. Show {a_n,m} is cyclic.
   
   
   6. What is the period of a_n,3?
   
   
   
   


2. There is a test by Alan Turing that determines the quality of artificial intelligence systems.
   
   
   
   1. What is its name?
   
   
   2. Describe it (in about 5 lines)
   
   
   3. In about 15 lines, describe its influence and criticisms, using these words:
      Loebner prize, common sense, John Searle, speech recognition, Chinese Room, natural language processing, Eliza
   
   
   
   


3. In C,
   
   
   
   1. define the sort function of signature: void sort(int array[], int n).
   
   
   2. for a structure List { List *next, int v }, define the reverse function of signature: List *reverse(List *list).
   
   
   
   

I think I didn't do too badly. I'm pretty sure I aced the TOEFL two weeks ago, and that I'm over the threshold with the current offering. And if I am, I'll probably do well on the interview next week, since I'm told they'll be asking me about my research plan. And I know in quite a detail what I want to research. The quotas are not too bad either, despite what I thought before: 45 candidates for 19 places is not too bad. So even if I don't manage to pass, I'm satisfied that I did the best I could, and didn't make a monkey or a cabbage out of myself.