Skip to content

Commit f76c34b

Browse files
keonkeon
committed
initial
0 parents  commit f76c34b

34 files changed

Lines changed: 1541 additions & 0 deletions

‎README.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
# Pythonic Data Structures and Algorithms
2+
3+
Minimal and clean examples of data structures and algorithms.
4+
5+

‎builtins/dictionary.py‎

Whitespace-only changes.

‎builtins/list.py‎

Whitespace-only changes.

‎builtins/set.py‎

Whitespace-only changes.

‎builtins/tuple.py‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
def append_to_sequence (myseq):
2+
myseq += (9,9,9)
3+
return myseq
4+
5+
tuple1 = (1,2,3) # tuples are immutable
6+
list1 = [1,2,3] # lists are mutable
7+
8+
tuple2 = append_to_sequence(tuple1)
9+
list2 = append_to_sequence(list1)
10+
11+
print 'tuple1 = ', tuple1 # outputs (1, 2, 3)
12+
print 'tuple2 = ', tuple2 # outputs (1, 2, 3, 9, 9, 9)
13+
print 'list1 = ', list1 # outputs [1, 2, 3, 9, 9, 9]
14+
print 'list2 = ', list2 # outputs [1, 2, 3, 9, 9, 9]

‎graph/find_path.py‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
myGraph = {'A': ['B', 'C'],
2+
'B': ['C', 'D'],
3+
'C': ['D', 'F'],
4+
'D': ['C'],
5+
'E': ['F'],
6+
'F': ['C']}
7+
8+
# find path from start to end using recursion with backtracking
9+
def find_path(graph, start, end, path=[]):
10+
path = path + [start]
11+
if (start == end):
12+
return path
13+
if not start in graph:
14+
return None
15+
for node in graph[start]:
16+
if node not in path:
17+
newpath = find_path(graph, node, end, path)
18+
return newpath
19+
return None
20+
21+
# find all path
22+
def find_all_path(graph, start, end, path=[]):
23+
path = path + [start]
24+
print(path)
25+
if (start == end):
26+
return [path]
27+
if not start in graph:
28+
return None
29+
paths = []
30+
for node in graph[start]:
31+
if node not in path:
32+
newpaths = find_all_path(graph, node, end, path)
33+
for newpath in newpaths:
34+
paths.append(newpath)
35+
return paths
36+
37+
38+
def find_shortest_path(graph, start, end, path=[]):
39+
path = path + [start]
40+
if start == end:
41+
return path
42+
if start not in graph:
43+
return None
44+
shortest = None
45+
for node in graph[start]:
46+
if node not in path:
47+
newpath = find_shortest_path(graph, start, end, path)
48+
if newpath:
49+
if not shortest or len(newpath) < len(shortest):
50+
shortest = newpath
51+
return shortest
52+
53+
print(find_all_path(myGraph, 'A', 'F'))
54+
# print(find_shortest_path(myGraph, 'A', 'D'))

‎graph/graph.py‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
class Graph:
2+
def __init__(self, node, edges, source):
3+
pass

‎graph/traversal.py‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
graph = {'A': set(['B', 'C', 'F']),
2+
'B': set(['A', 'D', 'E']),
3+
'C': set(['A', 'F']),
4+
'D': set(['B']),
5+
'E': set(['B', 'F']),
6+
'F': set(['A', 'C', 'E'])}
7+
8+
# dfs and bfs are the ultimately same except that they are visiting nodes in
9+
# different order. To simulate this ordering we would use stack for dfs and
10+
# queue for bfs.
11+
#
12+
13+
def dfs_traverse(graph, start):
14+
visited, stack = set(), [start]
15+
while stack:
16+
node = stack.pop()
17+
if node not in visited:
18+
visited.add(node)
19+
for nextNode in graph[node]:
20+
if nextNode not in visited:
21+
stack.append(nextNode)
22+
return visited
23+
24+
# print(dfs_traverse(graph, 'A'))
25+
26+
27+
def bfs_traverse(graph, start):
28+
visited, queue = set(), [start]
29+
while queue:
30+
node = queue.pop(0)
31+
if node not in visited:
32+
visited.add(node)
33+
for nextNode in graph[node]:
34+
if nextNode not in visited:
35+
queue.append(nextNode)
36+
return visited
37+
38+
# print(bfs_traverse(graph, 'A'))
39+
40+
def dfs_traverse_recursive(graph, start, visited=None):
41+
if visited is None:
42+
visited = set()
43+
visited.add(start)
44+
for nextNode in graph[start]:
45+
if nextNode not in visited:
46+
dfs_traverse_recursive(graph, nextNode, visited)
47+
return visited
48+
49+
# print(dfs_traverse_recursive(graph, 'A'))
50+
51+
# def find_path(graph, start, end, visited=[]):
52+
# # basecase
53+
# visitied = visited + [start]
54+
# if start == end:
55+
# return visited
56+
# if start not in graph:
57+
# return None
58+
# for node in graph[start]:
59+
# if node not in visited:
60+
# new_visited = find_path(graph, node, end, visited)
61+
# return new_visited
62+
# return None
63+
64+
# print(find_path(graph, 'A', 'F'))
65+
66+

‎hashtable/hashtable.py‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# MAP Abstract Data Type
2+
# Map() Create a new, empty map. It returns an empty map collection.
3+
# put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
4+
# get(key) Given a key, return the value stored in the map or None otherwise.
5+
# del Delete the key-value pair from the map using a statement of the form del map[key].
6+
# len() Return the number of key-value pairs stored in the map.
7+
# in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.
8+
9+
class HashTable(object):
10+
def __init__(self, size = 11):
11+
self.size = size
12+
self.keys = [None] * size # keys
13+
self.values = [None] * size # values
14+
15+
def put(self, key, value):
16+
hashval = self.hash(key)
17+
18+
if hashval not in keys:
19+
self.keys[hashval] = key
20+
self.values[hashval] = value
21+
else:
22+
if self.keys[hashval] == key: # replace
23+
self.values[hashval] = value
24+
else: # probing
25+
rehashval = self.rehash(key)
26+
while self.keys[rehashval] is not None and \
27+
self.keys[rehashval] != key:
28+
rehashval = self.rehash(rehashval)
29+
if keys[rehashval] is None:
30+
self.keys[rehashval] = key
31+
self.values[rehashval] = value
32+
else:
33+
self.values[rehashval] = value # replacee
34+
35+
def get(self, key):
36+
pass
37+
38+
def hash(self, key):
39+
return key % self.size
40+
41+
def rehash(self, oldhash):
42+
"""
43+
linear probing
44+
"""
45+
return (oldhash + 1) % self.size
46+
47+
def __getitem__(self,key):
48+
return self.get(key)
49+
50+
def __setitem__(self, key, value):
51+
self.put(key, value)
52+
53+

‎linkedlist/linkedlist.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# Pros
2+
# Linked Lists have constant-time insertions and deletions in any position,
3+
# in comparison, arrays require O(n) time to do the same thing.
4+
# Linked lists can continue to expand without having to specify
5+
# their size ahead of time (remember our lectures on Array sizing
6+
# form the Array Sequence section of the course!)
7+
8+
# Cons
9+
# To access an element in a linked list, you need to take O(k) time
10+
# to go from the head of the list to the kth element.
11+
# In contrast, arrays have constant time operations to access
12+
# elements in an array.
13+
14+
class DoublyLinkedList(object):
15+
def __init__(self, value):
16+
self.value = value
17+
self.next = None
18+
self.prev = None
19+
20+
21+
class SinglyLinkedList(object):
22+
def __init__(self, value):
23+
self.value = value
24+
self.next = None

0 commit comments

Comments
 (0)