Skip to content

README.md

Latest commit

 

History

History
31 lines (23 loc) · 3.01 KB

README.md

File metadata and controls

31 lines (23 loc) · 3.01 KB

Algorithms - Exercises

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.

Others

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:

  1. 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.
  2. BTree: Self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.
  3. Insertion Sort: Sorting algorithm that is performed in O(n^2) runtime but has a simple implementation.
  4. Integer partitions: Given a positive integer n, generate all possible unique ways to represent n as a sum of positive integers.
  5. 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.
  6. 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.
  7. Parentheses balance: Checks if an expression with parentheses is balanced.
  8. Set Partitions: Generates the all nonempty subsets from an array with the elements from 1 to n.
  9. Shellsort: Variation of Insertion Sort, the idea of shellSort is to allow an exchange of far items.
  10. Skip list: Data structure that allows fast search within an ordered sequence of elements. The search and insert operations take O(log n)
  11. Splay Tree: Binary search tree that is auto adjusted and has the property that recently accessed elements can be accessed quickly.
  12. 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