Массив [Array]

[Все типы данных]

Рассматриваемые темы:
1. Что такое массив?
2. Как хранится массив в памяти компьютера?
3. Оценка сложности базовых операций

Абстрактные типы данных

По мотивам одноименной книги Станислава Окулова с тематическими задачами от Александра Шеня(2004).

* Массивы
* Матрицы
* Списки
  * Односвязные
  * Двусвязные
  * Кольцевые
* Стеки
* Очереди
* Множества
  * Системы непересекающихся множеств
  * Словарь
* Очереди с приоритетами
* Деревья
  * Двоичные кучи
  * Биномиальные кучи
  * Дерево Фенвика
  * Дерево отрезков
  * Двоичное дерево поиска
  * Декартово дерево
  * АВЛ - деревья
  * 2-3 деревья
  * Б – деревья
  * Красно-черные деревья

Алгоритм Джарвиса

Теория:   Wikipedia, Hardfire

Практика: Меньшиков – 5D [informatics.mccme.ru]

Визуализатор: rain.ifmo.ru [Java]

Реализация:
Алгоритм Джарвиса позволяет строить выпуклую оболочку на множестве заданных точек. Алгоритмическая сложность O(N*H), где N – общее количество точек, H – количество точек в выпуклой оболочке.

Плавная сортировка (Smooth_sort)

[Все сортировки]

Предварительные темы:
1. Пирамидальная сортировка
2. Битовые операции

Теория: На русском языке мне, к сожалению, не удалось найти ни одного материала по этой теме. Поэтому общее представление об алгоритме можно получить из англоязычного источника, например здесь.
Рекомендую обратить внимание на gif’ку, представленную в статье. Лично мне она очень понравилась).

Битовый операции

Рассмотрим ряд базовых задач на работу с битами числа. В качестве базового целочисленного типа будем использовать 32битный int.

Попрактиковаться можно здесь: задачи на битовые операции.

1. Обнулить последние i бит числа А

1. A>>=i;
2. A<<=i;

или

1. A &= (~0)<<i;

2. 2^n

1. A = 1<<n;