Rohan Sharma MOOC Course Report (1).pptx

Mooc Ppt on Programming in python using data structures and algorithm

1. A MOOC Course Report on PROGRAMMING, DATA STRUCTURES AND ALGORITHMS IN PYTHON Submitted by Rohan Sharma [RA2011003030052] under the guidance of Mr. Lalit Sagar Under the governing ( NPTEL /COURSEERA/SEMINAR/ INDUSTRIAL TRAINING) body of BACHELOR OF TECHNOLOGY in COMPUTER SCIENCE & ENGINEERING of FACULTY OF ENGINEERING AND TECHNOLOGY SRM INSTITUTE OF SCIENCE & TECHNOLOGY,NCR CAMPUS NOV 2022

2. Certificate Add the image of the certificate

3. Outline Week 1: Introduction Week 2: Basics of Python Week 3: Lists, Inductive functions definitions, Sorting Week 4: Sorting ,Tuples,Dictionaries, Passing functions Week 5: Exception handling,Input/Output,file handling,string Week 6: Backtracing, Scope,Data structures,stacks ,queues ,heap Week 7: Classes,Objects and user defined datatypes Week 8: dynamic programming

4. Week1 Lecture 1: Algorithms and Programming : Simple gcd Lecture 2: Improving naive gcd Lecture 3:Euclid’s algorithm for gcd Lecture 4: Downloading and Installing Python

5. Algorithms, programming Algorithm: how to systematically perform a task Write down as a sequence of steps “Recipe”, or program Programming language describes the steps What is a step? Degrees of detail “Arrange the chairs” vs “Make 8 rows with 10 chairs in each row”

6. Computing gcd(m,n) List out factors of m List out factors of n Report the largest number that appears on both lists Is this a valid algorithm? Finite presentation of the “recipe” Terminates after a finite number of steps

7. Python program def gcd(m,n): fm = [] for i in range(1,m+1): if (m%i) == 0: fm.append(i) fn = [] for j in range(1,n+1): If (n%j) == 0: fn.append(j) cf = [] for f in fm: if f in fn: cf.append(f) return(cf[-1])

8. Week2 Lecture 1: Assignment statement, basic types- int ,float,bool Lecture 2: Strings Lecture 3: Lists Lecture 4:Control Flow Lecture 5:Functions

9. Assignment statement Assign a value to a name i = 5 j = 2*i j = j + 5 Left hand side is a name Right hand side is an expression Operations in expression depend on type of value

10. int vs float Why are these different types? Internally, a value is stored as a finite sequence of 0’s and 1’s (binary digits, or bits) For an int, this sequence is read off as a binary number For a float, this sequence breaks up into a mantissa and exponent Like “scientific” notation: 0.602 x 1024

11. Strings —type str Text values — type str, sequence of characters Single character is string of length 1 Extract individual characters by position Slices extract substrings + glues strings together Cannot update strings directly — immutable

12. Lists Lists are sequences of values Values need not be of uniform type Lists may be nested Can access value at a position, or a slice Lists are mutable, can update in place Assignment does not copy the value Use full slice to make a copy of a list

13. Control flow Normally, statements are executed top to bottom, in sequence Can alter the control flow if ... elif ... else — conditional execution for i in ... — repeat a fixed number of times while ... — repeat based on a condition

14. Function definition Functions are a good way to organise code in logical chunks Passing arguments to a function is like assigning values to names Only mutable values can be updated Names in functions have local scope Functions must be defined before use Recursion — a function can call itself

15. Week3 Lecture 1: More about range() Lecture 2: Manipulating lists Lecture 3: Breaking out of a loop Lecture 4: Arrays vs lists, binary search Lecture 5: Efficiency Lecture 6: Selection Sort Lecture 7: Insertion Sort Lecture 8: Recursion

16. More about range() range(n) has is implicitly from 0 to n-1 range(i,j,k) produces sequence in steps of k Negative k counts down Sequence produced by range() is not a list Use list(range(..)) to get a list

17. Lists To extend lists in place, use l.append(), l.extend() Can also assign new value, in place, to a slice Many built in functions for lists — see documentation Don’t forget to assign a value to a name before it is first used

18. Loops revisited Can exit prematurely from loop using break Applies to both for and while Loop also has an else: clause Special action for normal termination

19. Are built in lists in Python lists or arrays? Documentation suggests they are lists Allow efficient expansion, contraction However, positional indexing allows us to treat them as arrays In this course, we will “pretend” they are arrays Will later see explicit implementation of lists

20. Efficiency Theoretically T(n) = O(nk) is considered efficient Polynomial time In practice even T(n) = O(n2) has very limited effective range Inputs larger than size 5000 take very long

21. Sorting Finding minimum in unsorted segment of length k requires one scan, k steps In each iteration, segment to be scanned reduces by 1 T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n2)

22. Insertion Sort Inserting a new value in sorted segment of length k requires upto k steps in the worst case In each iteration, sorted segment in which to insert increased by 1 T(n) = 1 + 2 + ... + n-1 = n(n-1)/2 = O(n2)

23. O(n2) sorting algorithms Selection sort and insertion sort are both O(n2) O(n2) sorting is infeasible for n over 5000 Among O(n2) sorts, insertion sort is usually better than selection sort What happens when we apply insertion sort to an already sorted list? Next week, some more efficient sorting algorithms

24. Week4 Lecture 1: Merge Sort Lecture 2: Mergesort , analysis Lecture 3: Quicksort Lecture 4: Quicksort analysis Lecture 5: Tuples and Dictionaries Lecture 6: Functions Definitions Lecture 7: List Comprehension

25. Merge Sort def mergesort(A,left,right): # Sort the slice A[left:right] if right - left <= 1: # Base case return(A[left:right]) if right - left > 1: # Recursive call mid = (left+right)//2 L = mergesort(A,left,mid) R = mergesort(A,mid,right) return(merge(L,R))

26. Quicksort Quicksort, as described, is not stable Swap operation during partitioning disturbs original order Merge sort is stable if we merge carefully Do not allow elements from right to overtake elements from left Favour left list when breaking ties

27. Tuples and Dictionaries Dictionaries allow a flexible association of values to keys Keys must be immutable values Structure of dictionary is internally optimized for key- based lookup Use sorted(d.keys()) to retrieve keys in predictable order Extremely useful for manipulating information from text files, tables ... — use column headings as keys

28. Function definitions Function definitions behave like other assignments of values to names Can reassign a new definition, define conditionally Can pass function names to other functions

29. Week5 Lecture 1: Exception Handling Lecture 2: Standard input and output Lecture 3: Handling files Lecture 4: String Functions Lecture 5: Formatting printed output Lecture 6: pass, del() and None

30. Exception handling Exception handling allows us to gracefully deal with run time errors Can check type of error and take appropriate action based on type Can change coding style to exploit exception handling When dealing with files and input/output, exception handling becomes very important

31. Read from keyboard using input() Can also display a message Print to screen using print() Caveat: In Python 2, () is optional for print Can control format of print() output Optional arguments end="...", sep="..." More precise control later

32. Use pass for an empty block Use del() to remove elements from a list or dictionary Use the special value None to check if a name has been assigned a valid value

33. Week6 Lecture 1: Backtracking, N queens Lecture 2: Global scope , nested function Lecture 3: Generating permutations Lecture 4: Sets , Stacks , queues Lecture 5: Priority queues and heaps

34. Python names are looked up inside-out from within functions Updating a name with immutable value creates a local copy of that name Can update global names with mutable values Use global definition to update immutable values Can nest helper function — hidden to the outside

35. Data structures Data structures are ways of organising information that allow efficient processing in certain contexts Python has a built-in implementation of sets Stacks are useful to keep track of recursive computations Queues are useful for breadth-first exploration

36. Heaps are a tree implementation of priority queues insert( ) and delete_max( ) are both O(log N) heapify( ) builds a heap in O(N) Tree can be manipulated easily using an array Can invert the heap condition Each node is smaller than its children Min-heap, for insert( ), delete_min( )

37. Week7 Lecture 1: Abstract datatypes,classes and objects Lecture 2: Classes and Objects in Python Lecture 3: User defined lists Lecture 4: Search trees

38. Abstract datatype An abstract data type is a black box description Public interface — update/query the data type Private implementation — change does not affect functionality Classes and objects can be used for this

39. Classes and objects Class Template for a data type How data is stored How public functions manipulate data Object Concrete instance of template

40. Complexity All operations on search trees walk down a single path Worst-case: height of the tree Balanced trees: height is O(log n) for n nodes Tree can be balanced using rotations — look up AVL trees

41. Week8 Lecture 1: Memoization and dynamic programming Lecture 2:Grid paths Lecture 3: longest common subsequence Lecture 4: matrix multiplication Lecture 5: Wrap-Up

42. Dynamic programming Memoization Store values of subproblems in a table Look up the table before making a recursive call Dynamic programming: Solve subproblems in order of dependency Dependencies must be acyclic Iterative evaluation