Theory of Computation 2023 - История изменений

Bauwens в 14:53, 19 марта 2024

2024-03-19T14:53:22Z

← Предыдущая версия		Версия от 14:53, 19 марта 2024
Строка 71:		Строка 71:
	\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]		\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]
	\|-		\|-
	\|\| 12.03 \|\| FPT algorithms ~~for~~ feedback vertex ~~set and~~ k-path problem, dynamic programming \|\| [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]		\|\| 12.03 \|\| techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) \|\| [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]
	\|-		\|-
	\|\| 19.03 \|\| linear programming kernel for vertex cover, tree decompositions, hardness from ETH (exponential time hypothesis) \|\| [https://www.dropbox.com/scl/fi/pfn4pt04pko4er8mkp988/prob_p3.pdf?rlkey=ruyy67173lipbu33by31117tf&dl=0 problem list 16]		\|\| 19.03 \|\| linear programming kernel for vertex cover, tree decompositions, hardness from ETH (exponential time hypothesis) \|\| [https://www.dropbox.com/scl/fi/pfn4pt04pko4er8mkp988/prob_p3.pdf?rlkey=ruyy67173lipbu33by31117tf&dl=0 problem list 16]

Bauwens в 14:51, 19 марта 2024

2024-03-19T14:51:45Z

← Предыдущая версия		Версия от 14:51, 19 марта 2024
Строка 71:		Строка 71:
	\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]		\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]
	\|-		\|-
	\|\| 12.03 \|\| FPT algorithms for feedback vertex set and k-path problem, ~~linear~~ programming ~~kernel for vertex cover,~~ \|\| [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]		\|\| 12.03 \|\| FPT algorithms for feedback vertex set and k-path problem, dynamic programming \|\| [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]
	\|-		\|-
	\|\| 19.03 \|\| ~~W[1] and W[2]-~~hardness~~, lower bounds using the~~ exponential time hypothesis~~. (Another programming task will appear here.~~)\|\|		\|\| 19.03 \|\| linear programming kernel for vertex cover, tree decompositions, hardness from ETH (exponential time hypothesis) \|\| [https://www.dropbox.com/scl/fi/pfn4pt04pko4er8mkp988/prob_p3.pdf?rlkey=ruyy67173lipbu33by31117tf&dl=0 problem list 16]
	\|}		\|}

Bauwens в 11:56, 18 марта 2024

2024-03-18T11:56:52Z

← Предыдущая версия		Версия от 11:56, 18 марта 2024
Строка 82:		Строка 82:

	During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.		During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.

			There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.

	Deadline March 31st, 23h59.		Deadline March 31st, 23h59.

	~~There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.~~

	<!-- The task is to understand a theoretical paper better by either		<!-- The task is to understand a theoretical paper better by either

Bauwens в 11:56, 18 марта 2024

2024-03-18T11:56:14Z

← Предыдущая версия		Версия от 11:56, 18 марта 2024
Строка 82:		Строка 82:

	During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.		During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.

			Deadline March 31st, 23h59.

	There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.		There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.

Bauwens в 11:53, 18 марта 2024

2024-03-18T11:53:37Z

← Предыдущая версия		Версия от 11:53, 18 марта 2024
Строка 13:		Строка 13:

	Note: for PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2024.		Note: for PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2024.


	~~= Colloquium and exam =~~

	~~Colloquium: on 12.12 or 19.12 at the time and place of the lecture+seminar, you can choose your time.~~

	~~[https://www.dropbox.com/scl/fi/srv4bitahhdzcrd0vm0pr/col.pdf?rlkey=25tt9v6du6wa90tg4pn0sdn0u&dl=0 Rules and questions.] (Update 11.12 question 1 of part 2.)~~

	Exam: December 27th, 10h -- 13h, room M203. Copies of Sipser's book, Arora&Barak, Mertens&Moore, chapts 1 and 2 of Roughgarden will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam].


	~~= Homeworks =~~

	Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in [https://classroom.google.com/c/NjIwOTk0NTM2NzE5?cjc=l4uhnyi google classrooms], code l4uhnyi. [https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results]. For questions about grading, contact [https://t.me/ivanashev Yaroslav Ivanashev].

	~~Tasks are in the seminar sheets.~~
	~~Problem lists 1 and 2 on 19.09,~~
	~~lists 3 and 4 on 03.10,~~
	~~lists 5 and 6 on 17.10,~~
	~~lists 7 and 8 on 07.11,~~
	~~lists 9 and 10 on 21.11,~~
	~~lists 11 and 12 on 05.12.~~


Строка 156:		Строка 134:

	Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.		Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.



			= Colloquium and exam =

			Colloquium: on 12.12 or 19.12 at the time and place of the lecture+seminar, you can choose your time.

			[https://www.dropbox.com/scl/fi/srv4bitahhdzcrd0vm0pr/col.pdf?rlkey=25tt9v6du6wa90tg4pn0sdn0u&dl=0 Rules and questions.] (Update 11.12 question 1 of part 2.)

			Exam: December 27th, 10h -- 13h, room M203. Copies of Sipser's book, Arora&Barak, Mertens&Moore, chapts 1 and 2 of Roughgarden will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam].


			= Homeworks =

			Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in [https://classroom.google.com/c/NjIwOTk0NTM2NzE5?cjc=l4uhnyi google classrooms], code l4uhnyi. [https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results]. For questions about grading, contact [https://t.me/ivanashev Yaroslav Ivanashev].

			Tasks are in the seminar sheets.
			Problem lists 1 and 2 on 19.09,
			lists 3 and 4 on 03.10,
			lists 5 and 6 on 17.10,
			lists 7 and 8 on 07.11,
			lists 9 and 10 on 21.11,
			lists 11 and 12 on 05.12.

Bauwens в 11:52, 18 марта 2024

2024-03-18T11:52:04Z

← Предыдущая версия		Версия от 11:52, 18 марта 2024
Строка 103:		Строка 103:
	= Project (for PI students) =		= Project (for PI students) =

	During the 3rd module Januari till March ~~2023~~ there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.		During the 3rd module Januari till March 2024 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.

	There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.		There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.

Bauwens в 11:51, 18 марта 2024

2024-03-18T11:51:41Z

← Предыдущая версия		Версия от 11:51, 18 марта 2024
Строка 99:		Строка 99:

	[https://www.youtube.com/playlist?list=PL8EKo81hBCTGfNPpZlIe7USiEPpZGYDte Recordings]		[https://www.youtube.com/playlist?list=PL8EKo81hBCTGfNPpZlIe7USiEPpZGYDte Recordings]


	= Project (for PI students) =		= Project (for PI students) =

	During the 3rd module Januari till March 2023 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.		During the 3rd module Januari till March 2023 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.

			There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.

	<!-- The task is to understand a theoretical paper better by either		<!-- The task is to understand a theoretical paper better by either

Bauwens в 11:49, 18 марта 2024

2024-03-18T11:49:26Z

← Предыдущая версия		Версия от 11:49, 18 марта 2024
Строка 89:		Строка 89:
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
	! ~~Rec~~ !! Software engineering: parameterized complexity !! Problem list		! Date !! Software engineering: parameterized complexity !! Problem list
	\|-		\|-
	\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]		\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]
Строка 98:		Строка 98:
	\|}		\|}

			[https://www.youtube.com/playlist?list=PL8EKo81hBCTGfNPpZlIe7USiEPpZGYDte Recordings]

	= Project (for PI students) =		= Project (for PI students) =

Bauwens в 16:43, 12 марта 2024

2024-03-12T16:43:16Z

← Предыдущая версия		Версия от 16:43, 12 марта 2024
Строка 93:		Строка 93:
	\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]		\|\| 05.03 \|\| The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. \|\| [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]
	\|-		\|-
	\|\| 12.03 \|\| FPT algorithms for feedback vertex set and k-path problem, linear programming kernel for vertex cover, \|\|		\|\| 12.03 \|\| FPT algorithms for feedback vertex set and k-path problem, linear programming kernel for vertex cover, \|\| [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]
	\|-		\|-
	\|\| 19.03 \|\| W[1] and W[2]-hardness, lower bounds using the exponential time hypothesis. (Another programming task will appear here.)\|\|		\|\| 19.03 \|\| W[1] and W[2]-hardness, lower bounds using the exponential time hypothesis. (Another programming task will appear here.)\|\|

Bauwens в 16:41, 6 марта 2024

2024-03-06T16:41:16Z

← Предыдущая версия		Версия от 16:41, 6 марта 2024
Строка 12:		Строка 12:
	[https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results].		[https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results].

	Note: for PI students the course is called ``computational complexity'' and has a 2nd part in Febr--March 2024.		Note: for PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2024.