Lecture notes

Chapter 2: A Short Introduction to Python for Mathematicians

Chapter 3: Fast Arithmetic (updated: 27.03.2013)

Chapter 4: Algorithms and Data Structures (updated: 27.03.2013)

Chapter 5: Interpolation and the Chinese Remainder Theorem (updated: 26.04.2013)

Chapter 6: Linear Algebra (updated: 21.05.2013)

Chapter 7: Finite Groups (with end of Chapter 6, bibliography, list of algorithms and listings, and index)

Complete lecture notes (02.08.2013)

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

—

`ringstest.py`

(for Exercise 3)Exercise sheet 2

—

`moduloint.py`

(for Exercise 9; updated 21.03.2013)Exercise sheet 3

Exercise sheet 4

Exercise sheet 5

Exercise sheet 6

Exercise sheet 7 (updated 09.04.2013

Exercise sheet 8 (updated 26.04.2013)

Exercise sheet 9

Exercise sheet 10

Exercise sheet 11

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

Slides from the lectures

—

Lecture 1, practical part—

Python code (26.02.2013)Lecture 2, practical part

Lecture 3, practical part

Lecture 4, practical part

Lecture 5, practical part

Lecture 6, practical part

Lecture 7, practical part

Lecture 8, practical part

Lecture 9, practical part

Lecture 11, practical part

Lecture 12, practical part

Lecture 13, practical part

Corrections of the lecture notes

- Chapter 3, page 86, line 6: The subscript of rev in "Since
*rev*..." should be_{m}(g)(0) =*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)_{3} - 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
*â*. (21.03.2013)_{j+1}= 0 - 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*, the index of_{i}*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*and not until_{k}-2*l*. (26.04.2013)_{k}-1 - Chapter 5, page 160, Algorithm 5.1: in step 3(c),
*i*must be replaced by*l*. (26.04.2013)_{k}-1 - Chapter 5, page 171, Algorithm 5.4: the loop in 3(b) should only go until
*l*and not until_{k}-2*l*. (26.04.2013)_{k}-1 - Chapter 5, page 171, Algorithm 5.4: in step 3(c),
*i*must be replaced by*l*. (26.04.2013)_{k}-1 - Chapter 5, page 174, Algorithm 5.6: the loop in 3(b) should only go until
*l*and not until_{k}-2*l*. (26.04.2013)_{k}-1 - Chapter 5, page 174, Algorithm 5.6: in step 3(c),
*i*must be replaced by*l*. (26.04.2013)_{k}-1 - Chapter 5, page 176, Algorithm 5.9: the loop in 3(b) should only go until
*l*and not until_{k}-2*l*. (26.04.2013)_{k}-1 - Chapter 5, page 176, Algorithm 5.9: in step 3(c),
*i*must be replaced by*l*. (26.04.2013)_{k}-1 - Chapter 6, page 193, Algorithm 6.3: in step 6,
*D*has format*k*, and the top-left entry of the first displaystyle matrix in the note should be_{2}× (m - k_{1})*L*. (17.05.2013)_{1}Ũsub>1 - Chapter 6, page 197, Algorithm 6.6: in step 2(c),
*U*should be swapped with_{i•}*U*and not with_{r+1,•}*A*. (17.05.2013)_{r+1,•} - Chapter 6, page 197, Algorithm 6.6: in step 2(g),
*mU*should be subtracted from_{r•}*U*and not_{i•}*mA*. (21.05.2013)_{r•} - 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*. (17.05.2013)^{k} - Chapter 6, page 213, Algorithm 6.12, step 2, first line:
*m*should be^{i/2}||A||_{∞}^{i/2}*m*. (17.05.2013)^{i/2}||A||_{∞}^{i} - 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*. (21.05.2013)_{i}b_{i} - Chapter 6, page 218, Corollary 6.9.5: the number of basic
*e*-operations is in*O((n + m)*M*(m)*log*m)*(the log*m*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*, return_{2}, ..., j_{r-1})*(j*. (21.05.2013)_{2}-1, ..., j_{r-1}-1)

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.

Document is being generated. Please wait.

In progress..