# Course Identification

Algebraic structures for computer scientists
20234121

## Lecturers and Teaching Assistants

Dr. Josephine Shamash
N/A

## Course Schedule and Location

2023
First Semester
Tuesday, 09:15 - 11:00, Ziskind, Rm 1
08/11/2022
10/02/2023

## Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 2.00 points

N/A

## Prerequisites

A knowledge of linear algebra

15

English

## Attendance and participation

Expected and Recommended

Numerical (out of 100)

20%
80%

Take-home exam

N/A
N/A
-
N/A

N/A

## Syllabus

Syllabus: Finite Algebraic Structures for CS

Josephine Shamash

Fall 2022

This course is intended for computer science students who have not taken advanced algebra courses as part of their first degree. The course focuses on the theory of finite structures which are important in applications of algebra to computer science, especially for error-correcting codes. Detailed examples will be investigated.

1.         Basics: Fields, rings, groups, vector spaces and their substructures. Homomorphisms of rings, ideals, quotient rings.

2.         Polynomial rings over fields and their properties. The Chinese remainder Theorem and its corollary for the structure of Z/mZ,

3.         Finite Group theory: Introduction, finite cyclic groups and their properties, the fundamental theorem of finite abelian groups.

4.         Sylow's theorems and applications to examples. (Solvability and Rips exercise of numbers up to 100)

5.         The symmetric groups: their conjugacy classes and structure. Simplicity of the alternating group for .

6.         Finite Simple groups and the classification theorem – survey.

7.         Introduction to complex characters and representations of finite groups

8.         Finite Field theory: Basic extension theorem, Finite fields, their structure and properties. Existence and uniqueness of finite fields of order q for any prime power q. Detailed examples and arithmetic in finite fields.

9.         Factorization of polynomials over finite fields.

10.       Wedderburn's theorem that finite division rings are finite fields.

11.       Counting irreducible polynomials over finite fields. Finding irreducible polynomials for error-correcting codes over finite fields using the Berlekamp algorithm. (skipped 2019)

12.       The structure of some classical matrix groups over finite fields, conjugacy classes in finite matrix groups, detailed examples.

13.       Vector spaces over finite fields and error-correcting codes: Bilinear forms and orthogonality in finite dimensional vector spaces over fields of characteristic 2.

14.       The theory of linear codes over finite fields of characteristic 2.

Examples: Hamming codes, using the structure of the field of 16 elements to define the BCH double-error correcting code.

Bibliography:

Nathan Jacobson: Basic Algebra I & II

I. Martin Isaacs: Algebra: A Graduate Course (Chapter 21 on finite fields)

Serge Lang: Algebra

Vera Pless.: Error-correcting Codes

Ian Stewart: Galois Theory

• online:

## Learning Outcomes

A general knowledge of finite algebraic structures, and detailed finite examples relevant to computer scientists.