Algorithm Types

Below are the list of categories into which various algorithm can be categorized:

1. Simple recursive algorithms
2. Backtracking algorithms
3. Divide and conquer algorithms
4. Dynamic programming algorithms
5. Greedy algorithms
6. Branch and Bound algorithms
7. Randomized algorithms

ArrayList or LinkedList ...??

ArrayList or LinkedList ...?? compares ArrayList and LinkedList

Lecture Series on Design & Analysis of Algorithms

Computer Sc - Design & Analysis of Algorithms
Lecture Series on Design & Analysis of Algorithms by Prof.Abhiram Ranade, Department of Computer Science Engineering,IIT Bombay.

Refcardz #08: Design Patterns

List of Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

Algorithms are a sequence of steps for accomplishing a task. We use complex algorithms in our day to day tasks for eg. searching in Google, sending emails, booking air tickets etc.

an example on insertion sort (Photo credit: Wikipedia)

Characteristics of algorithms
Performance (memory & CPU)
Simplicity

List of Algorithms

• Finding Maximum
• Order Statistics
• Matrix Multiplication
• Comparison
• Linear Search
  String searching algorithm (Photo credit: Wikipedia)
• Binary Search
• Selection Sort
• Insertion Sort
• Bubble Sort
  English: an example on bubble sort. (Photo credit: Wikipedia)
  English: Sorting a random list using bubble sort (Photo credit: Wikipedia)
  
  
• Heap Sort
• Merge Sort
• English: Sorting a random list using merge sort. (Photo credit: Wikipedia)
  English: an example on merge sort. (Photo credit: Wikipedia)
• Radix or Bucket Sort
• Random algorithms - improves the worst case performance
• Quick Sort
• Finding Median
• Hashing
• Fibonacci sequence
• Spanning Tree
• Shortest Path - finding the shortest path from one point to another.
• Djikstra's algorithm
• String Searching
• String Matching

NP-complete or NP-hard problem has no known good optimal solution. If someone finds an efficient algorithm for one NP-hard problem, then that algorithm would be applicable to all NP-hard problems. 

Related articles

• Big-O Misconceptions(ssp.impulsetrain.com)

  ---

• Algorithm Headache(mayoiengineer.wordpress.com)

  ---

• insertion sort vs bubble sort vs quicksort algorithm(stackoverflow.com)

  ---

• What's really so bad about bubble sort?(nicknash.me)

  ---

• bubble sort help(daniweb.com)

  ---

• Radix sort(daniweb.com)

  ---

• A simple C program for Insertion sort(depthgr8.wordpress.com)

  ---

• How to teach Algorithms ?(kintali.wordpress.com)

  ---

List of Design Patterns

LazyList-Iterator (Photo credit: propella)

• singleton
• iterator / enumerator
• decorator
• facade
• listener
• publisher-subscriber
• factory
  Factory Method pattern in LePUS3 (Photo credit: Wikipedia)
• abstract factory - A tutorial about abstract factory design pattern
  The Abstract Factory pattern illustration, UML diagram. (Photo credit: Wikipedia)
  Abstract Factory (Photo credit: Wikipedia)
• Model View Controller (MVC)
  English: This diagram depicts how the Model View Controller Architecture works. (Photo credit: Wikipedia)
  English: The model, view, and controller (MVC) pattern relative to the user. (Photo credit: Wikipedia)
  Deutsch: Model View Controller (Photo credit: Wikipedia)
• Inversion of Control (IoC)

Related articles

• Inversion of Control Containers and the Dependency Injection pattern(lchandara.wordpress.com)

  ---

• Abstract Factory Design Pattern Explained(javacodegeeks.com)

  ---

• IoC container solves a problem you might not have but it's a nice problem to have(devlicio.us)

  ---

• Answer by jalf for Does Functional Programming Replace GoF Design Patterns?(stackoverflow.com)

  ---

• Abstract factory pattern in java(howtodoinjava.com)

  ---

• Factory Design Pattern(javabydesign.blogspot.com)

  ---

• Design Best practices using Factory Method Pattern(javacodegeeks.com)

  ---

• A Modern Alternative to Abstract Factory Filtered Dependencies(architects.dzone.com)

  ---

• An explanation to Factory Design Pattern...!(daniweb.com)

  ---

• Do These Design Patterns Stand the Test of Time?: Abstract Factory(architects.dzone.com)

  ---

List of Data Structures

Below is the list of important data structures

• Simple Data Structures
• Primitive Data Types
• Boolean
• Numbers
• String
• Structures (structs)
• Points (x & y coordinates), Color (red, green, blue, alpha)
• Objects (Custom Data Types)
• Collections
• Arrays
• single -dimensional arrays
• multi-dimensional arrays
• two-dimensional arrays (rectangular), 
• three-dimensional arrays,
• and so on...
• Jagged arrays (ex. daily sales per month ) 
• Lists
• ArrayList (resizable, dynamic or mutable arrays)
• Vector
• Operations
• Appending (Push) - adding an element at the end
• Insertion / Add - adding in the middle at a specified index
• Removing (Pop) - deleting an element at the end
• Deletion - removing an element at a specified index
• Splice - (adding and removing)
• Search / Find / Contains - searching for an item and returning location
• Sort - ordering the data
• Linked List 
• Singly Linked List
• Definition: A data structure consisting of a group of nodes where each node is composed of data and a reference (or a link) to the next node in the sequence.
• Operations
• Insertion
• Deletion
• Find / Search
• Traversal
• Iterative
• Recursive
• Reversal
• Iterative
• Recursive
• Doubly Linked List
• Definition: A data structure consisting of a group of nodes where each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
• The two node links allow traversal of the list in either direction. While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.
• Operations
• Insertion
• Deletion
• Traversal
• Reverse Traversal
• Circular Linked List
• Abstract Data Type
• Queue - First In, First Out
• Examples - Job Queue
• Operations
• Enqueue - adding an element at Last
• Dequeue - removing an element from Front
• Stack - Last In, First Out
• Operations
• Push
• Pop
• Peek
• Priority Queue
• Double-ended Queue (Deque) - supports adding deletion from both ends
• Hash-Based Data Structures

hash table illustration, with three keys, funcbox, sparse range, no collisions, only the values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 3 -funcbox 1 -sparse 1 -keys 0 -values 1 -collisions 0 -links 0 -overflow SP (Photo credit: Wikipedia)

hash table illustration, with three keys, sparse range, buckets are links, collisions resolved by separate chaining, keys and values stored. Inspired on File: HASHTB32.svg and other similar images. Created with make-hash-table-figure -nkeys 5 -funcbox 0 -sparse 1 -keys 1 -values 1 -collisions 1 -links 1 -overflow LL (Photo credit: Wikipedia)

• Associative Arrays 
• Invariants 
• Unique Keys
• Operations
• Add
• Remove
• Hash Tables / Hash Map / Dictionaries
• create with an initial capacity
• Hash Collision
• separate chaining
• Set / HashSet
• unordered collection of objects
• No sequence
• No duplicates
• Fast lookup - for checking membership, not retrieval
• Operations
• add
• remove
• contains
• Tree
• Binary Tree

A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. (Photo credit: Wikipedia)

• Binary Search Tree 
• invariants
• no duplicates
• operations
• add
• delete
• find
• traverse
• pre-order
• in-order
• post-order
• Self Balancing Trees
• AVL Tree
• Red-Black Tree - (implementation of TreeMap in Java uses this)
• Scapegoat Trees
• Splay Trees
• Segment Tree (for min/max/sum range queries)
• Fenwick Tree (Binary Indexed Tree)
• Heap (Min Heap or Max Heap)

A method for implementing Double ended priority queue(DEPQ) (Photo credit: Wikipedia)

• Graph
• Directed Graph
• Undirected Graph
• Weighted Graph
• Trie
• Disjoint Set
• Bloom Filter
• Consistent Hash Ring
• Maps
• Ternary Search Trees
• B-Trees
• Graph

Related articles

• Singly Linked List class using Collection hierarchy C++(stackoverflow.com)

  ---

• Five Myths about Hash Tables(hughewilliams.com)

  ---

• Open Data Structures: an open content textbook(opendatastructures.org)

  ---

• Implementing a binary tree using linear linked lists(en.nerdaholyc.com)

  ---