Algorithms

Front 1

Bubble Sort - implement
O(n^2)

Back 1

public static void bubbleSort(int[] x) {
boolean doMore = true;
while (doMore) {
doMore = false; // assume this is last pass over array
for (int i=0; i<x.length-1; i++) {
if (x[i] > x[i+1]) {
// exchange elements
int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
doMore = true; // after an exchange, must look again
}
}
}
}

Front 2

Selection Sort
O(n^2)

Back 2

public static void selectionSort1(int[] x) {
for (int i=0; i<x.length-1; i++) {
for (int j=i+1; j<x.length; j++) {
if (x[i] > x[j]) {
//... Exchange elements
int temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
}
}

Front 3

Insertion Sort - implement
O(n^2)

Back 3

void insertionSort(int[] arr) {
int i, j, newValue;
for (i = 1; i < arr.length; i++) {
newValue = arr[i];
j = i;
while (j > 0 && arr[j - 1] > newValue) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = newValue;
}
}

Front 4

Merge Sort - implement
O(nlg(n))

Back 4

public static void mergeSort_srt(int array[],int lo, int n){
int low = lo;
int high = n;
if (low >= high) {
return;
}

int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high)) {
if (array[low] < array[start_high]) {
low++;
} else {
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--) {
array[k+1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}

Front 5

QuickSort - implement
O(nlg(n))

Back 5

function quicksort('array')
create empty lists 'less' and 'greater'
if length('array') ≤ 1
return 'array' // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater'))

Front 6

DFS - implement
O( | V | + | E | )

Back 6

1 procedure DFS(G,v):
2 label v as explored
3 for all edges e in G.incidentEdges(v) do
4 if edge e is unexplored then
5 w ← G.opposite(v,e)
6 if vertex w is unexplored then
7 label e as a discovery edge
8 recursively call DFS(G,w)
9 else
10 label e as a back edge

Front 7

BFS - implement
O( | V | + | E | ) = O(bd)

Back 7

1 procedure BFS(Graph,source):
2 create a queue Q
3 enqueue source onto Q
4 mark source
5 while Q is not empty:
6 dequeue an item from Q into v
7 for each edge e incident on v in Graph:
8 let w be the other end of e
9 if w is not marked:
10 mark w
11 enqueue w onto Q

Front 8

RandomizedSelect
O(n)

Back 8

RANDOMIZED-SELECT.A; p; r; i/
1 if p == r
2 return A[p]
3 q = RANDOMIZED-PARTITION(A, p, r)
4 k = q-p+1
5 if i == k // the pivot value is the answer
6 return A[q]
7 else if i < k
8 return RANDOMIZED-SELECT(A, p, q-1, i)
9 else return RANDOMIZED-SELECT(A, q+1, r, i-k)

Front 9

Hash Tables - implement

Back 9

public class HashTable
{
private LinkedList[] hashArr=new LinkedList[128];
public static int HFunc(int key)
{
return key%128;
}


public boolean Put(Val V)
{

int hashval = HFunc(V.getKey());
LinkedNode ln = new LinkedNode(V,null);
hashArr[hashval].Insert(ln);
System.out.println("Inserted!");
return true;
}

public boolean Find(Val V)
{
int hashval = HFunc(V.getKey());
if (hashArr[hashval].getInitial()!=null && hashArr[hashval].search(V)==true)
{
System.out.println("Found!!");
return true;
}
else
{
System.out.println("Not Found!!");
return false;
}

}
public boolean delete(Val v)
{
int hashval = HFunc(v.getKey());
if (hashArr[hashval].getInitial()!=null && hashArr[hashval].delete(v)==true)
{
System.out.println("Deleted!!");
return true;
}
else
{
System.out.println("Could not be found. How can it be deleted?");
return false;
}
}

public HashTable()
{
for(int i=0; i<hashArr.length;i++)
hashArr[i]=new LinkedList();
}

}

class Val
{
private int key;
private int val;
public int getKey()
{
return key;
}
public void setKey(int k)
{
this.key=k;
}
public int getVal()
{
return val;
}
public void setVal(int v)
{
this.val=v;
}
public Val(int key,int value)
{
this.key=key;
this.val=value;
}
public boolean equals(Val v1)
{
if (v1.getVal()==this.val)
{
//System.out.println("hello im here");
return true;
}
else
return false;
}
}

class LinkedNode
{
private LinkedNode next;
private Val obj;
public LinkedNode(Val v,LinkedNode next)
{
this.obj=v;
this.next=next;
}
public LinkedNode()
{
this.obj=null;
this.next=null;
}
public Val getObj()
{
return this.obj;
}
public void setNext(LinkedNode ln)
{
this.next = ln;
}

public LinkedNode getNext()
{
return this.next;
}
public boolean equals(LinkedNode ln1, LinkedNode ln2)
{
if (ln1.getObj().equals(ln2.getObj()))
{
return true;
}
else
return false;

}

}

class LinkedList
{
private LinkedNode initial;
public LinkedList()
{
this.initial=null;
}
public LinkedList(LinkedNode initial)
{
this.initial = initial;
}
public LinkedNode getInitial()
{
return this.initial;
}
public void Insert(LinkedNode ln)
{
LinkedNode temp = this.initial;
this.initial = ln;
ln.setNext(temp);
}
public boolean search(Val v)
{
if (this.initial==null)
return false;
else
{
LinkedNode temp = this.initial;
while (temp!=null)
{
//System.out.println("encountered one!");
if (temp.getObj().equals(v))
return true;
else
temp=temp.getNext();
}
return false;
}

}
public boolean delete(Val v)
{
if (this.initial==null)
return false;
else
{
LinkedNode prev = this.initial;
if (prev.getObj().equals(v))
{
this.initial = null;
return true;
}
else
{
LinkedNode temp = this.initial.getNext();
while (temp!=null)
{
if (temp.getObj().equals(v))
{
prev.setNext(temp.getNext());
return true;
}
else
{
prev=temp;
temp=temp.getNext();
}
}
return false;
}
}
}
}

Front 10

Linked list - implement

Back 10

class LinkedNode
{
private LinkedNode next;
private Val obj;
public LinkedNode(Val v,LinkedNode next)
{
this.obj=v;
this.next=next;
}
public LinkedNode()
{
this.obj=null;
this.next=null;
}
public Val getObj()
{
return this.obj;
}
public void setNext(LinkedNode ln)
{
this.next = ln;
}

public LinkedNode getNext()
{
return this.next;
}
public boolean equals(LinkedNode ln1, LinkedNode ln2)
{
if (ln1.getObj().equals(ln2.getObj()))
{
return true;
}
else
return false;

}

}

class LinkedList
{
private LinkedNode initial;
public LinkedList()
{
this.initial=null;
}
public LinkedList(LinkedNode initial)
{
this.initial = initial;
}
public LinkedNode getInitial()
{
return this.initial;
}
public void Insert(LinkedNode ln)
{
LinkedNode temp = this.initial;
this.initial = ln;
ln.setNext(temp);
}
public boolean search(Val v)
{
if (this.initial==null)
return false;
else
{
LinkedNode temp = this.initial;
while (temp!=null)
{
//System.out.println("encountered one!");
if (temp.getObj().equals(v))
return true;
else
temp=temp.getNext();
}
return false;
}

}
public boolean delete(Val v)
{
if (this.initial==null)
return false;
else
{
LinkedNode prev = this.initial;
if (prev.getObj().equals(v))
{
this.initial = null;
return true;
}
else
{
LinkedNode temp = this.initial.getNext();
while (temp!=null)
{
if (temp.getObj().equals(v))
{
prev.setNext(temp.getNext());
return true;
}
else
{
prev=temp;
temp=temp.getNext();
}
}
return false;
}
}
}
}

Front 11

Priority queue - implement

Back 11

public class PriorityQ {
// array in sorted order, from max at 0 to min at size-1
private int maxSize;

private long[] queArray;

private int nItems;

public PriorityQ(int s) {
maxSize = s;
queArray = new long[maxSize];
nItems = 0;
}

public void insert(long item) {
int i;

if (nItems == 0)
queArray[nItems++] = item; // insert at 0
else
{
for (i = nItems - 1; i >= 0; i--) // start at end,
{
if (item > queArray[i]) // if new item larger,
queArray[i + 1] = queArray[i]; // shift upward
else
// if smaller,
break; // done shifting
}
queArray[i + 1] = item; // insert it
nItems++;
} // end else (nItems > 0)
}

public long remove(){
return queArray[--nItems];
}

public long peekMin(){
return queArray[nItems - 1];
}

public boolean isEmpty(){
return (nItems == 0);
}

public boolean isFull(){
return (nItems == maxSize);
}
public static void main(String[] args) {
PriorityQ thePQ = new PriorityQ(5);
thePQ.insert(30);
thePQ.insert(50);
thePQ.insert(10);
thePQ.insert(40);
thePQ.insert(20);

while (!thePQ.isEmpty()) {
long item = thePQ.remove();
System.out.print(item + " "); // 10, 20, 30, 40, 50
}
System.out.println("");
}
}

Front 12

objects and pointers graph

Back 12

bubbles (vertices) use lines (arrows if directed) to point to other bubbles

Front 13

adjacency matrix

Back 13

array[v][v] of booleans

1 2 3 4 5 6 //y goes to x
1 t //so something goes from 2 to 1
2 t
3 t t
4 t
5 t t
6 t

Front 14

adjacency list

Back 14

each vertex has its own linked list of all edges that go out from that vertex

1 -> 4
2 -> 1
3 -> 2 -> 6
4 -> 5
5 -> 2 ->6
6 -> 3

If vertices are consecutive integers, use array of lists

If vertices have name (“Albany”), use hash table to map strings (or any object) to lists
key - vertex name
value - list

Front 15

Dijkstra - Implement

Back 15

Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded tentative distance of B, then overwrite that distance. Even though a neighbor has been examined, it is not marked as "visited" at this time, and it remains in the unvisited set.
When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex>
{
public final String name;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(String argName) { name = argName; }
public String toString() { return name; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}

}


class Edge
{
public final Vertex target;
public final double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}

public class Dijkstra
{
public static void computePaths(Vertex source)
{
source.minDistance = 0.;
PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
vertexQueue.add(source);

while (!vertexQueue.isEmpty()) {
Vertex u = vertexQueue.poll();

// Visit each edge exiting u
for (Edge e : u.adjacencies)
{
Vertex v = e.target;
double weight = e.weight;
double distanceThroughU = u.minDistance + weight;
if (distanceThroughU < v.minDistance) {
vertexQueue.remove(v);

v.minDistance = distanceThroughU ;
v.previous = u;
vertexQueue.add(v);
}
}
}
}

public static List<Vertex> getShortestPathTo(Vertex target)
{
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
path.add(vertex);

Collections.reverse(path);
return path;
}

public static void main(String[] args)
{
Vertex v0 = new Vertex("Harrisburg");
Vertex v1 = new Vertex("Baltimore");
Vertex v2 = new Vertex("Washington");
Vertex v3 = new Vertex("Philadelphia");
Vertex v4 = new Vertex("Binghamton");
Vertex v5 = new Vertex("Allentown");
Vertex v6 = new Vertex("New York");
v0.adjacencies = new Edge[]{ new Edge(v1, 79.83),
new Edge(v5, 81.15) };
v1.adjacencies = new Edge[]{ new Edge(v0, 79.75),
new Edge(v2, 39.42),
new Edge(v3, 103.00) };
v2.adjacencies = new Edge[]{ new Edge(v1, 38.65) };
v3.adjacencies = new Edge[]{ new Edge(v1, 102.53),
new Edge(v5, 61.44),
new Edge(v6, 96.79) };
v4.adjacencies = new Edge[]{ new Edge(v5, 133.04) };
v5.adjacencies = new Edge[]{ new Edge(v0, 81.77),
new Edge(v3, 62.05),
new Edge(v4, 134.47),
new Edge(v6, 91.63) };
v6.adjacencies = new Edge[]{ new Edge(v3, 97.24),
new Edge(v5, 87.94) };
Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

computePaths(v0);
for (Vertex v : vertices)
{
System.out.println("Distance to " + v + ": " + v.minDistance);
List<Vertex> path = getShortestPathTo(v);
System.out.println("Path: " + path);
}
}
}

Front 16

Floyd-Warshall - implement

Back 16

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]

import java.util.ArrayList;
import java.util.Arrays;
public class FloydWarshall {

int[][] D;
Node[][] P;

public void calcShortestPaths(Node[] nodes, Edge[] edges) {
D = initializeWeight(nodes, edges);
P = new Node[nodes.length][nodes.length];

for(int k=0; k<nodes.length; k++){
for(int i=0; i<nodes.length; i++){
for(int j=0; j<nodes.length; j++){
if(D[i][k] != Integer.MAX_VALUE && D[k][j] != Integer.MAX_VALUE && D[i][k]+D[k][j] < D[i][j]){
D[i][j] = D[i][k]+D[k][j];
P[i][j] = nodes[k];
}
}
}
}
}

public int getShortestDistance(Node source, Node target){
return D[source.name][target.name];
}

public ArrayList<Node> getShortestPath(Node source, Node target){
if(D[source.name][target.name] == Integer.MAX_VALUE){
return new ArrayList<Node>();
}
ArrayList<Node> path = getIntermediatePath(source, target);
path.add(0, source);
path.add(target);
return path;
}

private ArrayList<Node> getIntermediatePath(Node source, Node target){
if(D == null){
throw new IllegalArgumentException("Must call calcShortestPaths(...) before attempting to obtain a path.");
}
if(P[source.name][target.name] == null){
return new ArrayList<Node>();
}
ArrayList<Node> path = new ArrayList<Node>();
path.addAll(getIntermediatePath(source, P[source.name][target.name]));
path.add(P[source.name][target.name]);
path.addAll(getIntermediatePath(P[source.name][target.name], target));
return path;
}

private int[][] initializeWeight(Node[] nodes, Edge[] edges){
int[][] Weight = new int[nodes.length][nodes.length];
for(int i=0; i<nodes.length; i++){
Arrays.fill(Weight[i], Integer.MAX_VALUE);
}
for(Edge e : edges){
Weight[e.from.name][e.to.name] = e.weight;
Weight[e.to.name][e.from.name] = e.weight; // Distance between AB = Distance between BA
}
return Weight;
}
}

Front 17

Kruskal - implement

Back 17

The Kruskal Algorithm starts with a forest which consists of n trees.Each and everyone tree,consists only by one node and nothing else.In every step of the algorithm,two different trees of this forest are connected to a bigger tree.Therefore ,we keep having less and bigger trees in our forest until we end up in a tree which is the minimum genetic tree (m.g.t.) .In every step we choose the side with the least cost,which means that we are still under greedy policy.If the chosen side connects nodes which belong in the same tree the side is rejected,and not examined again because it could produce a circle which will destroy our tree.Either this side or the next one in order of least cost will connect nodes of different trees,and this we insert connecting two small trees into a bigger one.

create a forest F (a set of trees), where each vertex in the graph is a separate tree
create a set S containing all the edges in the graph
while S is nonempty and F is not yet spanning
remove an edge with minimum weight from S
if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
otherwise discard that edge.

Front 18

Prim - implement

Back 18

Informal
create a tree containing a single vertex, chosen arbitrarily from the graph
create a set containing all the edges in the graph
loop until every edge in the set connects two vertices in the tree
remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
add that edge to the tree
[edit]Technical


Prim's algorithm has many applications, such as in the generation of this maze, which applies Prim's algorithm to a randomly weighted grid graph.
If a graph is empty then we are done immediately. Thus, we assume otherwise.
The algorithm starts with a tree consisting of a single vertex, and continuously increases its size one edge at a time, until it spans all vertices.
Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
Repeat until Vnew = V:
Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)
Add v to Vnew, and {u, v} to Enew
Output: Vnew and Enew describe a minimal spanning tree

Front 19

Topological sorting

Back 19

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Front 20

binary search tree - implement

Back 20

class Node
{
public $parent = null;
public $left = null;
public $right = null;
public $data = null;

public function __construct($data)
{
$this->data = $data;
}

public function __toString()
{
return $this->data;
}
}

class BinaryTree
{
protected $_root = null;

protected function _insert(&$new, &$node)
{
if ($node == null) {
$node = $new;
return;
}

if ($new->data <= $node->data) {
if ($node->left == null) {
$node->left = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->left);
}
} else {
if ($node->right == null) {
$node->right = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->right);
}
}
}

protected function _search(&$target, &$node)
{
if ($target == $node) {
return 1;
} else if ($target->data > $node->data && isset($node->right)) {
return $this->_search($target, $node->right);
} else if ($target->data <= $node->data && isset($node->left)) {
return $this->_search($target, $node->left);
}

return 0;
}

public function insert($node)
{
$this->_insert($node, $this->_root);
}

public function search($item)
{
return $this->_search($item, $this->_root);
}
}

$a = new Node(3);
$b = new Node(2);
$c = new Node(4);
$d = new Node(7);
$e = new Node(6);

$t = new BinaryTree();

$t->insert($a);
$t->insert($b);
$t->insert($c);
$t->insert($d);
$t->insert($e);

echo $t->search($e);

Front 21

Inorder

Back 21

Touch the bottom during euler tour

Front 22

Preorder

Back 22

Touch the left during euler tour

Front 23

Postorder

Back 23

Touch the right during euler tour

Front 24

Backtracking

Back 24

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.[1][2][3]

Front 25

Greedy

Back 25

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.

- A candidate set, from which a solution is created
- A selection function, which chooses the best candidate to be added to the solution
- A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
- An objective function, which assigns a value to a solution, or a partial solution, and
- A solution function, which will indicate when we have discovered a complete solution

Traveling salesman

Front 26

Divide and conquer

Back 26

In computer science, divide and conquer (D&C) is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

1. Divide the given problem instance into
subproblems
2. Conquer the subproblems by solving them
recursively
3. Combine the solutions for the subproblems
to a solution for the original problem

Front 27

binary search - implement

Back 27

import java.util.Arrays;

public class BinarySearch {

// precondition: array a[] is sorted
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}

public static void main(String[] args) {
int[] whitelist = In.readInts(args[0]);

Arrays.sort(whitelist);

// read key; print if not in whitelist
while (!StdIn.isEmpty()) {
int key = StdIn.readInt();
if (rank(key, whitelist) == -1)
StdOut.println(key);
}
}
}

Front 28

Dynamic Programming

Back 28

Think about whether the opt program can be expressed as a sequence of decisions
Not “extending solution” but “solving smaller problem of the same kind”
//dynamic programming idea #1
check if same problem is being solved again. If so, keep a table and save time
Do not use recurrence relations to estimate time
Use “transcript” idea to estimate run time

Front 29

Combinatorics

Back 29

permutation no repeats order -
n!/(n-k)!
eg 10 candies, pick 3

permutations with repeats order-
n!/(n1! * n2! * ... *nk!)
eg we have 97 coders to go in 5 rooms of capacity 20, 20, 20, 20, 17
97!/(20!*20!*20!*20!*17!)

combinations no repeats no order
n!/(k!*(n-k)!)

combination with repeats no order
(n + k - 1)!/(k!*(n-1)!)

Front 30

Traveling salesman

Back 30

A traveling salesman has to travel through a bunch of cities, in such a way that the expenses on traveling are minimized. This is the infamous Traveling Salesman Problem (aka TSP) problem (formal defintion). It belongs to a family of problems, called NP-complete problem. It is conjectured that all those problems requires exponential time to solve them. In our case, this means that to find the optimal solution you have to go through all possible routes, and the numbers of routes increases exponential with the numbers of cities.

Front 31

Knapsack

Back 31

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
The problem often arises in resource allocation where there are financial constraints and is studied in fields such as combinatorics, computer science, complexity theory, cryptography and applied mathematics.

Front 32

AVL trees

Back 32

an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented.[1] In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Front 33

Processes

Back 33

In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.[1][2]
A computer program is a passive collection of instructions; a process is the actual execution of those instructions. Several processes may be associated with the same program; for example, opening up several instances of the same program often means more than one process is being executed.

Front 34

Threads

Back 34

a thread of execution is the smallest sequence of programmed instructions that can be managed independently by an operating system scheduler. A thread is a light-weight process. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process. Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources. In particular, the threads of a process share the latter's instructions (its code) and its context (the values that its variables reference at any given moment).

Front 35

Lock

Back 35

locks an object until unlock is called for it

Front 36

Mutex

Back 36

In computer science, mutual exclusion refers to the problem of ensuring that no two processes or threads (henceforth referred to only as processes) are in their critical section at the same time. Here, a critical section refers to a period of time when the process accesses a shared resource, such as shared memory. The problem of mutual exclusion was first identified and solved by Edsger W. Dijkstra in his seminal 1965 paper titled: Solution of a problem in concurrent programming control.[1][2]

Front 37

Semaphores

Back 37

a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming or multi user environment.
A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely (i.e., without race conditions) adjust that record as units are required or become free, and, if necessary, wait until a unit of the resource becomes available. Semaphores are a useful tool in the prevention of race conditions; however, their use is by no means a guarantee that a program is free from these problems. Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores (same functionality that mutexes have).

Front 38

Monitors

Back 38

In concurrent programming, a monitor is an object or module intended to be used safely by more than one thread. The defining characteristic of a monitor is that its methods are executed with mutual exclusion. That is, at each point in time, at most one thread may be executing any of its methods. This mutual exclusion greatly simplifies reasoning about the implementation of monitors compared to reasoning about parallel code that updates a data structure.
Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task. Monitors also have a mechanism for signaling other threads that such conditions have been met.

Front 39

Deadlock

Back 39

A condition that occurs when two processes are each waiting for the other to complete before proceeding. The result is that both processes hang. Deadlocks occur most commonly in multitasking and client/server environments. Ideally, the programs that are deadlocked, or the operating system, should resolve the deadlock, but this doesn't always happen.

Front 40

Livelock

Back 40

A condition that occurs when two or more processes continually change their state in response to changes in the other processes. The result is that none of the processes will complete. An analogy is when two people meet in a hallway and each tries to step around the other but they end up swaying from side to side getting in each other's way as they try to get out of the way.

Front 41

Context switching

Back 41

the computing process of storing and restoring the state (context) of a Process so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system. Context switches are usually computationally intensive and much of the design of operating systems is to optimize the use of context switches. A context switch can mean a register context switch, a task context switch, a thread context switch, or a process context switch. What constitutes the context is determined by the processor and the operating system. Switching from one process to another requires a certain amount of time for doing the administration - saving and loading registers and memory maps, updating various tables and lists etc.

Front 42

Discrete math counting

Back 42

Sum rule - do either task 1 or 2 but not both
m + n ways

Product rule - do task 1 and 2
m * n ways

Front 43

Singleton

Back 43

Ensure that only one instance of a class is created and Provide a global access point to the object.

Singleton pattern should be used when we must ensure that only one instance of a class is created and when the instance must be available through all the code. A special care should be taken in multithreading environments when multible threads must access the same resources throught the same singleton object.

Front 44

Factory(Simplified version of Factory Method) -

Back 44

Creates objects without exposing the instantiation logic to the client and Refers to the newly created object through a common interface.

Factory pattern should be used when: - a framework delegate the creation of objects derived from a common superclass to the factory - we need flexibility in adding new types of objects that must be created by the class

Front 45

Factory method

Back 45

Defines an interface for creating objects, but let subclasses to decide which class to instantiate and Refers to the newly created object through a common interface.

Factory Method pattern should be used when:
- a framework delegate the creation of objects derived from a common superclass to the factory
- the base factory class does not know what concrete classes will be required to create - delegates to its subclasses the creation of concrete objects
- factory subclasses subclasses are aware of the concrete classes that must be instantiated

Factory method pattern, compared to Factory pattern replace the factory with an abstract class and a set of concrete factories subclasses. The subclasses are responsible for creating concrete product objects; for factory method is possible adding new product classes without changing the abstract factory. The same result can be achieved for simplified factory pattern if reflection is used.

Front 46

Abstract Factory

Back 46

Offers the interface for creating a family of related objects, without explicitly specifying their classes.

Abstract Factory should be used when:
A system should be configured with one of multiple families of products
A system should be independent of how its products are created, composed and represented
Products from the same family should be used all together, products from different families ahould not be used togheter and this constraint must be ensured.
Only the product interfaces are revealed, the implementations remains hidden to the clients.

Front 47

Builder

Back 47

Defines an instance for creating an object but letting subclasses decide which class to instantiate and Allows a finer control over the construction process.

Front 48

Prototype

Back 48

Specify the kinds of objects to create using a prototypical instance, and create new objects by copying this prototype.

Front 49

Object Pool

Back 49

reuses and shares objects that are expensive to create..

Basically, we'll use an object pool whenever there are several clients who needs the same stateless resource which is expensive to create.