University of Zurich - Lecture courses/details

Chapter 3, page 86, line 6: The subscript of rev in "Since rev_m(g)(0) = ..." should be m-1 and not m. (13.03.2013)
Chapter 3, page 90, Algorithm 3.6, line 4: both occurences of q̂ should be a p̂. (13.03.2013)
Chapter 3, page 91, Proposition 3.4.7, second line of the first displaystyle formula: M(m,n) should be M(mn). (13.03.2013)
Chapter 3, page 94, Algorithm 3.7, line 6: the return value should be g + p̂ · h. (13.03.2013)
Chapter 3, page 95, Theorem 3.4.10: both asymptotic running times should be O(M(log N + log d) log log N) instead of O(M(log N + log d) log d). (13.03.2013)
Chapter 3, page 103, at the bottom in the displaystyle formula for deg(r - r'), second line: the -deg g after the equality should be deg g. (13.03.2013)
Chapter 3, page 97, line 1 of Algorithm 3.9: "2-adic" instead of "b-adic". (20.03.2013)
Chapter 3, page 99, Algorithm 3.11 and page 100, proof of Theorem 3.5.6: everything having exponent e₃ should be 3 (and not 2). (Appears twice in the algorithm and twice in the proof.) (20.03.2013)
Chapter 3, page 112, Definition 3.7.4(a): the ℝ in the definition of the map DFT_ω should be an R. (20.03.2013)
Chapter 3, page 106, Algorithm 3.12: after line 7, another line should be inserted which tests whether â_j+1 = 0. (21.03.2013)
Chapter 3, page 109, Algorithm 3.13: in the last case, (a, b, c) should be computed from (1 0) A and not from (0 1) A. (21.03.2013)
Chapter 3, page 109, Algorithm 3.13: in the last lines, a does not need to be normalized anymore. Therefore, the second last line can be removed. (27.03.2013)
Chapter 3, page 109, Theorem 3.6.8: the constant in the running time should be modified to -13. This also applies to the corresponding cases in the proof. (27.03.2013)
Chapter 3, page 111, Lemma 3.7.3 (c): l can also be 1. 27.03.2013)
Chapter 3, page 112, Definition 3.7.4 (a): in the definition of b_i, the index of a should be k and not i. (27.03.2013)
Chapter 3, page 114, Algorithm 3.14, lines 2 and 3: b should be an a. (27.03.2013)
Chapter 3, page 117, Algorithm 3.15, line 1: the condition should be m ≤ 2 and not n ≤ 2. (27.03.2013)
Chapter 4, page 145, Theorem 4.2.26: in the second displayed formula, f' should be used instead of f at the beginning, and h should be denoted h_T in the first displayed equation and h_T' in the second. (27.03.2013)
Chapter 4, page 146, the large graph: inside the red boxes sometimes p was used instead of f. (27.03.2013)
Chapter 5, page 160, Algorithm 5.1: the loop in 3(b) should only go until l_k-2 and not until l_k-1. (26.04.2013)
Chapter 5, page 160, Algorithm 5.1: in step 3(c), i must be replaced by l_k-1. (26.04.2013)
Chapter 5, page 171, Algorithm 5.4: the loop in 3(b) should only go until l_k-2 and not until l_k-1. (26.04.2013)
Chapter 5, page 171, Algorithm 5.4: in step 3(c), i must be replaced by l_k-1. (26.04.2013)
Chapter 5, page 174, Algorithm 5.6: the loop in 3(b) should only go until l_k-2 and not until l_k-1. (26.04.2013)
Chapter 5, page 174, Algorithm 5.6: in step 3(c), i must be replaced by l_k-1. (26.04.2013)
Chapter 5, page 176, Algorithm 5.9: the loop in 3(b) should only go until l_k-2 and not until l_k-1. (26.04.2013)
Chapter 5, page 176, Algorithm 5.9: in step 3(c), i must be replaced by l_k-1. (26.04.2013)
Chapter 6, page 193, Algorithm 6.3: in step 6, D has format k₂ × (m - k₁), and the top-left entry of the first displaystyle matrix in the note should be L₁Ũsub>1. (17.05.2013)
Chapter 6, page 197, Algorithm 6.6: in step 2(c), U_i• should be swapped with U_r+1,• and not with A_r+1,•. (17.05.2013)
Chapter 6, page 197, Algorithm 6.6: in step 2(g), mU_r• should be subtracted from U_i• and not mA_r•. (21.05.2013)
Chapter 6, page 202, proof of Theorem 6.5.6: in the first line, 0.65 should be replaced with 1.1; the same is true for the next two occurences of 0.65 throughout this proof on the next page. (17.05.2013)
Chapter 6, page 203, Algorithm 6.9, step 2: the constant 0.65 should be replaced by 1.1. (17.05.2013)
Chapter 6, page 204, Algorithm 6.10, step 4: the CRT algorithm's number is 5.10. (17.05.2013)
Chapter 6, page 207, Algorithm 6.11, step 5(a): it should be b' := b - Ax. (17.05.2013)
Chapter 6, page 207, Algorithm 6.11, step 5(c): it should be b' := b'/p^k. (17.05.2013)
Chapter 6, page 213, Algorithm 6.12, step 2, first line: m^i/2||A||_∞^i/2 should be m^i/2||A||_∞ⁱ. (17.05.2013)
Chapter 6, page 216, Algorithm 6.14, step 4: i should run up to t and not d. (17.05.2013)
Chapter 6, page 218, Algorithm 6.15, output description: the sum inside the gcd should sum over c_ib_i. (21.05.2013)
Chapter 6, page 218, Corollary 6.9.5: the number of basic e-operations is in O((n + m)M(m)logm) (the logm factor was missing). (21.05.2013)
Chapter 6, page 220, Algorithm 6.16, step 2: the for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
Chapter 6, page 220, Algorithm 6.16, step 2: the for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
Chapter 6, page 225, Algorithm 6.19, step 6: instead of (j₂, ..., j_r-1), return (j₂-1, ..., j_r-1-1). (21.05.2013)

Exercise classes in April and May

April 9/10: exercise classes as usual
April 16/17: no exercise classes (and no lecture)
April 23/24: exercise classes as usual
April 30: exercise class in Y27 H28
May 1: no exercise class
May 7/8: exercise classes in Y27 H28
May 14/15: exercise classes as usual
May 21/22: exercise classes as usual
May 28/29: exercise classes as usual

(From April 16 to May 8, the computer room Y27 H52 is most of the time used for block course STA 220.)

Exam

The projects will be handed out and have to be returned and presented during August 2013. Alternatively, it is possible to pass a written exam instead of working on a project.

Exam

Module: 26.08.2013 9:00-12:00, Room: Y27H12 Seats: 50, Type: written exam