{"node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "revisions": [{"id": "f3a6d052-2f95-11f1-81ae-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n i = j\r\n while i >= 0:\r\n current = data[i]\r\n #insert_heap( current, i , length of subtree i - 1 )\r\n i -= 1\r\n\r\nMost operating systems use heap tree to manage memory.\r\n\r\n\r\n\r\nhash table\r\n==============\r\n\r\nDon't use this in production! python has a datatype called dict, use that instead!!!\r\n\r\nThis is an example of building a hash table.\r\n\r\n1. sparse table or direct address table.\r\n \r\n **Assume that:**\r\n \r\n * Totle number of keys <= the size or the array.\r\n * no 2 elements have the same keys.\r\n\r\n **Algorythm:**\r\n\r\n * Create A[0, max -1]\r\n * put key x into A[x]\r\n \r\n **Example:**\r\n\r\n .. code-block:: python\r\n\r\n keys = 5,2,3,7 \r\n\r\n A = list()\r\n A[2] = 2\r\n A[5] = 5\r\n A[3] = 3\r\n A[7] = 7\r\n\r\n2. Hash table\r\n\r\n **Assume that:**\r\n\r\n * keys = {0,1,2,3,4,n-1}\r\n * total numebr of keys > the size of the array\r\n\r\n **Algorythm:**\r\n\r\n * A = list(0, max -1)\r\n * put key x into A[ hash(x) ]\r\n\r\n hash function like md5 or sha256 hash(x) = x mod 6\r\n\r\nIf you have collisions there could be a problem.\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n \r\n\r\n\r\n\r\nExtras\r\n============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 36, "created": 1322504473000}, {"id": "f3a6cbbe-2f95-11f1-bd8f-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n i = j\r\n while i >= 0:\r\n current = data[i]\r\n #insert_heap( current, i , length of subtree i - 1 )\r\n i -= 1\r\n\r\nMost operating systems use heap tree to manage memory.\r\n\r\n\r\n\r\nhash table\r\n==============\r\n\r\nDon't use this in production! python has a datatype called dict, use that instead!!!\r\n\r\nThis is an example of building a hash table.\r\n\r\n#. sparse table or direct address table.\r\n \r\n **Assume that:**\r\n \r\n #. Totle number of keys <= the size or the array.\r\n #. no 2 elements have the same keys.\r\n\r\n **Algorythm:**\r\n\r\n #. Create A[0, max -1]\r\n #. put key x into A[x]\r\n \r\n **Example:**\r\n\r\n .. code-block:: python\r\n\r\n keys = 5,2,3,7 \r\n\r\n A = list()\r\n A[2] = 2\r\n A[5] = 5\r\n A[3] = 3\r\n A[7] = 7\r\n\r\n\r\n\r\n\r\n\r\n \r\n\r\n\r\n\r\nExtras\r\n============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 35, "created": 1322503927000}, {"id": "f3a6c6ee-2f95-11f1-8374-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n i = j\r\n while i >= 0:\r\n current = data[i]\r\n #insert_heap( current, i , length of subtree i - 1 )\r\n i -= 1\r\n\r\nMost operating systems use heap tree to manage memory.\r\n\r\n\r\n\r\nhash table\r\n==============\r\n\r\nDon't use this in production! python has a datatype called dict, use that instead!!!\r\n\r\nThis is an example of building a hash table.\r\n\r\n\r\n\r\n\r\n \r\n\r\n\r\n\r\nExtras\r\n============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 34, "created": 1322503095000}, {"id": "f3a6c325-2f95-11f1-b43b-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n i = j\r\n while i >= 0:\r\n current = data[i]\r\n #insert_heap( current, i , length of subtree i - 1 )\r\n i -= 1\r\n\r\n\r\nExtras\r\n============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 33, "created": 1322502936000}, {"id": "f3a6bf2a-2f95-11f1-b7aa-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n for \r\n\r\n\r\nExtras\r\n============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 32, "created": 1322502652000}, {"id": "f3a6b882-2f95-11f1-87ac-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n for Extras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 31, "created": 1322502622000}, {"id": "f3a6b2a5-2f95-11f1-96f5-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n\r\n\r\nasdf\r\n for Extras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 30, "created": 1322502547000}, {"id": "f3a6aedf-2f95-11f1-96d1-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\npython heap\r\n=============\r\n\r\nA heap is a binary tree where the parent is always larger than its children.\r\n\r\nDetermine the last nodes that are leaves: (total number of items / 2) - 1\r\n\r\n.. code-block:: python\r\n\r\n def build_heap( data ):\r\n \"\"\"Turn any array or list (data) into a heap tree\"\"\"\r\n j = ( len( data ) / 2 ) - 1\r\n for Extras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 29, "created": 1322502531000}, {"id": "f3a6ab12-2f95-11f1-b6c1-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 28, "created": 1321717878000}, {"id": "f3a6a73a-2f95-11f1-a439-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\n\r\n\r\n: )Extras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 27, "created": 1321717867000}, {"id": "f3a6a386-2f95-11f1-b17f-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\n\r\n\r\npython recursion\r\n======================\r\n\r\n.. code-block:: python\r\n\r\n def gcd( x, y ):\r\n \"\"\"Find greatest common divisor of two numbers recursion\"\"\"\r\n\r\n if y == 0: \r\n return x\r\n else:\r\n return gcd( y, x%y )\r\n \r\n def gcd2( x, y ):\r\n \"\"\"find the greatest common divisor of two numebrs\"\"\"\r\n for i in range( 2, x ):\r\n if x % i == 0 and y % i == 0:\r\n return i; \r\n\r\n\r\n if __name__ == \"__main__\":\r\n print gcd( 287, 91 )\r\n print gcd2( 287, 91 )\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 26, "created": 1321700218000}, {"id": "f3a69fb2-2f95-11f1-8a5e-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nBubble Sort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n**BIGO( n^2 )**\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 25, "created": 1320695647000}, {"id": "f3a69bf4-2f95-11f1-80d4-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nSort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) - 1 ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 24, "created": 1320695497000}, {"id": "f3a69834-2f95-11f1-b88a-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nSort an array or list\r\n===================================================\r\n\r\nThis is a bubble sort algo using python, don't use this in production this is for learning only!\r\n\r\n.. code-block:: python\r\n\r\n def bubsort( mylist ):\r\n while True:\r\n swapped = False\r\n for i in range( 0, len( mylist ) ):\r\n if mylist[i] > mylist[i+1]:\r\n temp = mylist[i]\r\n mylist[i] = mylist[i+1]\r\n mylist[i+1] = temp\r\n swapped = True\r\n if not swapped:\r\n break\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 23, "created": 1320695170000}, {"id": "f3a69391-2f95-11f1-bfe0-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\nSort an array or list\r\n===================================================\r\n\r\n\r\nasdfasdf\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 22, "created": 1320694514000}, {"id": "f3a68fc9-2f95-11f1-bdc3-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nNote\r\n We call this algorithm the binary search.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 21, "created": 1317060874000}, {"id": "f3a68c0c-2f95-11f1-9637-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n haystack = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( haystack )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > haystack[ mid ]:\r\n lo = mid + 1\r\n elif needle < haystack[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( haystack[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorithm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 20, "created": 1315869003000}, {"id": "f3a68847-2f95-11f1-89d5-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n \r\n # binary search\r\n numbers = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( numbers )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > numbers[ mid ]:\r\n lo = mid + 1\r\n elif needle < numbers[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( numbers[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 19, "created": 1315868921000}, {"id": "f3a68446-2f95-11f1-87d6-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n\r\n lo = 0\r\n hi = len( numbers )\r\n\r\n while lo < hi:\r\n\r\n mid = int( (lo + hi) / 2 )\r\n\r\n if needle > numbers[ mid ]:\r\n lo = mid + 1\r\n elif needle < numbers[ mid ]:\r\n hi = mid\r\n else:\r\n print \"found %d which is the %d index of the list\" % ( numbers[ mid ], mid )\r\n break\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 18, "created": 1315868864000}, {"id": "f3a67e8f-2f95-11f1-a6c1-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 80 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n #needle = 0 \r\n #needle = 94 \r\n\r\n i = 0\r\n j = len( numbers ) - 1\r\n\r\n while i < j:\r\n\r\n mid = int( (i + j) / 2 )\r\n if needle > numbers[ mid ]:\r\n i = mid + 1\r\n else:\r\n j = mid - 1\r\n\r\n if needle == numbers[ mid ]:\r\n print \"found %d which is the %d index of the list\" % ( numbers[ mid ], mid )\r\n break\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 17, "created": 1315867121000}, {"id": "f3a67a36-2f95-11f1-a220-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [0,11,25,38,41,54,66,79,80,94]\r\n needle = 80\r\n #needle = 0 \r\n #needle = 94 \r\n\r\n i = 0\r\n j = len( numbers ) - 1\r\n\r\n while i < j:\r\n\r\n mid = int( (i + j) / 2 )\r\n if needle > numbers[ mid ]:\r\n i = mid + 1\r\n else:\r\n j = mid - 1\r\n\r\n if needle == numbers[ mid ]:\r\n print \"found %d which is the %d index of the list\" % ( numbers[ mid ], mid )\r\n break\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 16, "created": 1315867041000}, {"id": "f3a6766e-2f95-11f1-beec-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Pseudo Code Algorithms with Python\r\n=========================================\r\n\r\n.. contents::\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 15, "created": 1315857628000}, {"id": "f3a6725b-2f95-11f1-95e3-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\nBig-O notation compared to Complexity\r\n================================================\r\n\r\nAlways look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\n", "source_format": "rst", "revision_number": 14, "created": 1315857567000}, {"id": "f3a66bf4-2f95-11f1-a315-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Always look for the worst case when finding the Big-O\r\n\r\n* O( 1 )\r\n\r\n * Constant complexity\r\n\r\n* O( log n ) \r\n \r\n * Logarithmic complexity\r\n\r\n* O( n )\r\n \r\n * Linear complexity\r\n\r\n* O( n log n )\r\n\r\n * n log n complexity\r\n\r\n* O( n^b )\r\n\r\n * Polynomial complexity\r\n\r\n* O( b^n ), where b>1\r\n \r\n * Exponential complexity\r\n\r\n* O( n! )\r\n\r\n * Factorial complexity\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 13, "created": 1315857505000}, {"id": "f3a665c5-2f95-11f1-9303-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Always look for the worst case when finding the Big-O\r\n\r\n\r\nFind the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 12, "created": 1315856941000}, {"id": "f3a660f5-2f95-11f1-a70b-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 11, "created": 1315856904000}, {"id": "f3a65d46-2f95-11f1-b7bb-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = numbers[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 10, "created": 1315856396000}, {"id": "f3a65993-2f95-11f1-a374-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons. Or at least n - 1 comparisons. \r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 9, "created": 1315855936000}, {"id": "f3a655e9-2f95-11f1-a895-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\nExtras\r\n=============\r\n\r\nNote:\r\n Count the total number of comparisons in terms of n.\r\n\r\n|\r\n|\r\n|\r\n\r\nfor( int i = 2 ; i<= n ; i++ ){ }\r\nWorst case there will be at least two comparisons.\r\n\r\n\r\n\r\n", "source_format": "rst", "revision_number": 8, "created": 1315855877000}, {"id": "f3a65233-2f95-11f1-a9d0-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\n.. code-block:: python\r\n\r\n numbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n needle = 7\r\n\r\n i = 1\r\n j = len(numbers) # or 11\r\n\r\n while i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\n if needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n", "source_format": "rst", "revision_number": 7, "created": 1315855562000}, {"id": "f3a64e55-2f95-11f1-b6d6-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nthe needle is the number we are searching for.\r\n\r\nnumbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\nneedle = 7\r\n\r\ni = 1\r\nj = len(numbers) # or 11\r\n\r\nwhile i < j:\r\n\r\n m = int( i + j / 2 )\r\n if needle < numbers[ m ]:\r\n i = m + 1\r\n else:\r\n j = m\r\n\r\nif needle == m:\r\n print True\r\n\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\nThis is a very good algorythm!\r\n", "source_format": "rst", "revision_number": 6, "created": 1315855506000}, {"id": "f3a64a57-2f95-11f1-b8ab-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in a Sorted array or list\r\n===================================================\r\n\r\nTry to search to see if the number 7 is in the list or array.\r\n\r\nnumbers = [-1,0,2,2,4,5,6,6,7,8,9]\r\n\r\n* Worst case in 8 item list is 3 compares.\r\n* Worst case in 16 item list is 4 compares.\r\n* Worst case in 32 item list is 5 compares.\r\n\r\n**The Big-0 of this program is n O(logn) - base 2**\r\n\r\n", "source_format": "rst", "revision_number": 5, "created": 1315855002000}, {"id": "f3a6457a-2f95-11f1-b00b-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**\r\n\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**", "source_format": "rst", "revision_number": 4, "created": 1315854528000}, {"id": "f3a6410e-2f95-11f1-932a-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\n**The Big-0 of this program is n O(n)**Search for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n\r\n**The Big-0 of this program is n O(n)**", "source_format": "rst", "revision_number": 3, "created": 1315854511000}, {"id": "f3a63b80-2f95-11f1-8350-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "Find the largest number in a list or array of numbers.\r\n========================================================\r\n\r\n.. code-block:: python\r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n max = a[0]\r\n\r\n for number in numbers:\r\n\r\n if number > max:\r\n max = number\r\n\r\nSearch for a number in an array or list\r\n=============================================\r\n\r\nTry to search and see if the number 0 is in the list or array\r\n\r\n.. code-block:: python \r\n\r\n numbers = [5,6,2,7,6,2,0,4]\r\n\r\n for number in numbers:\r\n if number == 0:\r\n return True\r\n ", "source_format": "rst", "revision_number": 2, "created": 1315854400000}, {"id": "f3a6340f-2f95-11f1-8074-e86a64d24d78", "node_id": "f3a5a031-2f95-11f1-8053-e86a64d24d78", "user_id": "edc3f576-2f95-11f1-900f-e86a64d24d78", "author": "foxhop", "data": "\r\nnumbers = [5,6,2,7,6,2,0,4]\r\n\r\nmax = a[0]\r\n\r\nfor number in numbers:\r\n\r\n if number > max:\r\n max = number", "source_format": "rst", "revision_number": 1, "created": 1315854183000}], "count": 36}