Data Structures and Algorithms 2022 — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎Grading system)
(→‎Class materials)
 
(не показано 9 промежуточных версий 2 участников)
Строка 5: Строка 5:
  
 
= Class materials =
 
= 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.
 +
* [https://drive.google.com/drive/folders/1cjYsKrjdV8OIxH5Aoc775emJDfwq8QDm?usp=share_link Google Drive]
  
 
{| class="wikitable"  
 
{| class="wikitable"  
 
|- style="font-weight:bold;"
 
|- style="font-weight:bold;"
−
! #
 
 
! Subject
 
! Subject
 
! Classwork / homework
 
! Classwork / homework
 
! Date
 
! Date
 
|-
 
|-
−
| 0
 
 
| Introduction
 
| Introduction
 
|  
 
|  
 
| 08.10.2022
 
| 08.10.2022
 
|-
 
|-
−
| 1.1
 
 
| Graph theory: representation
 
| Graph theory: representation
 
| See 1.2
 
| See 1.2
 
| 13.10.2022
 
| 13.10.2022
 
|-
 
|-
−
| 1.2
 
 
| 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
 
|-
 
|-
−
| 2.1<br />
 
 
| Remembering DFS<br />
 
| Remembering DFS<br />
−
| Contest TBA
+
| [https://contest.yandex.ru/contest/41542/enter Contest 2]<br />
 
| 18.10.2022
 
| 18.10.2022
 
|-
 
|-
−
| 2.2
 
 
| Asymptotics & master-theorem
 
| Asymptotics & master-theorem
−
| Problem set TBA
+
| Problem set 1 (deadline: 04.11)
 
| 20.10.2022
 
| 20.10.2022
 
|-
 
|-
−
| 2.3
 
 
| Sorting algorithms 1
 
| Sorting algorithms 1
−
| Problem set TBA
+
| rowspan="2" | Problem set 2 (deadline: 15.11)
−
| 22.10.2022
+
| 29.10.2022
−
|-
 
−
| 3.1
 
−
| Sorting algorithms 2
 
−
| Contest TBA
 
−
| 25.10.2022
 
−
|-
 
−
| 3.2
 
−
| Segment trees
 
−
| Problem set & contest TBA
 
−
| 27.10.2022
 
 
|-
 
|-
−
| 4.1
+
| QuickSelect, deterministic QuickSort, LSD
−
| Remembering Dijkstra
+
| 01.11.2022<br />
−
| Contest TBA
 
−
| 01.11.2022
 
 
|-
 
|-
−
| 4.2
+
| Heaps (binary)
−
| Dynamic programming 1
+
| rowspan="2" | Problem set 3 (deadline: 27.11)
−
| Problem set TBA
 
 
| 03.11.2022
 
| 03.11.2022
 
|-
 
|-
−
| 4.3
+
| Heaps (cont., binomial) + test 1
−
| Dynamic programming 2
 
−
| Contest TBA
 
−
| 05.11.2022
 
−
|-
 
−
| 5.1
 
−
| TBA
 
−
| TBA
 
 
| 08.11.2022
 
| 08.11.2022
 
|-
 
|-
−
| 5.2.
+
| Hashing 1
−
| TBA
+
| rowspan="2" | Problem set 4 TBA (deadline: 01.11)
−
| TBA
 
 
| 10.11.2022
 
| 10.11.2022
 
|-
 
|-
−
| 5.3
+
| Hashing 2
−
| TBA
 
−
| TBA
 
−
| 12.11.2022
 
−
|-
 
−
| 6.1<br />
 
−
| TBA
 
−
| TBA
 
 
| 15.11.2022
 
| 15.11.2022
 
|-
 
|-
−
| 6.2
+
| Numerical algorithms: overview
−
| TBA
+
|  
−
| TBA
 
 
| 17.11.2022
 
| 17.11.2022
 
|-
 
|-
−
| 7.1<br />
+
| Amortized analysis
−
| TBA
+
| rowspan="2" | Problem set 5 TBA (deadline: 05.12)
−
| TBA
 
 
| 22.11.2022
 
| 22.11.2022
 
|-
 
|-
−
| 7.2
+
| Segment trees, fractional cascading
−
| TBA
+
| 24.12.2022
−
| TBA
 
−
| 24.11.2022
 
−
|-
 
−
| 7.3
 
−
| TBA
 
−
| TBA
 
−
| 26.11.2022
 
 
|-
 
|-
−
| 8.1<br />
+
| Test 2
−
| TBA
+
| Contest 3 TBA (deadline: 06.12)
−
| TBA
 
 
| 29.11.2022
 
| 29.11.2022
 
|-
 
|-
−
| 8.2
+
| Persistency, segment tree modifications<br />
−
| TBA
+
|  
−
| TBA
 
 
| 01.12.2022
 
| 01.12.2022
 +
|-
 +
| Fenwick tree
 +
|
 +
| 06.12.2022
 +
|-
 +
| Final "zachet"
 +
|
 +
| 08.12.2022
 
|}
 
|}
  
 
= Grading system =
 
= Grading system =
−
* 5 points for contests
+
* 3 points for contests
−
* 5 points for problem sets
+
* 3 points for problem sets
 +
* 3 points for tests
 
* 2 points for attendance
 
* 2 points for attendance
 
* 3 points for "zachet" in the end of semester (optional)
 
* 3 points for "zachet" in the end of semester (optional)
 
* the final grade is calculated as a minimum of sum and 10
 
* 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
 
* project option: practical & uses algorithms from the course; the subject needs to be discussed with Ilya by 01.11.2022

Текущая версия на 17:55, 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.
  • Google Drive
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 24.12.2022
Test 2 Contest 3 TBA (deadline: 06.12) 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 problem sets
  • 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
Источник — «http://wiki.atp-fivt.org/index.php?title=Data_Structures_and_Algorithms_2022&oldid=1356»