## Algorithms and Computability

### Lectures, realization - fall 2018

• 3 X 2018 (We) Organisational arrangements. Introduction to complexity theory: problem, instance of a problem, algorithm, elementary operations, cost functions, time and space complexity, pessimistic (the worst case) and average complexity.
• 4 X 2018 (Th) Description of laboratory problem. Dominant operations. Uniform and logarithmic complexity criteria, examples.
• 11 X 2018 (Th) Value vs. logarithm of value as size od numbers, uniform vs. logarithmic complexity criteria, examples. RAM machines, definitione, simple model, sum of two integers, direct and indirect addressing.
• 17 X 2018 (We) Equivalence of classes of Turing machines and RAM machines with direct addressing. Turing machines simulating RAM machines with indirect addressing.
• 18 X 2018 (Th) Primitive recursive functions, definition, examples. Properties: total functions, computed by Turing machines with stop properties, proofs.
• 24 X 2018 (We) Primitive recursive functions cont., bounded sum, bounded product, bounded minimum, quotient, reminder, divisor, numer of divisors, prime numer, Cantor encoding and decoding, proofs.
• 25 X 2018 (Th) Godel encoding/decoding. Ackerman function, properties, proof (basic steps) that is not primitive recursive.
• 8 XI 2018 (Th) Equivalence of the classes of recursive functions and the classes of Turing machines.
• 14 XI 2018 (We) Church hypothesis. Complexity theory: polynomial transformation and its transitivity, classes P, NP, NPC of decidable problems, lemma about transformation of NPC problem to NP problem, SAT problem, Cook Theorem.
• 15 XI 2018 (Th) Cook Theorem, proof. Savitch Theorem, formulation. Classes P-space, NP-space.
• 21 XI 2018 (We) Attempts to answer question P=NP.
• 22 XI 2018 (Th) Polynomial hierarchy.
• 28 XI 2018 (We) Self evaluation questionnaire. Assessments of theory.
• 29 XI 2018 (Th) Assessments of theory.
• 11 I 2019 (Fr) Retaken assessments of theory, 16.15, room 216.

### Tutorials, realization - fall 2018

• 5 X 2018 Characterisation of the space of languages: classes of recursive, recursively enumerable and not recursively enumerable languages. Languages diagonal and universal and their inclusion in respective classes.
• 12 X 2018 Equivalence of classes of Turing machines and RAM machines.
• 19 X 2018 Primitive recursive functions, examples. RAM machines simulating Turing machines.
• 26 X 2018 Classes of recursive and partially recursive functions.
• 9 XI 2018 Equivalence of the classes of recursive functions and the classes of Turing machines, cont.
• 16 XI 2018 Savitch Theorem, proof.
• 23 XI 2018 Reviewing.

### Laboratories, realization - fall 2018

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 16.10.2018. 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. Students bring the documentation in person on 6.11.2018.
• Stage 3: implementation of the algorithms and sample input preparation. Dates: 13.11.2018 or 20.11.2018. Students present fully working code on lab computers.
• 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 the CD on 27.11.2018 or 11.12.2018. CD must be labelled using a non-washable marker with the name of the course, names of teammates, date of submission.

• Stage 1: -
• Stage 2: 50% of the grade
• Stage 3: 25% of the grade
• Stage 4: 25% of the grade

Note, that:

• a student must obtain at least half of the required points at Stages 2-4 to pass the course,
• 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 we will deduct between 10% and 20% of this Stage's grade (concerns Stages 2&4).

### Lectures, realization - fall 2017

• 4 X 2017 (We) Organisational arrangements. Introduction to complexity theory: problem, instance of a problem, algorithm, elementary operations, cost functions, time and space complexity, pessimistic (the worst case) and average complexity.
• 4 X 2017 (Th) Dominant operations. Uniform and logarithmic complexity criteria, examples.
• 11 X 2017 (We) RAM machines, definition, simplified model, equivalence of basic and simplified models, examples of programs: concatenating contents of registers, copying revert contents of register, sum of binary numbers.
• 12 X 2017 (Th) RAM machines with indirect addressing, equivalence of this class of RAM machines and the class of Turing machines. Setting new assesment method.
• 18 X 2017 (We) Primitive recursive functions, examples, totality, computability with Turing machines with stop property.
• 19 X 2017 (Th) Primitive recursive functions cont., limited sum and product, bounded minimum, quotient, reminder, divisor, number of divisors, prime number.
• 26 X 2017 (Th) Primitive recursive functions cont. Cantor and Godel encoding/decoding. Ackerman function, properties, proof (basic steps) that is not primitive recursive.
• 2 XI 2017 (Th) Unbounded minimum, classes of recursive and partially recursive functions, recursiveness of Ackerman function. Equivalence of classes of recursive and partially recursive functions and Turing machines with stop property and Turing machines, proof that classes of recursive functions are computed by corresponding classes of Turing machines. Proof that Turing machines are simulated by recursive functions at tutorials.
• 8 XI 2017 (We) Fundamentals of complexity theory: problems, decidable decision problems, instances of problems, polynomial transformation, transitivity of polynomial transformation, classes P, NP, coNP.
• 9 XI 2017 (Th) Class NPC, lemma about NPC problem, Cook Theorem with proof.
• 15 XI 2017 (We) WUT DAY, classes canceled.
• 23 XI 2017 (Th) Savitch Theorem, classes of problems with regard to time and pace complexity.
• 29 XI 2017 (We) Attempts to prove the P=NP? problem.
• 30 XI 2017 (Th) Assessments.
• 11 I 2018 (Th). Assessments, time and place - see Announcements.

### Tutorials, realization - fall 2017

Tutorials are conducted by dr Michał Tuczyński

• 9/11 X 2017 Characterisation of the space of languages: recursive languages, recursively enumerable and complementary to recursively enumerable, not recursively enumerable / complementary. Languages Lne, Le, Lr, Lnr.
• xxxx x xxxx Not reported by Dr. M. Tuczyński.

### Laboratories, realization - fall 2017

Stages of the project:

• The first stage includes graphical user interface, importing input data and controlling program parameters. The first stage should be completed and submitted in October.
• The second stage includes methodological preparation and implementing of considered methods and their presentation for the whole laboratory group. The second stage should be completed and submitted in November.
• The third stage includes empirical verification of considered methods, tests reports and integration of documentation of all stages including technical documentation. The third stage should be completed and submitted in November.

Notes:

• Evaluation of the project: stages I and II - up to 15 pt each, stage III - up to 70 pt.
• It is students responsibility to agree earlier with teacher(s) testing data preparation.
• Every commenced week of delay will cost -9 pt.
• Requirements:
• source code documentation (contact dr. A. Jastrzębska for details),
• project report describes: project objectives, problem presentation, applied method/algorithm, test data, critical analysis of results, conclusions.
• Students are encouraged to complete stages and the whole project before deadlines.
• Schedule is at the web page of Agnieszka Jastrzębska, PhD. She conducts laboratories with me.

• 51 - 60 points - C
• 61 - 70 points - C+
• 71 - 80 points - B
• 81 - 90 points - B+
• 91 - 100 points - A

### Lectures, realization - fall 2016

• 5 X 2016 (We) Recursive and recursively enumerable languages. Universal and diagonal languages and their complements. Characterisation of the space of languages: recursive languages, recursively enumerable and complementary to recursively enumerable, not recursively enumerable / complementary. Languages Lne, Le, Lr, Lnr.
• 6 X 2016 (Th) Organisational arrangements. Introduction to laboratory project. Introduction to complexity theory: problem, instance of a problem, algorithm, elementary operations, cost function.
• 12 X 2016 (We) Dominant operations, time and space complexity, pessimistic (the worst case) and average complexity, uniform and logarithmic cost criteria.
• 13 X 2016 (Th) RAM machines, definition, simplified model, equivalence of basic and simplified models, examples of programs: concatenating contents of registers, copying revert contents of register, sum of binary numbers.
• 19 X 2016 (We) Equivalence of classes of RAM machines and Turing machines.
• 20 X 2016 (Th) Primitive recursive functions, definition, examples.
• 26 X 2016 (We) Primitive recursive functions, totality, computability by Turing machines, Godel numbering.
• 27 X 2016 (Th) Introductory test. Ackerman function, introduction.
• 2 XI 2016 (We) Unbounded minimum, regular functions. Recursive functions and partially recursive functions. Proof that Ackerman function is recursive one. Hierarchy of classes of recursive functions (strict inclusions).
• 3 XI 2016.(Th) Proof that classes of recursive functions are computed by Turing machines (homework). Simulation of computations of (classes of) Turing machines by (classes of) recursive functions. Church hypothesis. Polynomial transformation, definition.
• 9 XI 2016 (We) Cook's Theorem.
• 16 XI 2016 (We) Attempts to answer the question P=NP?
• 17 XI 2016 (Th) Savitch Theorem.
• 24 XI 2016 1 XII 2016, 4 PM, room 102, (Th) Final test.
• December XII 2016 Assessment, details in the tab "Announcements".
• 9 I 2017 Final test retaken, details in the tab "Announcements".

### Tutorials, realization - fall 2016

• 3 X 2016. Recursive and recursively enumerable languages. Universal and diagonal languages and their complements. Characterisation of the space of languages: recursive languages, recursively enumerable and complementary to recursively enumerable, not recursively enumerable / complementary. Languages Lne, Le, Lr, Lnr.
• 10 X 2016. Languages Ld, Lu, Lne, Le, Lr, Lnr - cont. Characterisation of the classes of RkL, REL, coREL and All languages. Equivalence of the spaces of languages, decision problems and decision function (intuitive justification).
• 17 X 2016. Equivalence of classes of RAM machines and Turing machines.
• 24 X 2016. Primitive recursive functions, bounded minimum, quotient and relative functions, Cantor encoding and decoding.
• 7 XI 2016 Transitivity of polynomial transformation, classes P, NP, coNP and NPC of problems, transforming NPC problem to a NP problem, NPC problem solved deterministically in polynomial time.
• 14 XI 2016 Examples of NPC problems, proofs
• 21 XI 2016. Preparation to final test - consultations.
• xx xx xxx. Introductory test, retaken no need

### Laboratories, realization - fall 2016

Stages of the project:

• The first stage includes graphical user interface, importing input data and controlling program parameters. The first stage should be completed and submitted in October.
• The second stage includes methodological preparation and implementing of considered methods and their presentation for the whole laboratory group. The second stage should be completed and submitted in November.
• The third stage includes empirical verification of considered methods, tests reports and integration of documentation of all stages including technical documentation. The third stage should be completed and submitted in November.

Notes:

• Evaluation of the project: stages I and II - up to 15 pt each, stage III - up to 70 pt.
• It is students responsibility to agree earlier with teacher(s) testing data preparation.
• Every commenced week of delay will cost -9 pt.
• Requirements:
• source code documentation (contact dr. A. Jastrzębska for details),
• project report describes: project objectives, problem presentation, applied method/algorithm, test data, critical analysis of results, conclusions.
• Students are encouraged to complete stages and the whole project before deadlines.
• Schedule is at the web page of Agnieszka Jastrzębska, PhD. She conducts laboratories with me.

• 51 - 60 points - C
• 61 - 70 points - C+
• 71 - 80 points - B
• 81 - 90 points - B+
• 91 - 100 points - A

### Lectures, realization - fall 2015

• 5 X 2015 (Mo) Organisational arrangements. Introduction: problem, instance of a problem, algorithm, elementary operations, cost function, pesimistic and average time complexity, space complexity.
• 8 X 2015 (Th) Uniform and logarithmic criteria, when and how apply. Equivalence of spaces of decision problems, languages and decision functions. Recursive and recursively enumerable languages, computable and partially computable decision functions, decidable and partially decidable decision problems. Universal and diagonal languages and their complements.
• 12 X 2015 (Mo) Characterisation of the space of languages (and so of decision problems and of decision functions): recursive languages, recursively enumerable and complementary to recursively enumerable, not recursively enumerable / complementary. Languages Lne, Le, Lr, Lnr.
• 15 X 2015 (Th) RAM machines, definition of basic model; examples of RAM machines: testing eveness of binary numer, adding binary numbers.
• 19 X 2015 (Mo) Equivalence of classes of RAM machines and Turing machines, complexity of simulation. Introductory test.
• 22 X 2015 (Th) Primitive recursive functions, definition, properties: total and computed by Turing machines with stop property, examples.
• 26 X 2015 (Mo) Primitive recursive functions (cont.) - bounded minimum, quotient and related functions, Cantor and Godel numberings.
• 29 X 2015 (Th) Unbounded minimum, regular functions. Recursive functions and partially recursive functions. Proof that Ackerman function is recursive one. Hierarchy of classes of recursive functions (strict inclusions). Proof that classes of recursive functions are computed by Turing machines.
• 2 XI 2015 (Mo) Simulation of computations of (classes of) Turing machines by (classes of) recursive functions. Church hypothesis.
• 5 XI 2015 (Th) Polynomial transformation, transitivity. Classes of problems: NP, coNP, P, EXP, NPC. Cook theorem, proof (tbc.)
• 9 XI 2015 (Mo) Cook theorem, proof. Savitch theorem, proof. Characterisation of the class of the class of decidable problem, classes P, Np, coNP, NPC, P-space, NP-space.
• 19 XI 2015 (Th) Attempts to answer the question P=NP?
• 26 XI 2015 (Th) Preparing to final test.
• 30 XI 2015 (Mo) Final test.
• 12 I 2016 (Tu), 2-4 PM, room 329. Final test, 2nd attempt.

### Tutorials, realization - fall 2015

• 8 X 2015. Introduction to laboratory project.
• 15 X 2015. Characterisation of the space of languages, languages Lne, Le, Lr, Lnr
• 22 X 2015. RAM machine with reduces set of commands, direct and indirect addressing.
• 29 X 2015. Ackerman function, proof that it is not primitive recursive.
• 5 XI 2015. Examples of primitive recursive functions, proofs. Polynomial transformation, definition, example.
• 20 XI 2015, 4-6 PM. Quasi linear transformation, classes of problems QL, NQL, NQLC.
• 26 XI 2015. Controlling laboratory problem.
• 15 XII 2015 (Tu), 3 PM, room 329. Introductory test, 2nd attempt.

### Laboratories, realization - fall 2015

Stages of the project:

• The first stage includes elaboration and documentation of methodology and should be completed and submitted in October.
• The second stage includes implementation of considered methods and documentation of the program, should be completed and submitted in November.
• The third stage includes empirical verification of considered methods, tests reports and integration of documentation of all stages, should be completed and submitted by mid December.

Notes:

• Evaluation of the project: stages I and II - up to 25 pt each, stage III - up to 50 pt.
• It is students responsibility to agree earlier with teacher(s) dates/time and ways of reporting results of every stage in order to meet deadlines.
• Every week of delay will cost -7 pt. First (one) delay during I or II stage may not be punished.
• Students are encouraged to complete stages and the whole project before deadlines.

• 51 - 60 points - C
• 61 - 70 points - C+
• 71 - 80 points - B
• 81 - 90 points - B+
• 91 - 100 points - A

Schedule could be found at the web page of Agnieszka Jastrzębska, MSc. She conducts laboratories with me.

### Lectures, realization - fall 2014

• 2 X 2014 (Th). Introduction: problem, algorithm, elementary operations, cost function, pesimistic and average time complexity, space complexity.
• 6 X 2014 (Mo). Laboratory problem - discussion.
• 9 X 2014 (Th). Introduction: dominant operations, asymptotic evaluations, uniform and logarithmic cost criteria. Equivalence of spaces of decision problems, languages and decision functions. Models of computations (Turing machines, RAM machines, recursive functions. Classes of recursive languages, recursively enumerable languages and their complements.
• 13 X 2014 (Mo). Characterization of the class of problems/languages/functions. Closeness of the classes of recursive and recursively enumerable languages, example of recursively enumerable languages, their complements and non recursive languages.
• 16 X 2014 (Th). RAM machines, equivalence of the class of Turing Machines and the class of RAM machines.
• 20 X 2014 (Mo) Primitive recursive functions, definition, totality and computability by Turing machines, examples.
• 23 X 2014 (Th). Primitive recursive functions - examples, Cantor and Godel encoding and decoding. Ackerman function.
• 27 X 2014 (Mo). Recursive and partially recursive functions. Equivalence of classes of recursive and partially recursive functions and Turing machines with stop property and Turing machines.
• 30 X 2014 (Th) Equivalence of classes of recursive and partially recursive functions and Turing machines with stop property and Turing machines (cont.)
• 3 XI 2014 (Mo) Polynomial transformation, classes of problems P, NP, coNP, EXP. Examples of NP problems, complementary problems.
• 13 XI 2014 (Th). Cook theorem, proof. Savitch theorem, proof.
• 17 XI 2014 (Mo). Attempts to answer if P?=NP: p-isomorphism, density of languages, nonemptinees of the class NPI, NP?=coNP. Complexity classes: P-space=NP-space, relations between time and space complexity classes.
• 20 XI 2014 (Th). Preparations to final test.
• 27 XI 2014 (Th). Final test.
• January 2015 (time and place will be announced later,  see Announcements). Final test - second attempt.

### Tutorials, realization - fall 2014

• 2 X 2014 (Th). Introduction to laboratory problem.
• 9 X 2014 (Th). Laboratory problem, discussion.
• 16 X 2014 (Th). RAM machines, simple programs.
• 23 X 2014 (Th). Introductory test. RAM/Turing machines equivalence, practical experience.
• 30 X 2014 (Th). Primitive recursive functions - examples.
• 20 XI 2014 (Th). Preparations to final test.
• January 2015 (time and place will be announced later, see Announcements). Preparations to final test.

### Laboratories, realization - fall 2014

Here. Students not speaking Polish are requested to send e-mail or meet me.

### 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 - fall 2012

• 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,
• 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.