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

.obj: /* Exam */

2021-12-21T10:00:50Z

Exam

← Предыдущая версия		Версия от 10:00, 21 декабря 2021
Строка 39:		Строка 39:
	You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.		You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.

	We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom ~~(the link will appear here)~~.		We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom].

	[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)		[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)

.obj: /* Exam */

2021-12-20T06:29:49Z

Exam

← Предыдущая версия		Версия от 06:29, 20 декабря 2021
Строка 42:		Строка 42:

	[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)		[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)

			Here is the [https://www.dropbox.com/s/2bt00a3fy28xwsu/exam21_12_20.pdf?dl=0 exam].

	= Course Materials =		= Course Materials =

.obj: /* Course Materials */

2021-12-19T20:10:30Z

Course Materials

← Предыдущая версия		Версия от 20:10, 19 декабря 2021
Строка 57:		Строка 57:
	\|\| 07.09 \|\| Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples ([https://www.dropbox.com/s/wna14b7y7nmw3cq/tm.py?dl=0 one], [https://www.dropbox.com/s/wrl3mkeqslj3xtu/wsharpw.py?dl=0 two]). Time and space complexity. Complexity classes P, PSPACE, EXP. \|\| [https://www.dropbox.com/s/37eel2qayios6b3/prob_1.pdf?dl=0 Problem set 1]		\|\| 07.09 \|\| Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples ([https://www.dropbox.com/s/wna14b7y7nmw3cq/tm.py?dl=0 one], [https://www.dropbox.com/s/wrl3mkeqslj3xtu/wsharpw.py?dl=0 two]). Time and space complexity. Complexity classes P, PSPACE, EXP. \|\| [https://www.dropbox.com/s/37eel2qayios6b3/prob_1.pdf?dl=0 Problem set 1]
	\|-		\|-
	\|\| 14.09 \|\| Time and space hierarchy ~~theorem~~. Time and space constructible functions. \|\| [https://www.dropbox.com/s/ow4m1z8u8r211qs/prob_2.pdf?dl=0 Problem set 2]		\|\| 14.09 \|\| Time and space hierarchy theorems. Time and space constructible functions. \|\| [https://www.dropbox.com/s/ow4m1z8u8r211qs/prob_2.pdf?dl=0 Problem set 2]
	\|-		\|-
	\|\| 21.09 \|\| Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.		\|\| 21.09 \|\| Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.

.obj: /* Exam */

2021-12-19T19:39:49Z

Exam

← Предыдущая версия		Версия от 19:39, 19 декабря 2021
Строка 35:		Строка 35:
	The exam consists of 8 questions of the same level as the homework.		The exam consists of 8 questions of the same level as the homework.

	You may use all notes, books, and ~~do internet searches~~. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.		You may use all notes, books, and other reference materials. However, the solutions you submit must, of course, be your own. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.

	You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.		You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.

Bbauwens в 17:59, 18 декабря 2021

2021-12-18T17:59:21Z

← Предыдущая версия		Версия от 17:59, 18 декабря 2021
Строка 41:		Строка 41:
	We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).		We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).

	[https://youtu.be/sKYibeWX5LU Recording] of the ~~'''~~consultation~~'''~~ (with solutions of problems 11.7, 7.7 and 12.7)		[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)

	= Course Materials =		= Course Materials =

Bbauwens в 17:58, 18 декабря 2021

2021-12-18T17:58:32Z

← Предыдущая версия		Версия от 17:58, 18 декабря 2021
Строка 13:		Строка 13:
	Homework 3, deadline: <s>December 7</s> December 14, 14:00 <br>		Homework 3, deadline: <s>December 7</s> December 14, 14:00 <br>

	~~'''~~Colloquium: December 7, 14:40–17:40; December 8, 16:30–18:30~~'''~~ <br>		Colloquium: December 7, 14:40–17:40; December 8, 16:30–18:30 <br>
	[https://www.dropbox.com/s/lxyjm6b4xatl0pz/col.pdf?dl=0 Rules and questions]<br>		[https://www.dropbox.com/s/lxyjm6b4xatl0pz/col.pdf?dl=0 Rules and questions]<br>
	Choose your [https://docs.google.com/document/d/1OxiLVx_6LWIJlGP9qjQe1CuBH3BGjk4Q5drHc9r5CE0/ time].		Choose your [https://docs.google.com/document/d/1OxiLVx_6LWIJlGP9qjQe1CuBH3BGjk4Q5drHc9r5CE0/ time].
Строка 41:		Строка 41:
	We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).		We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).

	[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)		[https://youtu.be/sKYibeWX5LU Recording] of the '''consultation''' (with solutions of problems 11.7, 7.7 and 12.7)

	= Course Materials =		= Course Materials =

Bbauwens в 17:57, 18 декабря 2021

2021-12-18T17:57:20Z

← Предыдущая версия		Версия от 17:57, 18 декабря 2021
Строка 24:		Строка 24:
	Exam: 30%		Exam: 30%

	==Homework Grading==		== Homework Grading ==
	Some homework assignments contain extra problems. Let us call all other problems regular. The weight of each problem (whether regular or extra) in the overall homework grade is 8/''n'', where ''n'' is the total number of regular problems in all homework assignments. Partial credit is possible for some problems.		Some homework assignments contain extra problems. Let us call all other problems regular. The weight of each problem (whether regular or extra) in the overall homework grade is 8/''n'', where ''n'' is the total number of regular problems in all homework assignments. Partial credit is possible for some problems.

Строка 33:		Строка 33:
	December 20, 9:30–12:30, [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom]		December 20, 9:30–12:30, [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom]

	The exam consists of ~~7 or~~ 8 questions of the same level as the homework.		The exam consists of 8 questions of the same level as the homework.

	You may use all ~~course materials (seminar sheets~~, ~~Sipser's book~~, ~~etc)~~. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.		You may use all notes, books, and do internet searches. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.

	You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.		You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.

	We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).		We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).

			[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)

	= Course Materials =		= Course Materials =

.obj в 08:36, 16 декабря 2021

2021-12-16T08:36:54Z

← Предыдущая версия		Версия от 08:36, 16 декабря 2021
Строка 28:		Строка 28:

	If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.		If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.


	== Exam ==		== Exam ==

.obj в 08:35, 16 декабря 2021

2021-12-16T08:35:00Z

← Предыдущая версия		Версия от 08:35, 16 декабря 2021
Строка 28:		Строка 28:

	If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.		If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.


			== Exam ==

			December 20, 9:30–12:30, [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom]

			The exam consists of 7 or 8 questions of the same level as the homework.

			You may use all course materials (seminar sheets, Sipser's book, etc). You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.

			You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.

			We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via Zoom (the link will appear here).

	= Course Materials =		= Course Materials =

.obj: /* Course Materials */

2021-12-14T21:59:28Z

Course Materials

← Предыдущая версия		Версия от 21:59, 14 декабря 2021
Строка 69:		Строка 69:
	\|\| 07.12 \|\| Colloquium. \|\|		\|\| 07.12 \|\| Colloquium. \|\|
	\|-		\|-
	\|\| 14.12 \|\| Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance.		\|\| [https://www.dropbox.com/s/emvoow009xjvf5q/tc-14-clustering.pdf?dl=0 14.12] \|\| Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance.
	\|\| [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]		\|\| [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]
	\|}		\|}