This repository contains some exercises, examples and data structures from the book The Algorithm Design Manual. Everything was made using Swift 4.
To run the exercises open a terminal and execute the following command:
swift FILENAME.swift
Optionally, you can create a "Command utility" project in Xcode, add the files there and run the project.
Additionally, it contains some other popular problems, algorithms, and structures that came up frequently when I was reading the book. These additional items are listed here:
- Geometry: This section contains Geometry related problems and other useful structures used to solve this kind of problems. Some of these problems can be found in the book Programming Challenges: The Programming Contest Training Manual.
- BTree: Self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
- Insertion Sort: Sorting algorithm that is performed in O(n^2) runtime but has a simple implementation.
- Integer partitions: Given a positive integer n, generate all possible unique ways to represent n as a sum of positive integers.
- K-Subsets: Given an integer array of N elements, the task is to divide this array into K non-empty subsets such that the sum of elements in every subset is same. All elements of this array should be part of exactly one partition.
- Knapsack problem: Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
- Parentheses balance: Checks if an expression with parentheses is balanced.
- Set Partitions: Generates the all nonempty subsets from an array with the elements from 1 to n.
- Shellsort: Variation of Insertion Sort, the idea of shellSort is to allow an exchange of far items.
- Skip list: Data structure that allows fast search within an ordered sequence of elements. The search and insert operations take O(log n)
- Splay Tree: Binary search tree that is auto adjusted and has the property that recently accessed elements can be accessed quickly.
- Tournament Tree: Form of min (max) heap which is a complete binary tree. Every external node represents a player and internal node represents winner. In a tournament tree, every internal node contains winner and every leaf node contains one player.
Note: Many of the descriptions of the list were obtained from Geeks for Geeks