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

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Grading system)
(Class materials)
 
(не показано 7 промежуточных версий 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
+
| QuickSelect, deterministic QuickSort, LSD
| Sorting algorithms 2
+
| 01.11.2022<br />
| Contest TBA
 
| 25.10.2022
 
 
|-
 
|-
| 3.2
+
| Heaps (binary)
| Binary search
+
| rowspan="2" | Problem set 3 (deadline: 27.11)
| Contest TBA
 
| 27.10.2022
 
|-
 
| 4.1
 
| Segment trees
 
| Problem set & contest TBA
 
| 01.11.2022
 
|-
 
| 4.2
 
| Remembering Dijkstra
 
| Contest TBA
 
 
| 03.11.2022
 
| 03.11.2022
 
|-
 
|-
| 4.3
+
| Heaps (cont., binomial) + test 1
| Remembering Dijkstra 2
 
|
 
| 05.11.2022
 
|-
 
| 5.1
 
| Dynamic programming 1
 
| Problem set TBA
 
 
| 08.11.2022
 
| 08.11.2022
 
|-
 
|-
| 5.2.
+
| Hashing 1
| Dynamic programming 2
+
| rowspan="2" | Problem set 4 TBA (deadline: 01.11)
| Contest TBA
 
 
| 10.11.2022
 
| 10.11.2022
 
|-
 
|-
| 5.3
+
| Hashing 2
| Dynamic programming 3
+
| 15.11.2022
| Problem set TBA
 
| 12.11.2022
 
 
|-
 
|-
| 6.1
+
| Numerical algorithms: overview
| Test 1
 
 
|  
 
|  
| 15.11.2022
 
|-
 
| 6.2
 
| Hashing 1
 
| Problem set TBA
 
 
| 17.11.2022
 
| 17.11.2022
 
|-
 
|-
| 6.3<br />
+
| Amortized analysis
| Hashing 2
+
| rowspan="2" | Problem set 5 TBA (deadline: 05.12)
| Contest TBA
 
| 19.11.2022
 
|-
 
| 7.1<br />
 
| String algorithms 1
 
| TBA
 
 
| 22.11.2022
 
| 22.11.2022
 
|-
 
|-
| 7.2
+
| Segment trees, fractional cascading
| String algorithms 2
+
| 24.12.2022
| TBA
 
| 24.11.2022
 
 
|-
 
|-
| 7.3
+
| Test 2
| Graph algorithms 1
+
| Contest 3 TBA (deadline: 06.12)
| Contest TBA
 
| 26.11.2022
 
|-
 
| 8.1<br />
 
| Graph algorithms 2
 
| TBA
 
 
| 29.11.2022
 
| 29.11.2022
 
|-
 
|-
| 8.2
+
| Persistency, segment tree modifications<br />
| Test 2
 
 
|  
 
|  
 
| 01.12.2022
 
| 01.12.2022
 
|-
 
|-
| 8.3
+
| Fenwick tree
| Project presentations & zachet
+
|
 +
| 06.12.2022
 +
|-
 +
| Final "zachet"
 
|  
 
|  
| 03.12.2022
+
| 08.12.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