Programming

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

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

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

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

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]))

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]))

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

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))

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

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

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

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

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'])}

Collection Push and pop Peek access to too without changing Last in first out LIFO queue

FIFO Enqueue add to end Dequeue removal from front

Left and right Left < right Add: recursive call with left if < current left, right if right > current right, if left or right is none then assign Find: recursive call with left if val < node.val, right if val > node.val, return node if equal.

min and max, floor division, -1 if searching lower, +1 if searching higher, first max value -1 in python def binary_search(seq, t): min = 0 max = len(seq) - 1 while True: if max < min: return -1 m = (min + max) // 2 if seq[m] < t: min = m + 1 elif seq[m] > t: max = m - 1 else: return m