pseudo-code-algorithms-with-python

content history

JSON

rev 36  |  foxhop  |  1322504473000  |  JSON

rev 35
rev 36
159This is an example of building a hash table.159This is an example of building a hash table.
160160
n161#. sparse table or direct address table.n1611. sparse table or direct address table.
162 162 
163 **Assume that:**163 **Assume that:**
164 164 
n165 #.  Totle number of keys <= the size or the array.n165 *  Totle number of keys <= the size or the array.
166 #.  no 2 elements have the same keys.166 *  no 2 elements have the same keys.
167167
168 **Algorythm:**168 **Algorythm:**
169169
n170 #. Create A[0, max -1]n170 * Create A[0, max -1]
171 #. put key x into A[x]171 * put key x into A[x]
172  172  
173 **Example:**173 **Example:**
174174
n175  .. code-block:: pythonn175 .. code-block:: python
176176
n177   keys = 5,2,3,7 n177  keys = 5,2,3,7 
178178
t179   A = list()t179  A = list()
180   A[2] = 2180  A[2] = 2
181   A[5] = 5181  A[5] = 5
182   A[3] = 3182  A[3] = 3
183   A[7] = 7183  A[7] = 7
184 
1852. Hash table
186 
187 **Assume that:**
188 
189 * keys = {0,1,2,3,4,n-1}
190 * total numebr of keys > the size of the array
191 
192 **Algorythm:**
193 
194 * A = list(0, max -1)
195 * put key x into A[ hash(x) ]
196 
197 hash function like md5 or sha256 hash(x) = x mod 6
198 
199If you have collisions there could be a problem.
200 
201 
202 
203 
204 
205 
206 
184207
185208
rev 35  |  foxhop  |  1322503927000  |  JSON

rev 34
rev 35
159This is an example of building a hash table.159This is an example of building a hash table.
160160
tt161#. sparse table or direct address table.
162 
163 **Assume that:**
164 
165 #.  Totle number of keys <= the size or the array.
166 #.  no 2 elements have the same keys.
167 
168 **Algorythm:**
169 
170 #. Create A[0, max -1]
171 #. put key x into A[x]
172  
173 **Example:**
174 
175  .. code-block:: python
176 
177   keys = 5,2,3,7 
178 
179   A = list()
180   A[2] = 2
181   A[5] = 5
182   A[3] = 3
183   A[7] = 7
184 
185 
161186
162187
rev 34  |  foxhop  |  1322503095000  |  JSON

rev 33
rev 34
148          i -= 1148          i -= 1
149149
tt150Most operating systems use heap tree to manage memory.
151 
152 
153 
154hash table
155==============
156 
157Don't use this in production!  python has a datatype called dict, use that inste
 >ad!!!
158 
159This is an example of building a hash table.
160 
161 
162 
163 
164 
165 
166 
150167
151Extras168Extras
rev 33  |  foxhop  |  1322502936000  |  JSON

rev 32
rev 33
142     """Turn any array or list (data) into a heap tree"""142     """Turn any array or list (data) into a heap tree"""
143     j = ( len( data ) / 2 ) - 1143     j = ( len( data ) / 2 ) - 1
t144     for t144     i = j
145     while i >= 0:
146         current = data[i]
147         #insert_heap( current, i , length of subtree i - 1 )
148          i -= 1
145149
146150
rev 32  |  foxhop  |  1322502652000  |  JSON

rev 31
rev 32
142     """Turn any array or list (data) into a heap tree"""142     """Turn any array or list (data) into a heap tree"""
143     j = ( len( data ) / 2 ) - 1143     j = ( len( data ) / 2 ) - 1
t144     for Extrast144     for 
145 
146 
147Extras
145=============148============
146149
147Note:150Note:
rev 31  |  foxhop  |  1322502622000  |  JSON

rev 30
rev 31
142     """Turn any array or list (data) into a heap tree"""142     """Turn any array or list (data) into a heap tree"""
143     j = ( len( data ) / 2 ) - 1143     j = ( len( data ) / 2 ) - 1
n144 n
145 
146asdf
147     for Extras144     for Extras
148=============145=============
160157
161158
tt159Big-O notation compared to Complexity
160================================================
161 
162Always look for the worst case when finding the Big-O
163 
164* O( 1 )
165 
166 * Constant complexity
167 
168* O( log n ) 
169 
170 * Logarithmic complexity
171 
172* O( n )
173 
174 * Linear complexity
175 
176* O( n log n )
177 
178 * n log n complexity
179 
180* O( n^b )
181 
182 * Polynomial complexity
183 
184* O( b^n ), where b>1
185 
186 * Exponential complexity
187 
188* O( n! )
189 
190 * Factorial complexity
191 
192 
rev 30  |  foxhop  |  1322502547000  |  JSON

rev 29
rev 30
142     """Turn any array or list (data) into a heap tree"""142     """Turn any array or list (data) into a heap tree"""
143     j = ( len( data ) / 2 ) - 1143     j = ( len( data ) / 2 ) - 1
nn144 
145 
146asdf
144     for Extras147     for Extras
145=============148=============
157160
158161
t159Big-O notation compared to Complexityt
160================================================
161 
162Always look for the worst case when finding the Big-O
163 
164* O( 1 )
165 
166 * Constant complexity
167 
168* O( log n ) 
169 
170 * Logarithmic complexity
171 
172* O( n )
173 
174 * Linear complexity
175 
176* O( n log n )
177 
178 * n log n complexity
179 
180* O( n^b )
181 
182 * Polynomial complexity
183 
184* O( b^n ), where b>1
185 
186 * Exponential complexity
187 
188* O( n! )
189 
190 * Factorial complexity
191 
192 
rev 29  |  foxhop  |  1322502531000  |  JSON

rev 28
rev 29
130130
131131
t132Extrast132python heap
133=============
134 
135A heap is a binary tree where the parent is always larger than its children.
136 
137Determine the last nodes that are leaves: (total number of items / 2) - 1
138 
139.. code-block:: python
140 
141 def build_heap( data ):
142     """Turn any array or list (data) into a heap tree"""
143     j = ( len( data ) / 2 ) - 1
144     for Extras
133=============145=============
134146
rev 28  |  foxhop  |  1321717878000  |  JSON

rev 27
rev 28
127127
128128
tt129: )
130 
131 
129: )Extras132Extras
130=============133=============
131134
rev 27  |  foxhop  |  1321717867000  |  JSON

rev 26
rev 27
125    print gcd( 287, 91 )125    print gcd( 287, 91 )
126    print gcd2( 287, 91 )126    print gcd2( 287, 91 )
tt127 
128 
127Extras129: )Extras
128=============130=============
129131
rev 26  |  foxhop  |  1321700218000  |  JSON

rev 25
rev 26
100            break100            break
101101
tt102 
103 
104python recursion
105======================
106 
107.. code-block:: python
108 
109 def gcd( x, y ):
110     """Find greatest common divisor of two numbers recursion"""
111 
112     if y == 0: 
113         return x
114     else:
115         return gcd( y, x%y )
116    
117 def gcd2( x, y ):
118     """find the greatest common divisor of two numebrs"""
119     for i in range( 2, x ):
120         if x % i == 0 and y % i == 0:
121             return i; 
122 
123 
124 if __name__ == "__main__":
125    print gcd( 287, 91 )
126    print gcd2( 287, 91 )
102Extras127Extras
103=============128=============
rev 25  |  foxhop  |  1320695647000  |  JSON

rev 24
rev 25
7979
8080
n81Sort an array or listn81Bubble Sort an array or list
82===================================================82===================================================
8383
84This is a bubble sort algo using python, don't use this in production this is fo84This is a bubble sort algo using python, don't use this in production this is fo
>r learning only!>r learning only!
tt85 
86**BIGO(  n^2 )**
8587
86.. code-block:: python88.. code-block:: python
rev 24  |  foxhop  |  1320695497000  |  JSON

rev 23
rev 24
89    while True:89    while True:
90        swapped = False90        swapped = False
t91        for i in range( 0, len( mylist ) ):t91        for i in range( 0, len( mylist ) - 1 ):
92            if mylist[i] > mylist[i+1]:92            if mylist[i] > mylist[i+1]:
93                temp = mylist[i]93                temp = mylist[i]
rev 23  |  foxhop  |  1320695170000  |  JSON

rev 22
rev 23
82===================================================82===================================================
8383
nn84This is a bubble sort algo using python, don't use this in production this is fo
 >r learning only!
8485
n85asdfasdfn86.. code-block:: python
8687
t87 t88 def bubsort( mylist ):
88 89    while True:
90        swapped = False
91        for i in range( 0, len( mylist ) ):
92            if mylist[i] > mylist[i+1]:
93                temp = mylist[i]
94                mylist[i] = mylist[i+1]
95                mylist[i+1] = temp
96                swapped = True
97        if not swapped:
98            break
8999
90Extras100Extras
rev 22  |  foxhop  |  1320694514000  |  JSON

rev 21
rev 22
7979
8080
tt81Sort an array or list
82===================================================
83 
84 
85asdfasdf
8186
8287
rev 21  |  foxhop  |  1317060874000  |  JSON

rev 20
rev 21
4444
45the needle is the number we are searching for.45the needle is the number we are searching for.
tt46 
47Note
48  We call this algorithm the binary search.
4649
47.. code-block:: python50.. code-block:: python
rev 20  |  foxhop  |  1315869003000  |  JSON

rev 19
rev 20
48 48 
49 # binary search49 # binary search
n50 numbers = [0,11,25,38,41,54,66,79,80,94]n50 haystack = [0,11,25,38,41,54,66,79,80,94]
51 needle = 8051 needle = 80
5252
53 lo = 053 lo = 0
n54 hi = len( numbers )n54 hi = len( haystack )
5555
56 while lo < hi:56 while lo < hi:
58     mid = int( (lo + hi) / 2 )58     mid = int( (lo + hi) / 2 )
5959
n60     if needle > numbers[ mid ]:n60     if needle > haystack[ mid ]:
61         lo = mid + 161         lo = mid + 1
n62     elif needle < numbers[ mid ]:n62     elif needle < haystack[ mid ]:
63         hi = mid63         hi = mid
64     else:64     else:
n65         print "found %d which is the %d index of the list" % ( numbers[ mid ], n65         print "found %d which is the %d index of the list" % ( haystack[ mid ],
>mid )> mid )
66         break66         break
6767
72**The Big-0 of this program is n O(logn) - base 2**72**The Big-0 of this program is n O(logn) - base 2**
7373
t74This is a very good algorythm!t74This is a very good algorithm!
7575
7676
rev 19  |  foxhop  |  1315868921000  |  JSON

rev 18
rev 19
4646
47.. code-block:: python47.. code-block:: python
t48 t48 
49 # binary search
49 numbers = [0,11,25,38,41,54,66,79,80,94]50 numbers = [0,11,25,38,41,54,66,79,80,94]
50 needle = 8051 needle = 80
rev 18  |  foxhop  |  1315868864000  |  JSON

rev 17
rev 18
49 numbers = [0,11,25,38,41,54,66,79,80,94]49 numbers = [0,11,25,38,41,54,66,79,80,94]
50 needle = 8050 needle = 80
n51 #needle = 0 n
52 #needle = 94 
5351
n54 i = 0n52 lo = 0
55 j = len( numbers ) - 153 hi = len( numbers )
5654
n57 while i < j:n55 while lo < hi:
5856
n59     mid = int( (i + j) / 2 )n57     mid = int( (lo + hi) / 2 )
58 
60     if needle > numbers[ mid ]:59     if needle > numbers[ mid ]:
n61         i = mid + 1n60         lo = mid + 1
61     elif needle < numbers[ mid ]:
62         hi = mid
62     else:63     else:
n63         j = mid - 1n
64 
65     if needle == numbers[ mid ]:
66         print "found %d which is the %d index of the list" % ( numbers[ mid ], 64         print "found %d which is the %d index of the list" % ( numbers[ mid ], 
>mid )>mid )
67         break65         break
t68 t
6966
70* Worst case in  8 item list is 3 compares.67* Worst case in  8 item list is 3 compares.
rev 17  |  foxhop  |  1315867121000  |  JSON

rev 16
rev 17
41===================================================41===================================================
4242
t43Try to search to see if the number 7 is in the list or array.t43Try to search to see if the number 80 is in the list or array.
4444
45the needle is the number we are searching for.45the needle is the number we are searching for.
rev 16  |  foxhop  |  1315867041000  |  JSON

rev 15
rev 16
47.. code-block:: python47.. code-block:: python
4848
n49 numbers = [-1,0,2,2,4,5,6,6,7,8,9]n49 numbers = [0,11,25,38,41,54,66,79,80,94]
50 needle = 750 needle = 80
51 #needle = 0 
52 #needle = 94 
5153
n52 i = 1n54 i = 0
53 j = len(numbers) # or 1155 j = len( numbers ) - 1
5456
55 while i < j:57 while i < j:
5658
n57     m = int( i + j / 2 )n59     mid = int( (i + j) / 2 )
58     if needle < numbers[ m ]:60     if needle > numbers[ mid ]:
59         i = m + 161         i = mid + 1
60     else:62     else:
n61         j = mn63         j = mid - 1
6264
t63 if needle == m:t65     if needle == numbers[ mid ]:
64     print True66         print "found %d which is the %d index of the list" % ( numbers[ mid ], 
 >mid )
67         break
6568
6669
rev 15  |  foxhop  |  1315857628000  |  JSON

rev 14
rev 15
tt1Pseudo Code Algorithms with Python
2=========================================
3 
4.. contents::
5 
16
2Find the largest number in a list or array of numbers.7Find the largest number in a list or array of numbers.
rev 14  |  foxhop  |  1315857567000  |  JSON

rev 13
rev 14
n1Always look for the worst case when finding the Big-On
2 
3* O( 1 )
4 
5 * Constant complexity
6 
7* O( log n ) 
8 
9 * Logarithmic complexity
10 
11* O( n )
12 
13 * Linear complexity
14 
15* O( n log n )
16 
17 * n log n complexity
18 
19* O( n^b )
20 
21 * Polynomial complexity
22 
23* O( b^n ), where b>1
24 
25 * Exponential complexity
26 
27* O( n! )
28 
29 * Factorial complexity
30 
311
32Find the largest number in a list or array of numbers.2Find the largest number in a list or array of numbers.
11989
12090
tt91Big-O notation compared to Complexity
92================================================
93 
94Always look for the worst case when finding the Big-O
95 
96* O( 1 )
97 
98 * Constant complexity
99 
100* O( log n ) 
101 
102 * Logarithmic complexity
103 
104* O( n )
105 
106 * Linear complexity
107 
108* O( n log n )
109 
110 * n log n complexity
111 
112* O( n^b )
113 
114 * Polynomial complexity
115 
116* O( b^n ), where b>1
117 
118 * Exponential complexity
119 
120* O( n! )
121 
122 * Factorial complexity
123 
124 
rev 13  |  foxhop  |  1315857505000  |  JSON

rev 12
rev 13
f1Always look for the worst case when finding the Big-Of1Always look for the worst case when finding the Big-O
tt2 
3* O( 1 )
4 
5 * Constant complexity
6 
7* O( log n ) 
8 
9 * Logarithmic complexity
10 
11* O( n )
12 
13 * Linear complexity
14 
15* O( n log n )
16 
17 * n log n complexity
18 
19* O( n^b )
20 
21 * Polynomial complexity
22 
23* O( b^n ), where b>1
24 
25 * Exponential complexity
26 
27* O( n! )
28 
29 * Factorial complexity
230
331
rev 12  |  foxhop  |  1315856941000  |  JSON

rev 11
rev 12
tt1Always look for the worst case when finding the Big-O
2 
3 
1Find the largest number in a list or array of numbers.4Find the largest number in a list or array of numbers.
2========================================================5========================================================
rev 11  |  foxhop  |  1315856904000  |  JSON

rev 10
rev 11
t No Differences Found t No Differences Found 
rev 10  |  foxhop  |  1315856396000  |  JSON

rev 9
rev 10
6 numbers = [5,6,2,7,6,2,0,4]6 numbers = [5,6,2,7,6,2,0,4]
77
t8 max = a[0]t8 max = numbers[0]
99
10 for number in numbers:10 for number in numbers:
rev 9  |  foxhop  |  1315855936000  |  JSON

rev 8
rev 9
8484
85for( int i = 2 ; i<= n ; i++ ){   }85for( int i = 2 ; i<= n ; i++ ){   }
t86Worst case there will be at least two comparisons.t86Worst case there will be at least two comparisons. Or at least n - 1 comparisons
 >. 
8787
8888
rev 8  |  foxhop  |  1315855877000  |  JSON

rev 7
rev 8
6666
67This is a very good algorythm!67This is a very good algorythm!
tt68 
69 
70 
71 
72 
73 
74 
75Extras
76=============
77 
78Note:
79  Count the total number of comparisons in terms of n.
80 
81|
82|
83|
84 
85for( int i = 2 ; i<= n ; i++ ){   }
86Worst case there will be at least two comparisons.
87 
88 
89 
rev 7  |  foxhop  |  1315855562000  |  JSON

rev 6
rev 7
39the needle is the number we are searching for.39the needle is the number we are searching for.
4040
n41numbers = [-1,0,2,2,4,5,6,6,7,8,9]n41.. code-block:: python
42needle = 7
4342
n44i = 1n43 numbers = [-1,0,2,2,4,5,6,6,7,8,9]
45j = len(numbers) # or 1144 needle = 7
4645
n47while i < j:n46 i = 1
47 j = len(numbers) # or 11
4848
n49    m = int( i + j / 2 )n49 while i < j:
50    if needle < numbers[ m ]:
51        i = m + 1
52    else:
53        j = m
5450
tt51     m = int( i + j / 2 )
52     if needle < numbers[ m ]:
53         i = m + 1
54     else:
55         j = m
56 
55if needle == m:57 if needle == m:
56    print True58     print True
5759
5860
rev 6  |  foxhop  |  1315855506000  |  JSON

rev 5
rev 6
37Try to search to see if the number 7 is in the list or array.37Try to search to see if the number 7 is in the list or array.
3838
nn39the needle is the number we are searching for.
40 
39numbers = [-1,0,2,2,4,5,6,6,7,8,9]41numbers = [-1,0,2,2,4,5,6,6,7,8,9]
nn42needle = 7
43 
44i = 1
45j = len(numbers) # or 11
46 
47while i < j:
48 
49    m = int( i + j / 2 )
50    if needle < numbers[ m ]:
51        i = m + 1
52    else:
53        j = m
54 
55if needle == m:
56    print True
57 
4058
41* Worst case in  8 item list is 3 compares.59* Worst case in  8 item list is 3 compares.
45**The Big-0 of this program is n O(logn) - base 2**63**The Big-0 of this program is n O(logn) - base 2**
4664
tt65This is a very good algorythm!
rev 5  |  foxhop  |  1315855002000  |  JSON

rev 4
rev 5
3030
31**The Big-0 of this program is n  O(n)**31**The Big-0 of this program is n  O(n)**
tt32 
33 
34Search for a number in a Sorted array or list
35===================================================
36 
37Try to search to see if the number 7 is in the list or array.
38 
39numbers = [-1,0,2,2,4,5,6,6,7,8,9]
40 
41* Worst case in  8 item list is 3 compares.
42* Worst case in 16 item list is 4 compares.
43* Worst case in 32 item list is 5 compares.
44 
45**The Big-0 of this program is n O(logn) - base 2**
46 
rev 4  |  foxhop  |  1315854528000  |  JSON

rev 3
rev 4
13        max = number13        max = number
1414
t15**The Big-0 of this program is n  O(n)**Search for a number in an array or listt15**The Big-0 of this program is n  O(n)**
16 
17 
18Search for a number in an array or list
16=============================================19=============================================
1720
rev 3  |  foxhop  |  1315854511000  |  JSON

rev 2
rev 3
13        max = number13        max = number
1414
n15Search for a number in an array or listn15**The Big-0 of this program is n  O(n)**Search for a number in an array or list
16=============================================16=============================================
1717
25     if number == 0:25     if number == 0:
26         return True26         return True
t27 t27 
28**The Big-0 of this program is n  O(n)**
rev 2  |  foxhop  |  1315854400000  |  JSON

rev 1
rev 2
nn1Find the largest number in a list or array of numbers.
2========================================================
13
n2numbers = [5,6,2,7,6,2,0,4]n4.. code-block:: python
35
n4max = a[0]n6 numbers = [5,6,2,7,6,2,0,4]
57
nn8 max = a[0]
9 
6for number in numbers:10 for number in numbers:
711
8    if number > max:12    if number > max:
9        max = number13        max = number
tt14 
15Search for a number in an array or list
16=============================================
17 
18Try to search and see if the number 0 is in the list or array
19 
20.. code-block:: python 
21 
22 numbers = [5,6,2,7,6,2,0,4]
23 
24 for number in numbers:
25     if number == 0:
26         return True
27 
rev 1  |  foxhop  |  1315854183000  |  JSON

empty
rev 1
tt1 
2numbers = [5,6,2,7,6,2,0,4]
3 
4max = a[0]
5 
6for number in numbers:
7 
8    if number > max:
9        max = number