Data Structures and Algorithms 2022 — различия между версиями
Izaharov (обсуждение | вклад) (→Class materials) |
Izaharov (обсуждение | вклад) (→Class materials) |
||
| Строка 12: | Строка 12: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- style="font-weight:bold;" | |- style="font-weight:bold;" | ||
| − | |||
! Subject | ! Subject | ||
! Classwork / homework | ! Classwork / homework | ||
! Date | ! Date | ||
|- | |- | ||
| − | |||
| Introduction | | Introduction | ||
| | | | ||
| 08.10.2022 | | 08.10.2022 | ||
|- | |- | ||
| − | |||
| Graph theory: representation | | Graph theory: representation | ||
| See 1.2 | | See 1.2 | ||
| 13.10.2022 | | 13.10.2022 | ||
|- | |- | ||
| − | |||
| Remembering BFS<br /> | | Remembering BFS<br /> | ||
| [https://contest.yandex.ru/contest/41169/enter Contest 1]<br /> | | [https://contest.yandex.ru/contest/41169/enter Contest 1]<br /> | ||
| 15.10.2022 | | 15.10.2022 | ||
|- | |- | ||
| − | |||
| Remembering DFS<br /> | | Remembering DFS<br /> | ||
| − | | Contest | + | | [https://contest.yandex.ru/contest/41542/enter Contest 2]<br /> |
| 18.10.2022 | | 18.10.2022 | ||
|- | |- | ||
| − | |||
| Asymptotics & master-theorem | | Asymptotics & master-theorem | ||
| − | | Problem set | + | | Problem set 1 (deadline: 04.11) |
| 20.10.2022 | | 20.10.2022 | ||
|- | |- | ||
| − | |||
| Sorting algorithms 1 | | Sorting algorithms 1 | ||
| − | | Problem set | + | | rowspan="2" | Problem set 2 (deadline: 15.11) |
| − | | | + | | 29.10.2022 |
|- | |- | ||
| − | | | + | | QuickSelect, deterministic QuickSort, LSD |
| − | + | | 01.11.2022<br /> | |
| − | |||
| − | | | ||
|- | |- | ||
| − | | | + | | Heaps (binary) |
| − | | | + | | rowspan="2" | Problem set 3 (deadline: 27.11) |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | | Problem set | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 03.11.2022 | | 03.11.2022 | ||
|- | |- | ||
| − | | | + | | Heaps (cont., binomial) + test 1 |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 08.11.2022 | | 08.11.2022 | ||
|- | |- | ||
| − | | | + | | Hashing 1 |
| − | | | + | | rowspan="2" | Problem set 4 TBA (deadline: 01.11) |
| − | | | ||
| 10.11.2022 | | 10.11.2022 | ||
|- | |- | ||
| − | | | + | | Hashing 2 |
| − | | | + | | 15.11.2022 |
| − | |||
| − | |||
|- | |- | ||
| − | | | + | | Numerical algorithms: overview |
| − | |||
| | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 17.11.2022 | | 17.11.2022 | ||
|- | |- | ||
| − | | | + | | Amortized analysis |
| − | | | + | | rowspan="2" | Problem set 5 TBA (deadline: 05.12) |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| 22.11.2022 | | 22.11.2022 | ||
|- | |- | ||
| − | | | + | | Segment trees, fractional cascading |
| − | | | + | | |
| − | |||
| − | |||
|- | |- | ||
| − | | | + | | Test 2 |
| − | + | | | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | | | ||
| 29.11.2022 | | 29.11.2022 | ||
|- | |- | ||
| − | | | + | | Persistency, segment tree modifications<br /> |
| − | |||
| | | | ||
| 01.12.2022 | | 01.12.2022 | ||
|- | |- | ||
| − | | | + | | Fenwick tree |
| − | | | + | | |
| + | | 06.12.2022 | ||
| + | |- | ||
| + | | Final "zachet" | ||
| | | | ||
| − | | | + | | 08.12.2022 |
|} | |} | ||
Версия 16:04, 14 ноября 2022
General Info
- 2nd Semester
- Grading system: check below
- all inquiries to @ilya101010
Class materials
- Classwork/homework deadline is in two weeks after the class.
- TBA means "to be announced" -- wait till the class :)
- Contest means programming contest; problem set means math problem set.
| Subject | Classwork / homework | Date |
|---|---|---|
| Introduction | 08.10.2022 | |
| Graph theory: representation | See 1.2 | 13.10.2022 |
| Remembering BFS |
Contest 1 |
15.10.2022 |
| Remembering DFS |
Contest 2 |
18.10.2022 |
| Asymptotics & master-theorem | Problem set 1 (deadline: 04.11) | 20.10.2022 |
| Sorting algorithms 1 | Problem set 2 (deadline: 15.11) | 29.10.2022 |
| QuickSelect, deterministic QuickSort, LSD | 01.11.2022 | |
| Heaps (binary) | Problem set 3 (deadline: 27.11) | 03.11.2022 |
| Heaps (cont., binomial) + test 1 | 08.11.2022 | |
| Hashing 1 | Problem set 4 TBA (deadline: 01.11) | 10.11.2022 |
| Hashing 2 | 15.11.2022 | |
| Numerical algorithms: overview | 17.11.2022 | |
| Amortized analysis | Problem set 5 TBA (deadline: 05.12) | 22.11.2022 |
| Segment trees, fractional cascading | ||
| Test 2 | 29.11.2022 | |
| Persistency, segment tree modifications |
01.12.2022 | |
| Fenwick tree | 06.12.2022 | |
| Final "zachet" | 08.12.2022 |
Grading system
- 3 points for contests
- 3 points for class activity
- 3 points for tests
- 2 points for attendance
- 3 points for "zachet" in the end of semester (optional)
- the final grade is calculated as a minimum of sum and 10
- project option: practical & uses algorithms from the course; the subject needs to be discussed with Ilya by 01.11.2022
