Algorithms and Computability

 

Lectures, realization - fall 2024

conducted with Prof. Agnieszka Jastrzębska,

  1. 3 X 2024. Organisational arrangements. Description of a laboratory task. Primitive recursive functions, definition, examples, sum, product, limited difference etc., bounded sum, bounded product, bounded minimum, quotient, reminder, divisor, numer of divisors, prime numbers, proofs of primitive recursivity.
  2. 17 X 2024. Properties of primitive recursive functions: total functions, proof; Cantor encoding/decoding, proof; Godel encoding/decoding, proof - hints. Ackerman function, properties, proof (basic steps) that is not primitive recursive.
  3. 24 X 2024. The hierarchy of recursive functions, strict inclusions. Ackerman function, proof (basic steps) that is recursive. Grzegorczyk hierarchy, Ritchie hierarchy - just information not required for passing. Equivalence of the classes of Turing machines and the classes of recursive functions, proofs (basic steps). Church hypothesis. (AJ)
    - - - 31 X 2024. Lecture cancelled.
  4. 7 XI 2024. Introduction to complexity theory: problem, instance of a problem, algorithm, elementary operations, dominant operations, cost functions, time and space complexity, pessimistic (the worst case) and average complexity. (AJ)
  5. 21 XI 2024. Problems, decision problems, decision functions. Polynomial transformation, defintion, transitivity. Classes of decion problems P, NP, coNP, NPC. Cook's Theorem, proof.
  6. 28 XI 2024. Revision of material, consultations, dean's hours.
  7. 5 XII 2024. Characterisation of the problems' space with regard to space complexity, Savitch Theorem, P-space=NP-space, polynomial hierarchy. (AJ)
  8. 12 XII 2024. Equivalence of classes: decision problems, decision functions, formal languages. Decidability/computability/recursiveness and derived concepts. The problem P?=NP, attempts to prove.
  9. 19 XII 2024. Revision of material, consultations.
  10. 9 I 2025. Completing the subject.

 

Tutorials, realization - fall 2024

Tutorials conducted by Prof. Anna Zamojska-Dzienio

 

Laboratories, realization - fall 2024

Laboratory assignment is split between the following stages:

  1. 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 11 X 2024. On this day students are present in the laboratory and talk with the teachers. No documentation/code is due on this day.
  2. Stage 2: documentation of algorithms, including algorithms pseudocode, exhaustive description, and analysis of their complexity. Due is documentation in an electronic form. Students bring the documentation in person on 25 X 2024.
  3. Stage 3: implementation of the algorithms and sample input preparation. Deadline: 15 XI 2024. Students present fully working code on faculty computers without compilers installed .
  4. Stage 4: empirical testing of algorithms and a report on those tests. Students deliver all materials (documentation, program, sources, examples) in electronic form on 6 XII 2024 at the latest.

Grading scheme:

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

Note, that:

  1. a student must obtain at least half of the required points at Stages 2-4 to pass the laboratory,
  2. absence on any Stage is equal to -10% of the final grade of the absentee,
  3. 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 2023

  1. 5 X 2023. Organisational arrangements. Description of laboratory task. RAM machines, definitione, simplified model, equivalence of basic and simplified models, examples of simple RAM machines (programs).
  2. 12 X 2023. RAM machines with indirect addressing. Equivalence of the class of RAM machines with direct and indirect addressing and the class of Turing machines.
  3. 19 X 2023. Primitive recursive functions, definition, examples, sum, product, limited difference etc., bounded sum, bounded product, bounded minimum, quotient, reminder, divisor, numer of divisors, prime numbers, proofs of primitive recursivity.
  4. 2 XI 2023. Properties of primitive recursive functions: total functions, proof; Cantor encoding and decoding, proof; Godel encoding/decoding, proof - hints. Ackerman function, properties, proof (basic steps) that is not primitive recursive.
  5. 9 XI 2023. Ackerman function, proof (basic steps) that is recursive. The hierarchy of recursive functions, strict inclusions. Equivalence of the classes of Turing machines and the classes of recursive functions, proofs (basic steps). Church hypothesis.
  6. 16 XI 2023. Introduction to complexity theory: problem, instance of a problem, algorithm, elementary operations, dominant operations, cost functions, time and space complexity, pessimistic (the worst case) and average complexity.
  7. 23 XI 2023. Value vs. logarithm of value as size od numbers, uniform vs. logarithmic complexity criteria, examples. Complexity theory: polynomial transformation and its transitivity, classes P, NP, coNP of decidable problems.
  8. 14 XII 2023. Test.
  9. 21 XII 2023. Study on Cook Theorem and Savitch Theorem. Consultations.

 

Tutorials, realization - fall 2023

Tutorials conducted by MSc Paweł Wesołowski

 

Laboratories, realization - fall 2023

Laboratory assignment is split between the following stages:

  1. 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.
  2. 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.
  3. 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 .
  4. Stage 4: empirical testing of algorithms and a report on those tests. Students deliver all materials (documentation, program, sources, examples) in electronic form on 5 XII 2022 at the latest.

Grading scheme:

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

Note, that:

  1. a student must obtain at least half of the required points at Stages 2-4 to pass the laboratory,
  2. absence on any Stage is equal to -10% of the final grade of the absentee,
  3. 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 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:

  1. 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.
  2. 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.
  3. 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 .
  4. 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:

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

Note, that:

  1. a student must obtain at least half of the required points at Stages 2-4 to pass the laboratory,
  2. absence on any Stage is equal to -10% of the final grade of the absentee,
  3. 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.

 

 

 

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:

  1. 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
  2. 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:

  1. Aho A,V, Hopcroft J,E, Ullman J,D, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing Company,
  2. Aho A,V, Hopcroft J,E, Ullman J,D, The design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company,
  3. Bovet P,B, Crescenzi P, Introduction to the theory of Complexity, Prentice Hall,
  4. Moret M,B, The Theory of Computation, Addison-Wesley Publishing Company,
  5. C. H. Papadimitriou, Złożonoscc obliczeniowa, WNT, Warszawa
  6. 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

  1. passing theory and practice, both must be completed during current academic year,
  2. 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 Prof. Anna Zamojska-Dzienio,
  3. 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,
  4. final grade is the average of theory and practice assessments rounded towards theory grade.