## Algorithms and Computability

### Lectures, realization - fall 2022

Lectures conducted by dr Michał Tuczyński

### Tutorials, realization - fall 2022

Tutorials conducted by dr Michał Tuczyński

### Laboratories, realization - fall 2022

Laboratory assignment is split between the following stages:

- Stage 1: organisation of student teams (who is with which team) and a conceptual solution of the problem (conceptual, meaning that you have a concrete idea, which you are able to express in words). Stage 1 is due on 15 X 2021. On this day students are present in the laboratory and talk with the teachers. No documentation/code is due on this day.
- Stage 2: documentation of algorithms, including algorithms pseudocode, exhaustive description, and analysis of their complexity. Due is documentation in a printed and stapled form. Due is documentation in an electronic form. Students bring the documentation in person on 28 X 2022.
- Stage 3: implementation of the algorithms and sample input preparation. Dates: 9 XI 2022 or 18 XI 2022. Students present fully working code on faculty computers without compilers installed .
- Stage 4: empirical testing of algorithms and a report on those tests. Students deliver all materials (documentation, program, sources, examples) in electronic form on 9 XII 2022 at the latest.

Grading scheme:

- Stage 1: -
- Stage 2: 33% of the grade
- Stage 3: 33% of the grade
- Stage 4: 34% of the grade

Note, that:

- a student must obtain at least half of the required points at Stages 2-4 to pass the laboratory,
- absence on any Stage is equal to -10% of the final grade of the absentee,
- if a documentation is poorly edited, contains many typos, is not printed&stapled, etc, then between 10% and 20% of the Stage's grade will be deducted (concerns Stages 2&4).

Note: each team can establish an individual schedule and procedure for the implementation of the laboratory.

### Lectures, realization - fall 2021

Lectures conducted by dr Michał Tuczyński

### Tutorials, realization - fall 2021

Tutorials conducted by dr Michał Tuczyński

### Laboratories, realization - fall 2021

Laboratory assignment is split between the following stages:

- Stage 1: organisation of student teams (who is with which team) and a conceptual solution of the problem (conceptual, meaning that you have a concrete idea, which you are able to express in words). Stage 1 is due on 8 X 2021. On this day students are present in the laboratory and talk with the teachers. No documentation/code is due on this day.
- Stage 2: documentation of algorithms, including algorithms pseudocode, exhaustive description, and analysis of their complexity. Due is documentation in a printed and stapled form. Due is documentation in an electronic form. Students bring the documentation in person on 22 X 2021 or 29 X 2021 (November 19th, 2021).
- Stage 3: implementation of the algorithms and sample input preparation. Dates: 5 XI 2021 or 19 XI 2021. Students present fully working code on lab computers. Dates: 5 XI 2021 or 19 XI 2021 or 26 XI 2021. Students present fully working code on faculty computers without compilers installed (November 19th, 2021).
- Stage 4: empirical testing of algorithms and a report on those tests. Students deliver printed and stapled documentation and a CD with the program and all documentation on 26 XI 2021. CD must be labelled using a non-washable marker with the name of the course, names of teammates, date of submission. Students deliver all materials (documentation, program, sources, examples) in electronic form on 10 XII 2021 at the latest. Details are in e-mail. (November 19th, 2021).

Grading scheme:

- Stage 1: -
- Stage 2: 33% of the grade
- Stage 3: 33% of the grade
- Stage 4: 34% of the grade

Note, that:

- a student must obtain at least half of the required points at Stages 2-4 to pass the laboratory,
- absence on any Stage is equal to -10% of the final grade of the absentee,
- if a documentation is poorly edited, contains many typos, is not printed&stapled, etc, then between 10% and 20% of the Stage's grade will be deducted (concerns Stages 2&4).

### Topics of introductory test

Problem, instance of a problem, algorithm, elementary operations, decision and optimisation problems, time and space cost functions, time and space complexity, the worst case and average complexity, uniform and logarithmic complexity criteria.

### Test/exam topics

- Problem, instance of a problem, problem vs. language, Turing Machines, deterministic and nondeterministic, step description, computation, accepted language, computed function, time and space complexity, the worst case complexity, uniform and logarithmic complexity criteria.
- Undecidability:
- Turing/RAM machines – deterministic, nondeterministic, program, acceptance, Chomsky hierarchy, binary code of Turing/RAM machines,
- diagonal and universal languages and complements of these languages, their location in Chomsky hierarchy with proofs
- emptiness and recursiveness – languages of Turing machines’s codes, their location in Chomsky hierarchy with proofs,
- Post Correspondence Problem – formulation and application,
- Oracle Turing Machines, problems hierarchy based on emptiness, equivalence of membership problem for Turing machines without Oracle and S1 (an idea of proof), equivalence of acceptance of all words with S2,

- Models of computation:
- Turing machines, RAM machines – definitions and equivalence of models,
- equivalence with regard to accepted languages: of RAM and Turing machines (idea of proof),
- equivalence with regard to complexity: RAM and Turing machines - formulation and idea of proof.

- Recursive function theory:
- the class of primitive recursive functions – definition,
- total functions and functions computed by Turing/RAM machines with stop property vs. primitive recursive functions, proofs,
- examples of primitive recursive functions, proofs of primitive recursiveness based on definition for simple functions, proofs for selected functions (bounded sum, bounded product, bounded minimum), Cantor and Godel numbering, proofs of primitive recursiveness of Cantor’s encoding and decoding functions),
- Ackerman function, its formula, an idea of construction, an idea of proof that it is not primitive recursive, an idea of proof that it is recursive,
- classes of recursive functions (primitive recursive, recursive, partial recursive), definitions, the hierarchy of recursive functions, inclusions and justifications.

- Classes of recursive functions vs. classes of Turing/RAM machines, idea of proofs.
- Complexity theory - characterization of spaces of problems and/or languages::
- polynomial transformation of decisions problems and of languages, definitions, transitiveness, examples,
- classes of problems with regard to time complexity: P, NP, NP- complete, coNP, coNP-complete, NPI – definitions, inclusions, justifications,
- NP-complete problems examples, Cook theorem with proof, lemma for proving NP-completeness with proof,
- classes of problems with regard to space complexity: P-space, NP- space, DLOGSPACE, POLYLOGSPACE, definitions,
- Savitch theorem with proof, inclusions of space complexity classes of problems,
- relations between time and space complexity classes of problems.

- The P?=NP problem, attempts to prove the P?=NP problem: p-izomorfizm, density of languages, nonemptiness of the NPI class, relations between NP and coNP classes (formulation of attempts).

## Course description:

Course title |
Algorithms and Computability |

Program |
BSc |

Status of the Course: |
compulsory |

Responsible person: |
Władysław Homenda, PhD, DSc |

Hours per week, assessment method |
2 / 1 / 1/ 0 / pass |

Internal code no |
---- |

### Lectures:

- Decidability
- Recursive and recursively enumerable languages, decidable, partially decidable and undecidable problems
- Models of computation: Turing machine, RAM machines
- Equivalence of computation models
- Recursive function theory; bounded and unbounded minimum, primitive recursive, recursive and recursively enumerable functions
- Turing computability
- Church hypothesis

- Complexity
- Time complexity of algorithms
- Classes P, QL, NQL, NPI, NP, co-NP
- NP-complete problems, Cook theorem
- Examples of NP problems
- Complexity equivalence of computation models
- Space complexity of algorithms
- Classes DLOG, POLYLOG, P, Sawitch theorem

### Tutorials:

Solving problems related to lecture’s topics

### Laboraty:

Empirical verification of some topics of complexity theory

### Reference books:

- Aho A,V, Hopcroft J,E, Ullman J,D, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company,
- Aho A,V, Hopcroft J,E, Ullman J,D, The design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company,
- Bovet P,B, Crescenzi P, Introduction to the theory of Complexity, Prentice Hall,
- Moret M,B, The Theory of Computation, Addison-Wesley Publishing Company,
- C. H. Papadimitriou, Złożonoscc obliczeniowa, WNT, Warszawa
- Yasuhara A, Recursive Function Theory and Logic, Academic Press,

### Required prerequisites:

Algorithms and Data Structures

Automata Theory and Languages

### Assessment method:

Passing the subject requires

- passing theory and practice, both must be completed during current academic year,
- it is necessary to complete without mistakes the introductory test (second half of October) and to complete final test (at the end of November) in order to pass theory the method of passing the theory is defined by Dr. Michał Tuczyński,
- solving a given problem and preparing documentation in the semester time. Presence at laboratory hours is claimed in order to control progress of problem solving,
- final grade is the average of theory and practice assessments rounded towards theory grade.