# Programming Flashcards

1
Q

change bases

A

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

2
Q

//

A

floor division

3
Q

DFS

A

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:
stack.extend(graph[vertex] - visited)
return visited```
4
Q

BFS

A

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:
queue.extend(graph[vertex] - visited)
return visited```
5
Q

Dijsktra

A

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

6
Q

DFS with goal node

A
```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]))```
7
Q

BFS with goal node

A
```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]))```
8
Q

Shortest path BFS

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

Permutations any list

A

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))```
10
Q

Combinations any list

A

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```
11
Q

Unique comibnations any list

A

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```
12
Q

Selections any list

A

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```
13
Q

insertion sort

A
```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```
14
Q

Simple Graph rep Python

A
```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'])}```
15
Q

Stack

A

Collection

Push and pop

Last in first out

LIFO queue

16
Q

Queue

A

FIFO

Dequeue removal from front

17
Q

Binary tree

A

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.

18
Q

binary search

A

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