В Davis CS самый важный предмет, который вы изучаете, называется «Структуры данных». Я не могу придумать метафору, чтобы описать это, это просто… важно. Интервьюеры любят спрашивать об этом. Тесты кодирования предполагают, что вы это знаете. Кроме того, это последний урок по прополке на факультете, поэтому студенты очень довольны, когда проходят его.

Если я правильно помню, мы были очень взволнованы из-за Хао Чена. Мы слышали о нем следующие слухи; для вашего удобства я выделил жирным шрифтом те, которые оказались правдой, и выделил курсивом те, которые оказались неправдой:

  • Написание кода занимает 45 часов в неделю
  • Ваша оценка за домашнее задание может быть снижена из-за плохого стиля даже после того, как вы ее вернете
  • Он шутит на очень спорные темы

Одними из самых важных структур данных являются деревья, похожие на "универсальные генеалогические деревья". В генеалогическом дереве вы перечисляете людей как свои узлы и представляете иерархические отношения как ребра. В общем дереве можно представить много вещей. Нравится…

… пушки.

Хао Чен любил использовать подобные примеры. Наши вторая и третья программы (каким-то образом) сравнивали структуры данных с военными кампаниями Соединенных Штатов; его веб-сайт был размещен в домене под названием рак, а код был отправлен в репозиторий под названием метастаз. Он также сделал религиозное заявление, но я не хочу его включать.

Однако, когда я вспоминаю тот класс, я вспоминаю многое из того, что мы делали. Представьте себе задания по кодированию, когда у вас есть свобода решать, какие алгоритмы использовать, какие файлы создавать и какому стилю соответствовать. Представьте себе, что 15 человек впервые встречаются друг с другом, чтобы обсудить дизайн программы и общие концепции, но не код. Представьте себе 100 человек, помогающих друг другу на странице в Facebook, и репетиторов, которые работают круглосуточно бесплатно. Это было 60.

Конечно, какой была бы история без капельки паники?

Дата — 25 февраля 2014 года. Я чувствую себя довольно усталым и выбитым из колеи, но в 23:30 Gradebot поднимается. Мы ждали этого месяц… мы писали программы, и теперь мы можем их протестировать. Я отправляю запрос на ключ, и он не приходит до 4 утра. Даже сейчас я понимаю, что так и не научился пользоваться Git.

Плюсы Gradebot:

  • Вы сразу получаете оценку
  • Вы можете отправить столько раз, сколько хотите, до крайнего срока
  • Есть хорошая система антиплагаризма
  • Вы можете соревноваться с людьми, но это анонимно (если только вы не один из тех хромых людей, которые использовали ваше настоящее имя в качестве псевдонима).

Минусы Gradebot:

  • Потребовалось вечность, чтобы настроить их конец
  • Ушло целое утро, чтобы понять, как использовать
  • Третьей пули нет. Gradebot был потрясающим
  • О, подождите, да есть. Иногда зависал

Наша первая программа многим понравилась, но не мне. Если мне никогда не нравилось решать судоку вручную, какого черта мне писать программу для этого? Опять же, возможно, мне просто не нравилась эта проблема из-за того, что я пытался ее решить глупо.

Привет Джону за исправление ошибки в Square.cpp после семи часов, когда он просматривал все, кроме Square.cpp, потому что я сказал ему, что, по крайней мере, Square.cpp гарантированно не содержит ошибок.

Оказывается, у меня была одна переменная с именем SquareLocked и другая с именем SquareIsLocked, и предполагалось, что они обе имеют одно и то же имя.

Идем дальше…

Во второй программе нас попросили создать остовное дерево с минимальной стоимостью. Это может показаться скучным, если вы не разбираетесь в технике или не интересуетесь теорией графов, но позвольте мне посмотреть, смогу ли я сделать это правильно:

Задание, по словам Хао Чена: у нас есть города и дороги в какой-то стране, которую мы вторглись, но мы полностью уничтожили все дороги с помощью бомб. Мы получили госгрант на ремонт дорог, но хотим сделать это с наименьшими затратами. На изображении ниже вы увидите тот же график после того, как мы разрушили вышеупомянутые дороги (понимаете, почему это вызвало споры??).

Нам нужно остовное дерево с минимальной стоимостью: что-то, что соединяет города вместе, не образуя цикла. Я показал это двум друзьям на собрании Circle K, и они сказали, что это звучит очень сложно. Фактически…

Это очень просто, благодаря алгоритму! В жадном алгоритме вы делаете локально оптимальныйвыбор — другими словами, каждое ваше решение — это то, что кажется правильным в данный момент. С помощью алгоритма Крускала вы просто добавляете ребра от наименьшего к наибольшему (если вы не создаете цикл), пока не создадите свой MST. Было доказано, что это глобально оптимально и тот случай, когда жадный алгоритм работает идеально.

Так что это была легкая часть. Сложные части были:

  • Понимание того, что использовать ограниченные массивы было проще, чем векторы, из-за ограничений присваивания, о которых я не хочу писать
  • Выбор между сортировкой кучи и быстрой сортировкой, потому что никто еще не знал, что это за две вещи
  • Тестовые примеры, в которых использовались тысячи входных данных, чтобы сократить время ожидания программы.
  • Утечки памяти

Тем временем мы застряли в UHP. Наша команда потратила около двух часов на съемку видео и еще несколько часов на его монтаж, но это казалось странным давать всем. Я взял интервью у профессора о его работе над более эффективным освещением, и я на самом деле подумал, что это действительно круто, но я бы хотел, чтобы из этого получилось что-то большее. Я прошел курс из двух частей по категоризации с удивительно объемной книгой, которая до сих пор стоит у меня на полке. Я мало что помню, но мы сделали «Путеводитель по местам для учебы в Дэвисе». Пожалуйста, погуглите, скачайте и обратите внимание на то, что на нем мое имя. Вы.

В любом случае, я чувствую, что часть этой истории отсутствует…

Ах да, задание №3. Давайте рассмотрим это быстро.

У нас было всего несколько недель, чтобы сделать это, и это было, наверное, самое сложное интуитивно, и если вам не нравились указатели, то это была не ваша программа. Приятно то, что тестовые случаи были нестрогими, и мы участвовали в них друг с другом.

Я мало что помню о коде, но помню, как проделывал его части с двумя друзьями, кофе и кучей блокнота. Я не помню, как я спроектировал файловую систему, но я помню, как один из моих соседей по дому не спал со мной далеко за полночь, чтобы предложить помощь, а другой сосед по дому сказал разбудить его, если нам что-нибудь понадобится. Я помню, как некоторые люди думали, что получить 100 во всем было легко, но для меня это было моим самым большим достижением.

Видите этот график? Это статистика. Я только что сделал то, что сделали около 60 других людей, но это цифры. Чего цифры не говорят, так это того, сколько студенты сделали, чтобы помочь друг другу добиться успеха, и сколько DCSC сделал (и продолжает делать) для отдела.

Я знаю, что прошло много времени с тех пор, как закончились занятия, и на сегодняшний день прошел семестр с тех пор, как я закончила.

Я просто хотел это запомнить.