The solutions should be submitted by e-mail to slkuznetsov@hse.ru; the deadline is Wednesday October 25, 19:00 Moscow time.
The exam will be checked on Wednesday, and the results will be put in the grading sheet. On Thursday (21:00 Moscow time), the grades will be transmitted to the study office, after that no changes will be possible.
The final exam is obligatory for all students enrolled in the course, no exceptions.
This is a written theoretical assignment. Deadline: October 15, 2023, AoE. Please submit by email to slkuznetsov@hse.ru (scan or high quality photo is fine).
Home Assignment #1
Boolean Logic. Checking satisfiability and finding satisfying assignments for 2-CNF.Formulation of the task (please read it carefully!)
Deadline: October 11, 2023 (strict!)
The preferable way of submitting the assignment is via GitHub Classroom:
Access the assignment via the invite link (https://classroom.github.com/a/xNemfNNW) and accept it.
Please use your real names!
This will create a repository for you, which includes the README file with the formulation of the tasks, and pre-configured autograding tests.
Submit your solution as boolean.py in this repository.
If all automated tests pass correctly, you will see the symbol of success () in your repository. Otherwise, it indicates failure (), and you might look inside, checking whether at least the satisfiabilty checking (first part of the task) works correctly.
Once you get , no further action is needed. The lecturer will see your success and properly grade HW#1 for you.
As a fallback, it is also possible to submit via e-mail to slkuznetsov@hse.ru. The same address may be used for asking questions, including problems with GitHub.
Previous Year: 2022
Videos of 2022 lectures and seminars (YouTube playlist).
The solutions should be submitted by e-mail to slkuznetsov@hse.ru; the deadline (strict!) is Wednesday October 26, 19:00 Moscow time.
The exam will be checked on Wednesday, and the results will be put in the grading sheet. On Thursday (evening), the grades will be transmitted to the study office, after that no changes will be possible.
The final exam is obligatory for all students enrolled in the course, no exceptions.
Grading Formula
Total = 0.5 · (HW1 + HW2 + HW3) + 0.5 · Exam
Maximal grades for home assignments: HW1 — 4, HW2 — 4, HW3 — 2 (giving 4+4+2=10).
The final exam is obligatory for all students enrolled in the course, no exceptions.
This is a written theoretical assignment. Deadline: Friday, October 14, AoE. Please submit by email to slkuznetsov@hse.ru (scan or high quality photo is fine).
Home Assignment #1
OBSOLETE!
Boolean Logic. Checking satisfiability and finding satisfying assignments for 2-CNF.Formulation of the task (please read it carefully!)
Deadline: October 12, AoE (strict!)
The preferable way of submitting the assignment is via GitHub Classroom:
Access the assignment via the invite link (https://classroom.github.com/a/AlaSr1mN) and accept it.
This will create a repository for you, which includes the README file with the formulation of the tasks, and pre-configured autograding tests.
If your name is not obviously readable from your GitHub nickname, please fill in this identification form.
Submit your solution as boolean.py in this repository.
If all automated tests pass correctly, you will see the symbol of success () in your repository. Otherwise, it indicates failure (), and you might look inside, checking whether at least the satisfiabilty checking (first part of the task) works correctly.
Once you get , no further action is needed. The lecturer will see your success and properly grade HW#1 for you.
As a fallback, it is also possible to submit via e-mail to slkuznetsov@hse.ru. The same address may be used for asking questions, including problems with GitHub.
2021
The information here can be used as a reference; the class of 2022 would be similar to that of 2021.
However, concrete links and dates are obsolete, do not rely on them!
Videos of 2021 lectures and seminars (YouTube playlist).
The solutions should be
submitted by e-mail to sk@mi-ras.ru; the deadline is Wednesday October 20, 13:00 Moscow time, and it is strict.
The exam will be checked on Wednesday, and the results will be put in the grading sheet. On Thursday (evening), the grades will be transmitted to the study office, after that no changes will be possible.
The final exam is obligatory for all students enrolled in the course, no exceptions.
Grading Formula
Total = 0.5 · (HW1 + HW2 + HW3) + 0.5 · Exam
Maximal grades for home assignments: HW1 — 4, HW2 — 4, HW3 — 2 (giving 4+4+2=10).
The final exam is obligatory for all students enrolled in the course, no exceptions.
Home Assignment #3: NetworkX and Social Network Analysis
This is a written theoretical assignment. Deadline: October 6, AoE. You may either bring your answers in written form to the lecture on Wednesday, October 6, or send them to sk@mi-ras.ru (scan or high quality photo is fine).
Home Assignment #1
Boolean Logic. Checking satisfiability and finding satisfying assignments for 2-CNF.Formulation of the task (please read it carefully!)
Deadline: October 5, AoE (strict!)
The preferable way of submitting the assignment is via GitHub Classroom:
Access the assignment via the invite link (https://classroom.github.com/a/ZRHmjSA-) and accept it.
This will create a repository for you, which includes the README file with the formulation of the tasks, and pre-configured autograding tests.
If your name is not obviously readable from your GitHub nickname, please fill in this identification form.
Submit your solution as boolean.py in this repository.
If all automated tests pass correctly, you will see the symbol of success () in your repository. Otherwise, it indicates failure (), and you might look inside, checking whether at least the satisfiabilty checking (first part of the task) works correctly.
Once you get , no further action is needed. The lecturer will see your success and properly grade HW#1 for you.
As a fallback, it is also possible to submit via e-mail to sk@mi-ras.ru. The same address may be used for asking questions, including problems with GitHub.
2020
The information below is outdated and may be used only for historical reference.
Final grade = 0.5·(Home assignments) + 0.5·(Exam).
Home assignments are graded out of 10: HW #1 out of 4, HW #2 out of 4, HW #3 out of 2.
Grading principles for home assignments are as follows. HW #1 and #3 are graded on a pass/fail basis: maximal grade, if the program works,
and zero, if it does not. A half of the maximal grade can be assigned if the assignment was submitted significantly after the deadline, or a correct solution was reached only after significant feedback from the teacher (that is, the original submission was incorrect). HW #2 is graded on a proportional basis: multiply the number of correctly solved tasks by 4/6 and round to the closest integer.
If a student gets 8, 9, or 10 as the mark for home assignments, and all assignments are submitted before
or on October 14, then the student is not obliged to pass the exam. In this case, the mark for home assignments is
considered as the final one.
The SNAP dataset called facebook_combined.txt
includes a union of 10 ego networks from Facebook. An ego network is a subgraph of the full friendship graph which includes a central node (ego) together with the vertices to which the ego is connected directly, and edges among them. Thus, each vertex in our dataset is either one of the 10 ego network centers, or is directly connected to (at least) one of them.
The task is as follows. Consider the following set of 11 vertices: 0, 107, 348, 414, 612, 686, 698, 1684, 1912, 3437, 3980. It is guaranteed that this set includes all 10 ego network centers, plus one extra vertex. The program should distinguish the added 11th vertex from the 10 ego network centers. As the answer, please provide the number of this additional vertex.
Notice: for testing, the nodes in the dataset can be renamed, in order to aviod hard-coding of the correct answer.
Deadline: Oct 14, 2020, 16:00 MSK.
HW #2: Theoretical Assignment
PDF
Deadline: Oct 16, 2020. (The students are encouraged to bring the solutions to the class of Oct 14, but submitting by email till Oct 16 is also fine.)
Erratum: there was a typo spotted and fixed in Problem 1. One should consider not the formula itself but rather its negation.
HW #1: Practice in Boolean Logic
This is a programming task. Choose one of the following two tasks and write a program
which solves it.
Given a Boolean formula, constructed from variables using
/\ (conjunction), \/ (disjunction), -> (implication), and ~ (negation),
translate it into Conjunctive Normal Form and into Disjunctive Normal Form.
Given a Boolean formula in 2-CNF, use the resolution method to determine whether it is satisfiable.
Clauses of the 2-CNF can be of one of the three forms: α \/ β, or α -> β,
or just α. Here α and β are literals (p or ~p, where p is a variable).
The CNF is presented in the usual notation, for example: (p -> q) /\ (~r \/ s) /\ (~q -> p)
Deadline: October 11, 2020 (23:59 MSK). Submissions by e-mail welcome.
Students are encouraged to use Python and PLY, but solutions in other programming languages are also OK.