discrete math in python: homework 2

Дед Мороз готовит подарки к Новому году. У Деда Мороза есть заводной
автомобиль, книжка–раскраска, кукла Таня, кулек конфет и еще n - 4
различных подарка. Каждый из них имеется в неограниченном количестве,
так что проблем вроде бы быть не должно. Однако Деду Морозу кажется, что
кулек конфет и заводной автомобиль — неравноценные подарки, поэтому к
кульку конфет он, скорее всего, добавит книжку–раскраску или что-то еще.
Дед Мороз уже составил k подарочных наборов, каждый из которых содержит
не более одного подарка каждого типа (т.е. в одном наборе — не более
одной куклы Тани). Принципы Деда Мороза не позволяют ему дарить одному
ребенку явно больше, чем другому, поэтому каждый из любых двух наборов
содержит какой-то подарок, которого нет в другом наборе. Дед Мороз
пытается составить еще один — (k + 1)-ый — подарочный набор,
согласующийся с его принципами, но у него не получается.

Напишите функцию another_gift(items, gifts), получающую на вход
множество (frozenset) типов подарков items и список (list) подарочных
наборов (frozenset) gifts, каждый из которых является подмножеством
items и не является подмножеством никакого другого набора из списка
gifts. Функция возвращает еще один такой подарочный набор, если таковой
существует, и None — в противном случае.

Например, вызов функции

another_gift(frozenset([1, 2, 3, 4]),
             [frozenset([1, 2]), frozenset([2, 3, 4])])

может вернуть frozenset([1, 3]), или frozenset([1, 4]), или
frozenset([1, 3, 4]). Вызов же функции

another_gift(frozenset([1, 2, 3]),
             [frozenset([1, 2]), frozenset([3])])

должен вернуть None.

Приведите и обоснуйте теоретическую оценку времени работы функции в
худшем случае.

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
bleh, update

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
class 2013-05-28

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
update homework 2

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
save progress

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
update prim's algorithm

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
update

this is the best commit message int he world

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
Submit the C version results

-3635748
tcc -run hse/2012-13_term_3/2013-02-28-b.c < input/edges500.txt  0.01s user 0.00s system 13% cpu 0.110 total

-4879008
tcc -run hse/2012-13_term_3/2013-02-28-b.c < input/edges500dense.txt 0.09s user 0.01s system 93% cpu 0.099 total

-8579081
tcc -run hse/2012-13_term_3/2013-02-28-b.c < input/edges1000.txt  0.03s user 0.01s system 77% cpu 0.042 total

-19868036
tcc -run hse/2012-13_term_3/2013-02-28-b.c < input/edges2000dense.txt 1.73s user 0.05s system 97% cpu 1.823 total

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
dont need this

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
python2.7 compat

line-profiler showed that most of the time is spent on line 47

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
Fix mst.py, include profiling data

The profiler is line_profiler (1.0b3) on python2.7

Timings:
  -3635748
  edges500.txt  0.06s user 0.01s system 99% cpu 0.065 total

  -4879008
  edges500dense.txt  0.33s user 0.01s system 99% cpu 0.335 total

  -8579081
  edges1000.txt  0.13s user 0.01s system 99% cpu 0.141 total

  -19868036
  edges2000dense.txt  6.40s user 0.10s system 99% cpu 6.505 total

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
blah

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
class 2013-06-04

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
update

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
Fix and update bst.Tree; rbtree.RBTree still WIP

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
move get_{grandparent,uncle} functions outside of RBTree class

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
Fix RBTree.insert, add time complexity test

'RBTree.insert_case\d()' functions are copied from wikipedia

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
update

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
hash tables

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>
Change file header

Signed-off-by: Andrew Tselischev <andrewtselischev@gmail.com>