fjbelchi / ekalgorithms

EKAlgorithms contains some well known CS algorithms & data structures.

EKAlgorithms

EKAlgorithms is a set of computer exercises implemented in Objective-C. Data structures, well known algorithms, CS curiosities, you name it!

Don't forget to watch the repository; Its content will be expanded and updated frequently.

Arrays and Lists

1. Index of maximum element in array.
2. Indexes of maximum and minimum elements simultaneously.
3. Find longest string in array of strings.
4. Find shortest string in array of strings.
5. Array reverse.
6. Intersection of two arrays.
7. Union of two arrays (with remove duplicates).
8. Union of two arrays (with remove duplicates) for some key.
9. Find duplicates.
10. Array with N unique/not unique random objects.
11. Check if array is sorted.
12. Array shuffle (Fisher-Yates).
13. Sum of array elements.
14. N of occurences of each element in array.

Search Algorithms

1. Linear search.
2. Binary search.

Sorting Algorithms

1. Bubble sort.
2. Shell sort.
3. Merge sort.
4. Quick sort.
5. Insertion sort.
6. Selection sort.
7. Radix Sort.
8. Partial selection sort.
9. Heap sort.

Selection Algorithms

1. Quickselect.

Strings

1. Palindrome or not.
2. String reverse.
3. Words count.
4. Permutations of string.
5. Occurrences of each character (a - z).
6. Count "needles" in a "haystack".
7. Random string.
8. Concatenation of two strings.
9. Find 1st occurrence of "needle" in a "haystack".
10. Last occurrence of "needle" in a "haystack".
11. Longest common subsequence.
12. Levenshtein distance.
13. KMP (Knuth–Morris–Pratt).

Numeric Algorithms

1. Sieve of Eratosthenes.
2. Great common divisor (GCD).
3. Least common multiple (LCM).
4. Factorial.
5. Fibonacci numbers (5 algos).
6. Sum of digits.
7. Binary to decimal conversion.
8. Decimal to binary conversion.
9. Fast exponentiation.
10. Number reverse.
11. Even/odd check.
12. Leap year check.
13. Armstrong number check.
14. Prime number check.
15. Find Nth prime.
16. Swap the value of two NSInteger pointers.
17. Square root using Newton-Raphson method.
18. Convert integer to another numeral system (2, 8, 12, 16).
19. Fast inverse square root.

Data Structures

1. Stack (LIFO).
2. Queue (FIFO).
3. Deque.
4. Linked list.
5. Graph:
   • DFS (depth-first search);
   • BFS (breadth-first search);
   • MST (minimum spanning tree - Prim's algorithm);
   • MST (minimum spanning tree - Kruskal's algorithm);
   • Shortest path (Dijkstra's algorithm);
   • Topsort.
6. Tree.
7. Binary tree:
   • Pre-order traversal;
   • In-order traversal;
   • Post-order traversal.
8. Binary search tree (BST).
9. AVL tree.
10. Binary heap.

Problems

1. Josephus Problem.
2. Modulo bias.

Geometry

1. Array of sorted locations according to a distance to a given location.
2. Cartesian quadrant selection algorithms

Recursion

1. Tower of Hanoi.

Contributions

Pull requests are welcome! But if you want to do a contribution, open an issue first.

Originally, the compiled exercises are for educational purposes only and have no intention of being the ultimate solution complexity-wise, but they do intend to be used by you as a starting point of a deeper study on algorithms and their optimization.

Important Note

The Foundation framework already includes tools and methods for most of the exercises contained here. Kudos to Apple on that! But... this. is. SPARTA! So lets get our hands dirty and try to implement cool CS stuff with minimal use of existing APIs.

Thanks!

Contributors

Special thanks to these guys for their contributions to the project's development:

• @stanislaw
• @vittoriom
• @AustinChou