# Programming Flashcards

change bases

repeatably // by new base until 0, taking modulo and appending it to back of string each time

negatives should be abs and then “-“ inserted at front before return

//

floor division

DFS

Mark the current vertex as being visited.

Explore each adjacent vertex that is not included in the visited set.

def dfs(graph, start): visited, stack = set(), [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) stack.extend(graph[vertex] - visited) return visited

BFS

Explore first in queue not just adjacent

First path is one of the shortest (if path cost is number of edges)

def bfs(graph, start): visited, queue = set(), [start] while queue: vertex = queue.pop(0) if vertex not in visited: visited.add(vertex) queue.extend(graph[vertex] - visited) return visited

Dijsktra

Make visited dict - node:dist with start initialized to dist 0

Make path dict

Make set of all nodes

While items in set

Find minimum node in visited

If no min node, break done

Remove min node from set of all nodes

Set current weight to min node dist

For all neighbors of min node

Weight = current weight + weight of this edge

If neighbor not in visited OR weight < visited[edge]

Visited[neighbir] = weight

Path[neighbir] = minimum node

def dijsktra(graph, initial): visited = {initial: 0} path = {}

nodes = set(graph.nodes)

while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node] < visited[min_node]: min_node = node

if min_node is None: break nodes.remove(min_node) current_weight = visited[min_node] for edge in graph.edges[min_node]: weight = current_weight + graph.distance[(min_node, edge)] if edge not in visited or weight < visited[edge]: visited[edge] = weight path[edge] = min_node

return visited, path

DFS with goal node

def dfs_paths(graph, start, goal): stack = [(start, [start])] while stack: (vertex, path) = stack.pop() for next in graph[vertex] - set(path): if next == goal: yield path + [next] else: stack.append((next, path + [next]))

BFS with goal node

def bfs_paths(graph, start, goal): queue = [(start, [start])] while queue: (vertex, path) = queue.pop(0) for next in graph[vertex] - set(path): if next == goal: yield path + [next] else: queue.append((next, path + [next]))

Shortest path BFS

def shortest_path(graph, start, goal): try: return next(bfs_paths(graph, start, goal)) except StopIteration: return None

Permutations any list

takes all elements from the sequence, order matters

items[:i]+items[i+1]

def xcombinations(items, n): if n==0: yield [] else: for i in range(len(items)): for cc in xcombinations(items[:i]+items[i+1:],n-1): yield [items[i]]+cc

def xpermutations(items): return xcombinations(items, len(items))

Combinations any list

takes n distinct elements from the sequence, order matters

items[:i]+items[i+1:]

def xcombinations(items, n): if n==0: yield [] else: for i in range(len(items)): for cc in xcombinations(items[:i]+items[i+1:],n-1): yield [items[i]]+cc

Unique comibnations any list

takes n distinct elements from the sequence, order is irrelevant

items[i+1:]

def xuniqueCombinations(items, n): if n==0: yield [] else: for i in range(len(items)): for cc in xuniqueCombinations(items[i+1:],n-1): yield [items[i]]+cc

Selections any list

takes n elements (not necessarily distinct) from the sequence, order matters

items

def xselections(items, n): if n==0: yield [] else: for i in range(len(items)): for ss in xselections(items, n-1): yield [items[i]]+ss

insertion sort

def insertionSort(alist): for index in range(1,len(alist)):

currentvalue = alist[index] position = index while position>0 and alist[position-1]>currentvalue: alist[position]=alist[position-1] position = position-1 alist[position]=currentvalue

Simple Graph rep Python

graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])}

Stack

Collection

Push and pop

Peek access to too without changing

Last in first out

LIFO queue