KVSPGTCS – Lets make things better



Computer Science (083)CLASS-XII 2020-21DISTRIBUTION OF MARKS:UNITUNIT NAMEMARKSIComputational Thinking and Programming - 240IIComputer Networks10IIIDatabase Management20TOTAL70● Revision of the basics of Python covered in Class XI.● Functions: scope, parameter passing, mutable/immutable properties of data objects, passing strings, lists, tuples, dictionaries to functions, default parameters, positional parameters, return values, functions using libraries: mathematical and string functions.● File handling: Need for a data file, Types of file: Text files, Binary files and CSV (Comma separated values) files.● Text File: Basic operations on a text file: Open (filename – absolute or relative path, mode) / Close a text file, Reading and Manipulation of data from a text file, Appending data into a text file, standard input / output and error streams, relative and absolute paths.● Binary File: Basic operations on a binary file: Open (filename – absolute or relative path, mode) / Close a binary file, Pickle Module – methods load and dump; Read, Write/Create, Search, Append and Update operations in a binary file.● CSV File: Import csv module, functions – Open / Close a csv file, Read from a csv file and Write into a csv file using csv.reader ( ) and csv.writerow( ).● Using Python libraries: create and import Python libraries.● Recursion: simple algorithms with recursion: print a message forever, sum of first n natural numbers, factorial, Fibonacci numbers; recursion on arrays: binary search.● Idea of efficiency: performance measurement in terms of the number of operations.●Data-structures: Lists as covered in Class XI, Stacks – Push, Pop using a list, Queues – Insert, Delete using a list.RecursionIt is a way of programming or coding technique, in which a function calls itself for one or more times in its body. Usually, it is returning the return value of this function call procedure. If a function definition fulfills such conditions, we can call this function a recursive function.Recursion basically divides the big problem into small problems up to the point where it can be solved easily, for example if we have to calculate factorial of a 5, we will divide factorial of 5 as 5*factorial(4), then 4*factorial(3), then 3*factorial(2), then 2*factorial(1) and now factorial of 1 can be easily solved without any calculation, now each pending function will be executed in reverse order.Two important rules for Recursion:Must have a base case - There must be at least one base criteria/condition, when such condition is met the function stops calling itself.Must move toward the base case - The recursive calls should moves in such a way that each time it comes closer to the base criteria.Example:To print message foreverdef hellomessage():print("hello") hellomessage()hellomessage()In this code, base case is missing so hellomessage() function will call itself again and again till out of memory errorTo exit press ctrl+cExample: Sum of N Natural Numbers def sum(n):if n <= 1: return nelse:return n + sum(n-1)num = int(input("Enter a number: "))print("The sum is: ", sum(num))The input() function takes input from the user and int() function converts its type to an integer as input() return string. Here we call sum() function and pass the entered number, which is assigned to n. The base condition for recursion is defined and if the input number is less than or equals to 1, the number is returned, else we return the same function call with number decremented by 1. In this way, the recursive function works in Python that can calculate the sum of natural numbers. It works like(suppose we pass 5 in input5+sum(4)+sum(3)+sum(2)+1Example: Factorial of a Number Using RecursionAlgorithm:Test if n <= 0. If so, return 1.If not, then call the factorial algorithm with n – 1 and multiply the result by n and return that value.def factorial(x): if x==1:return 1 else:return x*factorial(x-1)f=factorial(5)print ("factorial of 5 is ",f)(factorial 5)(* 5 (factorial 4))(* 5 (* 4 (factorial 3)))(* 5 (* 4 (* 3 (factorial 2))))(* 5 (* 4 (* 3 (* 2 (factorial 1)))))(* 5 (* 4 (* 3 (* 2 1))))(* 5 (* 4 (* 3 2 )))(* 5 (* 4 6 ))(* 5 24 ))120Example: Fibonacci series using Recursion0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …Algorithm:Fib(n)If n =1 or n=2, thenreturn 1Elsea = Fib(n-1)b = Fib(n-2)return a+bdef fib(n): if n <= 1:return n else:return(fib(n-1) + fib(n-2))nterms = int(input("enter a number")) if nterms <= 0:print("Plese enter a positive integer")else:print("Fibonacci sequence:") for i in range(nterms):print(fib(i))Example: Binary search using RecursionAlgorithm:Find the midpoint of the array; this will be the element at arr[size/2]. The midpoint divides the array into two smaller arrays: lower half and upper halfCompare key to arr[midpoint] by calling the userfunction cmp_proc.If the key is a match, return arr[midpoint]; otherwiseIf the array consists of only one element return NULL, indicating that there is no match; otherwiseIf the key is less than the value extracted from arr[midpoint] search the lower half of the array by recursively calling search; otherwiseSearch the upper half of the array by recursively calling search.NOTE:- For binary search all elements must be in order.def binarySearch (arr, first, last, x):if last >= first:mid =int( first + (last - first)/2) if arr[mid] == x:return mid elif arr[mid] > x:return binarySearch(arr, first, mid-1, x)else:return binarySearch(arr, mid+1, last, x) else:return -1arr = [ 1,3,5,6,7,8,10,13,14 ]x = 10result = binarySearch(arr, 0, len(arr)-1, x)if result != -1:print ("Element is present at index %d" % result)else:print ("Element is not present in array") ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download