Wydział Matematyki i Nauk Informacyjnych
Politechnika Warszawska
prof. dr hab. inż. Władysław Homenda
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 Pspace, NPspace.
 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.
 30 XI 2018 (Th) Assessments of theory, 4.15 PM, room 216.
 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 nonwashable marker with the name of the course, names of teammates, date of submission.
Grading scheme:
 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 24 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).
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, coNPcomplete, NPI – definitions, inclusions, justifications,
 NPcomplete problems examples, Cook theorem with proof, lemma for proving NPcompleteness with proof,
 classes of problems with regard to space complexity: Pspace, 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: pizomorfizm, 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, coNP
 NPcomplete 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, AddisonWesley Publishing Company,
 Aho A,V, Hopcroft J,E, Ullman J,D, The design and Analysis of Computer Algorithms, AddisonWesley Publishing Company,
 Bovet P,B, Crescenzi P, Introduction to the theory of Complexity, Prentice Hall,
 Moret M,B, The Theory of Computation, AddisonWesley 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.