Python – Algorithm Justifications ”; Previous Next In order to make claims about an Algorithm being efficient we need some mathematical tools as proof. These tools help us on providing a mathematically satisfying explanation on the performance and accuracy of the algorithms. Below is a list of some of those mathematical tools which can be used for justifying one algorithm over another. Direct Proof − It is direct verification of the statement by using the direct calculations. For example sum of two even numbers is always an even number. In this case just add the two numbers you are investigating and verify the result as even. Proof by induction − Here we start with a specific instance of a truth and then generalize it to all possible values which are part of the truth. The approach is to take a case of verified truth, then prove it is also true for the next case for the same given condition. For example all positive numbers of the form 2n-1 are odd. We prove it for a certain value of n, then prove it for the next value of n. This establishes the statement as generally true by proof of induction. Proof by contraposition − This proof is based on the condition If Not A implies Not B then A implies B. A simple example is if square of n is even then n must be even. Because if square on n is not even then n is not even. Proof by exhaustion − This is similar to direct proof but it is established by visiting each case separately and proving each of them. An example of such proof is the four color theorem. Print Page Previous Next Advertisements ”;
Category: python Data Structure
Python – 2-D Array
Python – 2-D Array ”; Previous Next Two dimensional array is an array within an array. It is an array of arrays. In this type of array the position of an data element is referred by two indices instead of one. So it represents a table with rows an dcolumns of data. In the below example of a two dimensional array, observer that each array element itself is also an array. Consider the example of recording temperatures 4 times a day, every day. Some times the recording instrument may be faulty and we fail to record data. Such data for 4 days can be presented as a two dimensional array as below. Day 1 – 11 12 5 2 Day 2 – 15 6 10 Day 3 – 10 8 12 5 Day 4 – 12 15 8 6 The above data can be represented as a two dimensional array as below. T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] Accessing Values The data elements in two dimesnional arrays can be accessed using two indices. One index referring to the main or parent array and another index referring to the position of the data element in the inner array.If we mention only one index then the entire inner array is printed for that index position. Example The example below illustrates how it works. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] print(T[0]) print(T[1][2]) Output When the above code is executed, it produces the following result − [11, 12, 5, 2] 10 To print out the entire two dimensional array we can use python for loop as shown below. We use end of line to print out the values in different rows. Example from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] for r in T: for c in r: print(c,end = ” “) print() Output When the above code is executed, it produces the following result − 11 12 5 2 15 6 10 10 8 12 5 12 15 8 6 Inserting Values We can insert new data elements at specific position by using the insert() method and specifying the index. Example In the below example a new data element is inserted at index position 2. from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] T.insert(2, [0,5,11,13,6]) for r in T: for c in r: print(c,end = ” “) print() Output When the above code is executed, it produces the following result − 11 12 5 2 15 6 10 0 5 11 13 6 10 8 12 5 12 15 8 6 Updating Values We can update the entire inner array or some specific data elements of the inner array by reassigning the values using the array index. Example from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] T[2] = [11,9] T[0][3] = 7 for r in T: for c in r: print(c,end = ” “) print() Output When the above code is executed, it produces the following result − 11 12 5 7 15 6 10 11 9 12 15 8 6 Deleting the Values We can delete the entire inner array or some specific data elements of the inner array by reassigning the values using the del() method with index. But in case you need to remove specific data elements in one of the inner arrays, then use the update process described above. Example from array import * T = [[11, 12, 5, 2], [15, 6,10], [10, 8, 12, 5], [12,15,8,6]] del T[3] for r in T: for c in r: print(c,end = ” “) print() Output When the above code is executed, it produces the following result − 11 12 5 2 15 6 10 10 8 12 5 Print Page Previous Next Advertisements ”;
Python – DS Environment
Python – DS Environment ”; Previous Next Python is available on a wide variety of platforms including Linux and Mac OS X. Let”s understand how to set up our Python environment. Local Environment Setup Open a terminal window and type “python” to find out if it is already installed and which version is installed. Unix (Solaris, Linux, FreeBSD, AIX, HP/UX, SunOS, IRIX, etc.) Win 9x/NT/2000 Macintosh (Intel, PPC, 68K) OS/2 DOS (multiple versions) PalmOS Nokia mobile phones Windows CE Acorn/RISC OS BeOS Amiga VMS/OpenVMS QNX VxWorks Psion Python has also been ported to the Java and .NET virtual machines Getting Python The most up-to-date and current source code, binaries, documentation, news, etc., is available on the official website of Python www.python.org You can download Python documentation from this website given herewith,www.python.org/doc. The documentation is available in HTML, PDF, and PostScript formats. Installing Python Python distribution is available for a wide variety of platforms. You need to download only the binary code applicable for your platform and install Python. If the binary code for your platform is not available, you need a C compiler to compile the source code manually. Compiling the source code offers more flexibility in terms of choice of features that you require in your installation. Here is a quick overview of installing Python on various platforms − Unix and Linux Installation Here are the simple steps to install Python on Unix/Linux machine. Open a Web browser and go to www.python.org/downloads. Follow the link to download zipped source code available for Unix/Linux. Download and extract files. Editing the Modules/Setup file if you want to customize some options. run ./configure script make make install This installs Python at standard location /usr/local/bin and its libraries at /usr/local/lib/pythonXX where XX is the version of Python. Windows Installation Here are the steps to install Python on Windows machine. Open a Web browser and go to www.python.org/downloads. Follow the link for the Windows installer python-XYZ.msi file where XYZ is the version you need to install. To use this installer python-XYZ.msi, the Windows system must support Microsoft Installer 2.0. Save the installer file to your local machine and then run it to find out if your machine supports MSI. Run the downloaded file. This brings up the Python install wizard, which is really easy to use. Just accept the default settings, wait until the install is finished, and you are done. Macintosh Installation Recent Macs come with Python installed, but it may be several years out of date. See www.python.org/download/mac/ for instructions on getting the current version along with extra tools to support development on the Mac. For older Mac OS”s before Mac OS X 10.3 (released in 2003), MacPython is available. Jack Jansen maintains it and you can have full access to the entire documentation at his website − http://www.cwi.nl/~jack/macpython.html. You can find complete installation details for Mac OS installation. Setting up PATH Programs and other executable files can be in many directories, so operating systems provide a search path that lists the directories that the OS searches for executables. The path is stored in an environment variable, which is a named string maintained by the operating system. This variable contains information available to the command shell and other programs. The path variable is named as PATH in Unix or Path in Windows (Unix is case sensitive; Windows is not). In Mac OS, the installer handles the path details. To invoke the Python interpreter from any particular directory, you must add the Python directory to your path. Setting path at Unix/Linux To add the Python directory to the path for a particular session in Unix − In the csh shell − type setenv PATH “$PATH:/usr/local/bin/python” and press Enter. In the bash shell (Linux) − type export ATH=”$PATH:/usr/local/bin/python” and press Enter. In the sh or ksh shell − type PATH=”$PATH:/usr/local/bin/python” and press Enter. Note − /usr/local/bin/python is the path of the Python directory Setting path at Windows To add the Python directory to the path for a particular session in Windows − At the command prompt − type path %path%;C:Python and press Enter. Note − C:Python is the path of the Python directory Python Environment Variables Here are important environment variables, which can be recognized by Python − Sr.No. Variable & Description 1 PYTHONPATH It has a role similar to PATH. This variable tells the Python interpreter where to locate the module files imported into a program. It should include the Python source library directory and the directories containing Python source code. PYTHONPATH is sometimes preset by the Python installer. 2 PYTHONSTARTUP It contains the path of an initialization file containing Python source code. It is executed every time you start the interpreter. It is named as .pythonrc.py in Unix and it contains commands that load utilities or modify PYTHONPATH. 3 PYTHONCASEOK It is used in Windows to instruct Python to find the first case-insensitive match in an import statement. Set this variable to any value to activate it. 4 PYTHONHOME It is an alternative module search path. It is usually embedded in the PYTHONSTARTUP or PYTHONPATH directories to make switching module libraries easy. Running Python There are three different ways to start Python, which are as follows − Interactive Interpreter You can start Python from Unix, DOS, or any other system that provides you a command-line interpreter or shell window.
Python – DS Home
Python – Data structures Tutorial PDF Version Quick Guide Resources Job Search Discussion Computers store and process data with an extra ordinary speed and accuracy. So, it is highly essential that the data is stored efficiently and can be accessed fast. Also, the processing of data should happen in the smallest possible time, but without losing the accuracy. Data structures deal with how the data is organised and held in the memory, when a program processes it. It is important to note that, the data that is stored in the disk as part of persistent storages (like relational tables) are not referred as data structure here. An Algorithm is step by step set of instruction to process the data for a specific purpose. So, an algorithm utilises various data structures in a logical way to solve a specific computing problem. In this tutorial, we will cover these two fundamental concepts of computer science using the Python programming language. Audience This tutorial is designed for Computer Science graduates as well as Software Professionals who are willing to learn data structures and algorithm programming in simple and easy steps using Python as a programming language. Prerequisites Before proceeding with this tutorial, you should have a basic knowledge of writing code in Python programming language, using any python integrated development environment (IDE) and execution of Python programs. If you are completely new to python, then please refer our Python tutorial to get a sound understanding of the language. Print Page Previous Next Advertisements ”;
Python – Arrays
Python – Arrays ”; Previous Next Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms. Following are the important terms to understand the concept of Array are as follows − Element − Each item stored in an array is called an element. Index − Each location of an element in an array has a numerical index, which is used to identify the element. Array Representation Arrays can be declared in various ways in different languages. Below is an illustration. As per the above illustration, following are the important points to be considered − Index starts with 0. Array length is 10, which means it can store 10 elements. Each element can be accessed via its index. For example, we can fetch an element at index 6 as 9. Basic Operations The basic operations supported by an array are as stated below − Traverse − print all the array elements one by one. Insertion − Adds an element at the given index. Deletion − Deletes an element at the given index. Search − Searches an element using the given index or by the value. Update − Updates an element at the given index. Array is created in Python by importing array module to the python program. Then, the array is declared as shown below − from array import * arrayName = array(typecode, [Initializers]) Typecode are the codes that are used to define the type of value the array will hold. Some common typecodes used are as follows − Typecode Value b Represents signed integer of size 1 byte B Represents unsigned integer of size 1 byte c Represents character of size 1 byte i Represents signed integer of size 2 bytes I Represents unsigned integer of size 2 bytes f Represents floating point of size 4 bytes d Represents floating point of size 8 bytes Before looking at various array operations lets create and print an array using python. Example The below code creates an array named array1. from array import * array1 = array(”i”, [10,20,30,40,50]) for x in array1: print(x) Output When we compile and execute the above program, it produces the following result − 10 20 30 40 50 Accessing Array Element We can access each element of an array using the index of the element. The below code shows how to access an array element. Example from array import * array1 = array(”i”, [10,20,30,40,50]) print (array1[0]) print (array1[2]) Output When we compile and execute the above program, it produces the following result, which shows the element is inserted at index position 1. 10 30 Insertion Operation Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array. Example Here, we add a data element at the middle of the array using the python in-built insert() method. from array import * array1 = array(”i”, [10,20,30,40,50]) array1.insert(1,60) for x in array1: print(x) When we compile and execute the above program, it produces the following result which shows the element is inserted at index position 1. Output 10 60 20 30 40 50 Deletion Operation Deletion refers to removing an existing element from the array and re-organizing all elements of an array. Example Here, we remove a data element at the middle of the array using the python in-built remove() method. from array import * array1 = array(”i”, [10,20,30,40,50]) array1.remove(40) for x in array1: print(x) Output When we compile and execute the above program, it produces the following result which shows the element is removed form the array. 10 20 30 50 Search Operation You can perform a search for an array element based on its value or its index. Example Here, we search a data element using the python in-built index() method. from array import * array1 = array(”i”, [10,20,30,40,50]) print (array1.index(40)) Output When we compile and execute the above program, it produces the following result which shows the index of the element. If the value is not present in the array then th eprogram returns an error. 3 Update Operation Update operation refers to updating an existing element from the array at a given index. Example Here, we simply reassign a new value to the desired index we want to update. from array import * array1 = array(”i”, [10,20,30,40,50]) array1[2] = 80 for x in array1: print(x) Output When we compile and execute the above program, it produces the following result which shows the new value at the index position 2. 10 20 80 40 50 Print Page Previous Next Advertisements ”;
Python – Lists
Python – Lists ”; Previous Next The list is a most versatile datatype available in Python which can be written as a list of comma-separated values (items) between square brackets. Important thing about a list is that items in a list need not be of the same type. Creating a list is as simple as putting different comma-separated values between square brackets. For example list1 = [”physics”, ”chemistry”, 1997, 2000] list2 = [1, 2, 3, 4, 5 ] list3 = [“a”, “b”, “c”, “d”] Similar to string indices, list indices start at 0, and lists can be sliced, concatenated and so on. Accessing Values To access values in lists, use the square brackets for slicing along with the index or indices to obtain value available at that index. For example #!/usr/bin/python list1 = [”physics”, ”chemistry”, 1997, 2000] list2 = [1, 2, 3, 4, 5, 6, 7 ] print (“list1[0]: “, list1[0]) print (“list2[1:5]: “, list2[1:5]) When the above code is executed, it produces the following result − list1[0]: physics list2[1:5]: [2, 3, 4, 5] Updating Lists You can update single or multiple elements of lists by giving the slice on the left-hand side of the assignment operator, and you can add to elements in a list with the append() method. For example #!/usr/bin/python list = [”physics”, ”chemistry”, 1997, 2000] print (“Value available at index 2 : “) print (list[2]) list[2] = 2001 print (“New value available at index 2 : “) print (list[2]) Note − append() method is discussed in subsequent section. When the above code is executed, it produces the following result − Value available at index 2 : 1997 New value available at index 2 : 2001 Delete List Elements To remove a list element, you can use either the del statement if you know exactly which element(s) you are deleting or the remove() method if you do not know. For example #!/usr/bin/python list1 = [”physics”, ”chemistry”, 1997, 2000] print (list1) del list1[2] print (“After deleting value at index 2 : “) print (list1) When the above code is executed, it produces following result − [”physics”, ”chemistry”, 1997, 2000] After deleting value at index 2 : [”physics”, ”chemistry”, 2000] Note − remove() method is discussed in subsequent section. Basic List Operations Lists respond to the + and * operators much like strings; they mean concatenation and repetition here too, except that the result is a new list, not a string. In fact, lists respond to all of the general sequence operations we used on strings in the prior chapter. Python Expression Results Description len([1, 2, 3]) 3 Length [1, 2, 3] + [4, 5, 6] [1, 2, 3, 4, 5, 6] Concatenation [”Hi!”] * 4 [”Hi!”, ”Hi!”, ”Hi!”, ”Hi!”] Repetition 3 in [1, 2, 3] True Membership for x in [1, 2, 3]: print x, 1 2 3 Iteration Print Page Previous Next Advertisements ”;