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

Материал из Public ATP Wiki
Перейти к навигации Перейти к поиску
← Предыдущая правка
 
(не показаны 4 промежуточные версии этого же участника)
Строка 9: Строка 9:
* TBA means "to be announced" -- wait till the class :)
* TBA means "to be announced" -- wait till the class :)
* Contest means programming contest; problem set means math problem set.
* 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
|}
|}


= Grading system =
= Grading system =
* 3 points for contests
* 3 points for contests
* 3 points for class activity
* 3 points for problem sets
* 3 points for tests
* 3 points for tests
* 2 points for attendance
* 2 points for attendance

Текущая версия от 14: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
Источник — https://wiki.atp-fivt.org/index.php?title=Data_Structures_and_Algorithms_2022&oldid=1356