--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/day1/Problems.tex Fri Oct 02 16:42:15 2009 +0530
@@ -0,0 +1,594 @@
+\documentclass[12pt]{article}
+\title{Python Workshop\\Problems and Exercises}
+\author{Asokan Pichai\\Prabhu Ramachandran}
+\begin{document}
+\maketitle
+
+\section{Python}
+\subsection{Getting started}
+ \begin{verbatim}
+>>> print 'Hello Python'
+>>> print 3124 * 126789
+>>> 1786 % 12
+>>> 3124 * 126789
+>>> a = 3124 * 126789
+>>> big = 12345678901234567890 ** 3
+>>> verybig = big * big * big * big
+>>> 12345**6, 12345**67, 12345**678
+
+>>> s = 'Hello '
+>>> p = 'World'
+>>> s + p
+>>> s * 12
+>>> s * s
+>>> s + p * 12, (s + p)* 12
+>>> s * 12 + p * 12
+>>> 12 * s
+\end{verbatim}
+\newpage
+
+\begin{verbatim}
+>>> 17/2
+>>> 17/2.0
+>>> 17.0/2
+>>> 17.0/8.5
+>>> int(17/2.0)
+>>> float(17/2)
+>>> str(17/2.0)
+>>> round( 7.5 )
+\end{verbatim}
+
+\subsection{Mini exercises}
+\begin{itemize}
+ \item Round a float to the nearest integer, using \texttt{int()}?
+ \item What does this do? \\\texttt{round(amount * 10) /10.0 }
+ \item How to round a number to the nearest 5 paise?
+ \begin{description}
+ \item[Remember] 17.23 $\rightarrow$ 17.25,\\ while 17.22 $\rightarrow$ 17.20
+ \end{description}
+ \item How to round a number to the nearest 20 paise?
+\end{itemize}
+
+\begin{verbatim}
+ amount = 12.68
+ denom = 0.05
+ nCoins = round(amount/denom)
+ rAmount = nCoins * denom
+\end{verbatim}
+
+\subsection{Dynamic typing}
+\begin{verbatim}
+a = 1
+a = 1.1
+a = "Now I am a string!"
+\end{verbatim}
+
+\subsection{Comments}
+\begin{verbatim}
+a = 1 # In-line comments
+# Comment in a line to itself.
+a = "# This is not a comment!"
+ \end{verbatim}
+
+\section{Data types}
+\subsection{Numbers}
+ \begin{verbatim}
+>>> a = 1 # Int.
+>>> l = 1000000L # Long
+>>> e = 1.01325e5 # float
+>>> f = 3.14159 # float
+>>> c = 1+1j # Complex!
+>>> print f*c/a
+(3.14159+3.14159j)
+>>> print c.real, c.imag
+1.0 1.0
+>>> abs(c)
+1.4142135623730951
+>>> abs( 8 - 9.5 )
+1.5
+ \end{verbatim}
+
+\subsection{Boolean}
+ \begin{verbatim}
+>>> t = True
+>>> f = not t
+False
+>>> f or t
+True
+>>> f and t
+False
+>>> NOT True
+\ldots ???
+>>> not TRUE
+\ldots ???
+\end{verbatim}
+
+\subsection{Relational and logical operators}
+ \begin{verbatim}
+>>> a, b, c = -1, 0, 1
+>>> a == b
+False
+>>> a <= b
+True
+>>> a + b != c
+True
+>>> a < b < c
+True
+>>> c >= a + b
+True
+ \end{verbatim}
+
+\subsection{Strings}
+ \begin{verbatim}
+s = 'this is a string'
+s = 'This one has "quotes" inside!'
+s = "I have 'single-quotes' inside!"
+l = "A string spanning many lines\
+one more line\
+yet another"
+t = """A triple quoted string does
+not need to be escaped at the end and
+"can have nested quotes" etc."""
+ \end{verbatim}
+
+ \begin{verbatim}
+>>> w = "hello"
+>>> print w[0] + w[2] + w[-1]
+hlo
+>>> len(w) # guess what
+5
+>>> s = u'Unicode strings!'
+>>> # Raw strings (note the leading 'r')
+... r_s = r'A string $\alpha \nu$'
+ \end{verbatim}
+ \begin{verbatim}
+>>> w[0] = 'H' # Can't do that!
+Traceback (most recent call last):
+ File "<stdin>", line 1, in ?
+TypeError: object does not support item assignment
+ \end{verbatim}
+
+ \subsection{IPython}
+ \begin{verbatim}
+In [1]: a = 'hello world'
+In [2]: a.startswith('hell')
+Out[2]: True
+In [3]: a.endswith('ld')
+Out[3]: True
+In [4]: a.upper()
+Out[4]: 'HELLO WORLD'
+In [5]: a.upper().lower()
+Out[5]: 'hello world'
+
+In [6]: a.split()
+Out[6]: ['hello', 'world']
+In [7]: ''.join(['a', 'b', 'c'])
+Out[7]: 'abc'
+In [8] 'd' in ''.join( 'a', 'b', 'c')
+Out[8]: False
+a.split( 'o' )}
+???
+'x'.join( a.split( 'o' ) )
+???
+
+In [11]: x, y = 1, 1.2
+In [12]: 'x is %s, y is %s' %(x, y)
+Out[12]: 'x is 1, y is 1.234'
+
+'x is \%d, y is \%f' \%(x, y)
+???
+'x is \%3d, y is \%4.2f' \%(x, y)
+???
+ \end{verbatim}
+
+\subsection{A classic problem}
+ How to interchange values of two variables? Please note that the type of either variable is unknown and it is not necessary that both be of the same type even!
+
+\subsection{Basic conditional flow}
+ \begin{verbatim}
+In [21]: a = 7
+In [22]: b = 8
+In [23]: if a > b:
+ ....: print 'Hello'
+ ....: else:
+ ....: print 'World'
+ ....:
+ ....:
+World
+ \end{verbatim}
+
+\subsection{\texttt{If...elif...else} example}
+\begin{verbatim}
+x = int(raw_input("Enter an integer:"))
+if x < 0:
+ print 'Be positive!'
+elif x == 0:
+ print 'Zero'
+elif x == 1:
+ print 'Single'
+else:
+ print 'More'
+\end{verbatim}
+
+\subsection{Basic looping}
+ \begin{verbatim}
+# Fibonacci series:
+# the sum of two elements
+# defines the next
+a, b = 0, 1
+while b < 10:
+ print b,
+ a, b = b, a + b
+
+\end{verbatim}
+
+\section{Problem set 1}
+All the problems can be solved using \texttt{if} and \texttt{while}
+\begin{description}
+ \item[1.1] Write a program that displays all three digit numbers that are equal to the sum of the cubes of their digits. That is, print numbers $abc$ that have the property $abc = a^3 + b^3 + c^3$\\
+These are called $Armstrong$ numbers.
+
+\item[1.2 Collatz sequence]
+\begin{enumerate}
+ \item Start with an arbitrary (positive) integer.
+ \item If the number is even, divide by 2; if the number is odd multiply by 3 and add 1.
+ \item Repeat the procedure with the new number.
+ \item There is a cycle of 4, 2, 1 at which the procedure loops.
+\end{enumerate}
+ Write a program that accepts the starting value and prints out the Collatz sequence.
+
+ \item[1.3 Kaprekar's constant]
+ \begin{enumerate}
+ \item Take a four digit number--with at least two digits different.
+ \item Arrange the digits in ascending and descending order, giving A and D respectively.
+ \item Leave leading zeros in A!
+ \item Subtract A from D.
+ \item With the result, repeat from step 2.
+ \end{enumerate}
+ Write a program to accept a 4-digit number and display the progression to Kaprekar's constant.
+
+\item[1.4]
+ Write a program that prints the following pyramid on the screen.
+ \begin{verbatim}
+1
+2 2
+3 3 3
+4 4 4 4
+ \end{verbatim}
+The number of lines must be obtained from the user as input.\\
+When can your code fail?
+\end{description}
+
+\subsection{Functions: examples}
+ \begin{verbatim}
+def signum( r ):
+ """returns 0 if r is zero
+ -1 if r is negative
+ +1 if r is positive"""
+ if r < 0:
+ return -1
+ elif r > 0:
+ return 1
+ else:
+ return 0
+
+def pad( n, size ):
+ """pads integer n with spaces
+ into a string of length size
+ """
+ SPACE = ' '
+ s = str( n )
+ padSize = size - len( s )
+ return padSize * SPACE + s
+ \end{verbatim}
+What about \%3d?
+
+\subsection {What does this function do?}
+ \begin{verbatim}
+def what( n ):
+ if n < 0: n = -n
+ while n > 0:
+ if n % 2 == 1:
+ return False
+ n /= 10
+ return True
+ \end{verbatim}
+\newpage
+
+\subsection{What does this function do?}
+\begin{verbatim}
+def what( n ):
+ i = 1
+ while i * i < n:
+ i += 1
+ return i * i == n, i
+ \end{verbatim}
+
+\subsection{What does this function do?}
+ \begin{verbatim}
+def what( n, x ):
+ z = 1.0
+ if n < 0:
+ x = 1.0 / x
+ n = -n
+ while n > 0:
+ if n % 2 == 1:
+ z *= x
+ n /= 2
+ x *= x
+ return z
+ \end{verbatim}
+
+\section{Problem set 2}
+ The focus is on writing functions and calling them.
+\begin{description}
+ \item[2.1] Write a function to return the gcd of two numbers.
+ \item[2.2 Primitive Pythagorean Triads] A pythagorean triad $(a,b,c)$ has the property $a^2 + b^2 = c^2$.\\By primitive we mean triads that do not `depend' on others. For example, (4,3,5) is a variant of (3,4,5) and hence is not primitive. And (10,24,26) is easily derived from (5,12,13) and should not be displayed by our program. \\
+Write a program to print primitive pythagorean triads. The program should generate all triads with a, b values in the range 0---100
+\item[2.3] Write a program that generates a list of all four digit numbers that have all their digits even and are perfect squares.\\For example, the output should include 6400 but not 8100 (one digit is odd) or 4248 (not a perfect square).
+\item[2.4 Aliquot] The aliquot of a number is defined as: the sum of the \emph{proper} divisors of the number. For example, the aliquot(12) = 1 + 2 + 3 + 4 + 6 = 16.\\
+ Write a function that returns the aliquot number of a given number.
+\item[2.5 Amicable pairs] A pair of numbers (a, b) is said to be \emph{amicable} if the aliquot number of a is b and the aliquot number of b is a.\\
+ Example: \texttt{220, 284}\\
+ Write a program that prints all five digit amicable pairs.
+\end{description}
+
+\section{Lists}
+\subsection{List creation and indexing}
+\begin{verbatim}
+>>> a = [] # An empty list.
+>>> a = [1, 2, 3, 4] # More useful.
+>>> len(a)
+4
+>>> a[0] + a[1] + a[2] + a[-1]
+10
+\end{verbatim}
+
+\begin{verbatim}
+>>> a[1:3] # A slice.
+[2, 3]
+>>> a[1:-1]
+[2, 3, 4]
+>>> a[1:] == a[1:-1]
+False
+\end{verbatim}
+Explain last result
+
+\newpage
+\subsection{List: more slices}
+\begin{verbatim}
+>>> a[0:-1:2] # Notice the step!
+[1, 3]
+>>> a[::2]
+[1, 3]
+>>> a[-1::-1]
+\end{verbatim}
+What do you think the last one will do?\\
+\emph{Note: Strings also use same indexing and slicing.}
+ \subsection{List: examples}
+\begin{verbatim}
+>>> a = [1, 2, 3, 4]
+>>> a[:2]
+[1, 3]
+>>> a[0:-1:2]
+[1, 3]
+\end{verbatim}
+\emph{Lists are mutable (unlike strings)}
+
+\begin{verbatim}
+>>> a[1] = 20
+>>> a
+[1, 20, 3, 4]
+\end{verbatim}
+
+ \subsection{Lists are mutable and heterogenous}
+\begin{verbatim}
+>>> a = ['spam', 'eggs', 100, 1234]
+>>> a[2] = a[2] + 23
+>>> a
+['spam', 'eggs', 123, 1234]
+>>> a[0:2] = [1, 12] # Replace items
+>>> a
+[1, 12, 123, 1234]
+>>> a[0:2] = [] # Remove items
+>>> a.append( 12345 )
+>>> a
+[123, 1234, 12345]
+\end{verbatim}
+
+ \subsection{List methods}
+\begin{verbatim}
+>>> a = ['spam', 'eggs', 1, 12]
+>>> a.reverse() # in situ
+>>> a
+[12, 1, 'eggs', 'spam']
+>>> a.append(['x', 1])
+>>> a
+[12, 1, 'eggs', 'spam', ['x', 1]]
+>>> a.extend([1,2]) # Extend the list.
+>>> a.remove( 'spam' )
+>>> a
+[12, 1, 'eggs', ['x', 1], 1, 2]
+\end{verbatim}
+
+ \subsection{List containership}
+ \begin{verbatim}
+>>> a = ['cat', 'dog', 'rat', 'croc']
+>>> 'dog' in a
+True
+>>> 'snake' in a
+False
+>>> 'snake' not in a
+True
+>>> 'ell' in 'hello world'
+True
+ \end{verbatim}
+ \subsection{Tuples: immutable}
+\begin{verbatim}
+>>> t = (0, 1, 2)
+>>> print t[0], t[1], t[2], t[-1]
+0 1 2 2
+>>> t[0] = 1
+Traceback (most recent call last):
+ File "<stdin>", line 1, in ?
+TypeError: object does not support item assignment
+\end{verbatim}
+ Multiple return values are actually a tuple.\\
+ Exchange is tuple (un)packing
+ \subsection{\texttt{range()} function}
+ \begin{verbatim}
+>>> range(7)
+[0, 1, 2, 3, 4, 5, 6]
+>>> range( 3, 9)
+[3, 4, 5, 6, 7, 8]
+>>> range( 4, 17, 3)
+[4, 7, 10, 13, 16]
+>>> range( 5, 1, -1)
+[5, 4, 3, 2]
+>>> range( 8, 12, -1)
+[]
+ \end{verbatim}
+
+ \subsection{\texttt{for\ldots range(\ldots)} idiom}
+ \begin{verbatim}
+In [83]: for i in range(5):
+ ....: print i, i * i
+ ....:
+ ....:
+0 0
+1 1
+2 4
+3 9
+4 16
+\end{verbatim}
+
+ \subsection{\texttt{for}: the list companion}
+
+ \begin{verbatim}
+In [84]: a = ['a', 'b', 'c']
+In [85]: for x in a:
+ ....: print x, chr( ord(x) + 10 )
+ ....:
+a k
+b l
+c m
+ \end{verbatim}
+
+ \subsection{\texttt{for}: the list companion}
+ \begin{verbatim}
+In [89]: for p, ch in enumerate( a ):
+ ....: print p, ch
+ ....:
+ ....:
+0 a
+1 b
+2 c
+ \end{verbatim}
+Try: \texttt{print enumerate(a)}
+
+\section{Problem set 3}
+ As you can guess, idea is to use \texttt{for}!
+
+\begin{description}
+ \item[3.1] Which of the earlier problems is simpler when we use \texttt{for} instead of \texttt{while}?
+ \item[3.2] Given an empty chessboard and one Bishop placed in any square, say (r, c), generate the list of all squares the Bishop could move to.
+ \item[3.3] Given two real numbers \texttt{a, b}, and an integer \texttt{N}, write a
+ function named \texttt{linspace( a, b, N)} that returns an ordered list
+ of \texttt{N} points starting with \texttt{a} and ending in \texttt{b} and
+ equally spaced.\\
+ For example, \texttt{linspace(0, 5, 11)}, should return, \\
+\begin{verbatim}
+[ 0.0 , 0.5, 1.0 , 1.5, 2.0 , 2.5,
+ 3.0 , 3.5, 4.0 , 4.5, 5.0 ]
+\end{verbatim}
+ \item[3.4a] Use the \texttt{linspace} function and generate a list of N tuples of the form\\
+\texttt{[($x_1$,f($x_1$)),($x_2$,f($x_2$)),\ldots,($x_N$,f($x_N$))]}\\for the following functions,
+\begin{itemize}
+ \item \texttt{f(x) = sin(x)}
+ \item \texttt{f(x) = sin(x) + sin(10*x)}.
+\end{itemize}
+
+\item[3.4b] Using the tuples generated earlier, determine the intervals where the roots of the functions lie.
+\end{description}
+
+\section{IO}
+ \subsection{Simple tokenizing and parsing}
+ \begin{verbatim}
+s = """The quick brown fox jumped
+ over the lazy dog"""
+for word in s.split():
+ print word.capitalize()
+ \end{verbatim}
+
+ \begin{description}
+ \item[4.1] Given a string like, ``1, 3-7, 12, 15, 18-21'', produce the list \texttt{[1,3,4,5,6,7,12,15,18,19,20,21]}
+\end{description}
+
+ \subsection{File handling}
+\begin{verbatim}
+>>> f = open('/path/to/file_name')
+>>> data = f.read() # Read entire file.
+>>> line = f.readline() # Read one line.
+>>> f.close() # close the file.
+\end{verbatim}
+Writing files
+\begin{verbatim}
+>>> f = open('/path/to/file_name', 'w')
+>>> f.write('hello world\n')
+>>> f.close()
+\end{verbatim}
+
+ \subsection{File and \texttt{for}}
+\begin{verbatim}
+>>> f = open('/path/to/file_name')
+>>> for line in f:
+... print line
+...
+\end{verbatim}
+
+ \begin{description}
+ \item[4.2] The given file has lakhs of records in the form:
+ \texttt{RGN;ID;NAME;MARK1;\ldots;MARK5;TOTAL;PFW}.
+ Some entries may be empty. Read the data from this file and print the
+ name of the student with the maximum total marks.
+ \item[4.3] For the same data file compute the average marks in different
+ subjects, the student with the maximum mark in each subject and also
+ the standard deviation of the marks. Do this efficiently.
+\end{description}
+
+\section{Modules}
+\begin{verbatim}
+>>> sqrt(2)
+Traceback (most recent call last):
+ File "<stdin>", line 1, in <module>
+NameError: name 'sqrt' is not defined
+>>> import math
+>>> math.sqrt(2)
+1.4142135623730951
+
+>>> from math import sqrt
+>>> from math import *
+>>> from os.path import exists
+\end{verbatim}
+
+ \subsection{Modules: example}
+ \begin{verbatim}
+# --- arith.py ---
+def gcd(a, b):
+ if a%b == 0: return b
+ return gcd(b, a%b)
+def lcm(a, b):
+ return a*b/gcd(a, b)
+# ------------------
+>>> import arith
+>>> arith.gcd(26, 65)
+13
+>>> arith.lcm(26, 65)
+130
+ \end{verbatim}
+
+ \begin{description}
+ \item[5.1] Put all the functions you have written so far as part of the problems
+ into one module called \texttt{iitb.py} and use this module from IPython.
+\end{description}
+\end{document}