Exercises

Downloads

Some content is protected. Please go to: MY > Lecture > MAT007 / Aspects of Computer Algebra

Archiv

FAQ

Details

Lecture notes

Python modules from the lecture notes and exercises

• gcd.py (functions simple_gcd, extended_gcd as a module from Section 2.2.2)

• vector.py (class Vector from Listing 2.1; updated 26.02.2013)

• rings.py (classes Integers and Rationals for Exercises 2, 3 and 7; updated 05.03.2013)

• polynomials.py (classes Polynomial and PolynomialRing for Exercises 4, 6, 7, 10, 15 and 18; updated 21.03.2013)

• polynomialstiming.py (timing tests for the Polynomial class for Exercises 10 and 15; updated 12.03.2013)

• bits.py (Exercise 11; updated 03.05.2013 with a ceil_log2() function)

• binaryexp.py (Exercise 12)

• benor.py (Exercise 13)

• exercise_14.py (Exercise 14)

• exercise_17.py (Exercise 17)

• taylor.py (Exercise 19)

• radix.py (Exercise 20)

• exercise_21.py (Exercise 21)

• heap.py (an implementation of a binary heap, compare Chapter 4)

• integerroot.py (Exercises 23 and 24)

• huffman.py (an implementation of a Huffman tree creator, compare Chapter 4)

• exercise_26.py (Exercise 26)

• fasteuclidean.py (Exercise 27)

• section_5_2.py (code from Section 5.2)

• fft.py (Exercises 33, 34 and 35)

• exercise_36.py (Exercise 36)

• matrix.py (matrix library for Chapter 6; updated 06.08.2013)

• permutation.py (Exercises 44 and 46; updated 14.05.2013)

• exercise_40.py (Exercise 40)

• exercise_41.py (Exercise 41)

• primes.py (algorithms from Section 6.5)

• exercise_45.py (Exercise 45)

• exercise_46.py (Exercise 46)

• groups.py (some abelian groups)

• exercise_47.py (Exercise 47)

• exercise_48.py (Exercise 48)

• exercise_49.py (Exercise 49)

• exercise_50.py (Exercise 50)

• smith.py (Smith Normal Form computation, see Section 6.11)

• hnf.py (HNF algorithm; Exercises 51 to 54)

• groupstest.py (simple example for groups.py)

• groupsorder.py (computes order of elements)

• groupsexp.py (computes exponent of group)

• groupsstructure.py (computes structure of subgroup generated by two elements)

• groupsstructure2.py (computes structure of generated subgroup)

Exercises

 — 

 — 

The following document contains solutions to certain exercises. It will be updated with new solutions throughout the semester.

Slides from the lectures

 — 

 — 

Corrections of the lecture notes

• 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

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

Exam

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