Data Structures

Introduction to Software Design

Python

Self Study in a Programming System

LESSON III: FUNCTIONS AND CONTROL STRUCTURES DANIEL EISERT Class Business Assignment 1 on Canvas is due in one week. Data Types & Object References - Identity: never changes once it is created. - id() function: returns integer values representing its identity; the id of an object is an integer that represents the address of an object in memory. - Type: defines the values and operations. - type() function: returns the type of an object; the type of an object cannot be changed like the identity. - Mutable values: values that are changeable (i.e. list, dictionary, set, and user-defined classes). - Immutable values: values that are unchangeable (i.e. int, float, bool, string, tuple, and range). - Python does not have variables; Python has object references instead. - Memory optimization: if two int variables have the same values between -5 and 256, the same location in memory is referenced since Python has front-loaded an array with those values.  Example from the Terminal >>> x_one = 10 >>> x_two = 10 >>> x_one is x_two # is keyword is used for memory values True >>> id(x_one) 4533881168 >>> id(x_two) 4533881168 >>> x_one = 100 >>> id(x_one) 4533884048 Lists - Two variables can refer to the same object through a process called aliasing .  Example from the Terminal (note that lists are mutable objects) >>> list1 = [4, 5, 6] >>> list2 = [4, 5, 6] >>> list1 is list2 False >>> id(list1) 4537849608 >>> id(list2) 4537866376 >>> list1 = list2 # sets both to same space in memory >>> list1 == list2 # == is for same contents True >>> list1.append(25) Daniel Eisert CS-2304: Python Programming Page 1 of 1 >>> list1 [4, 5, 6, 25] >>> list2 [4, 5, 6, 25] # note that 25 was appended to list2 as well Functions - ord(“d”) #returns 100  returns ASCII value (remember that capitals come before lowercase letters). - Remember that indentation is very important. - You cannot overload functions; however, Python is flexible about the number of parameters you need to specify. - You do not need blocks. - Python includes several built-in functions (some include max(), min(), and len()); they can convert values from one type to another. Examples: def main(): print(“Hello World!”) ## end of function main() ## calls the function def function(parameters): pass # empty block to non-implemented functions def function(): #this will not compile; need to say pass def volume(w, l, h): return w*l*h int ans = volume(6, 10, 76) >>> int(‘42’) 42 >>> int(5.697230) 5 >>> float(42) 42.0 >>> str(42) ‘42’ def computePay(): userInput = input(‘Enter hours: ‘) # inputs as string hours = float(userInput) # converts string to float userInput = input(‘Enter Rate: ‘) rate = float(userInput) Daniel Eisert CS-2304: Python Programming Page 1 of 1

CS | 2304 | Self Study in a Programming System | lecture notes | LESSON III: FUNCTIONS AND CONT

CS-2114_-_Notes_-_Reading_9_-_Sorting.docx-Daniel T. Eisert CS-2114 8 –

CS-2114_-_Notes_-_Day_20_-_Iterators_and_Generics_II.docx-Daniel T. Eisert CS-2114 Lecture 20

1 Daniel T. Eisert CS-2114 4 – Efficiency of Algorithms Software Design & Data Structures Algorithm Efficiency Efficiency is not as important as it was fifty years ago, but in some cases, it still can be a critical component to consider when writing code. Measuring an Algorithms Efficiency: - Complexity: the time and space requirements of an algorithm. This does not account for how involved or difficult it is. - Time Complexity: the time an algorithm takes to execute. - Space Complexity: the memory an algorithm needs to execute. - The best solution depends on various criteria such as time, space, generality, programming effort, etc. - Generally, time is more important than space, but saving execution time usually requires more space and reducing the space requirement usually requires more time. - Analysis of Algorithms: a processed used to measure the complexity of algorithms. - Problem Size: the number of items that an algorithm processes (i.e. if you are searching a collection of data, the problem size is the number of items in the collection). - The value of the function is directly proportional to the time requirement (also known as a growth-rate function since it measures how an algorithm’s time requirement grows as the problem size grows).  Example: The following logic requires n + 1 assignments, n + 1 comparisons, and n additions. Additionally, initialization requires another n + 1 assignments and n additions for its initialization and loop body. Total, this algorithm requires 2n + 2 assignments, 2n additions, and n + 1 comparisons. Therefore, it would require ( 2 n + 2 ) t ¿ + ( 2 n ) t + ¿ +( n + 1 ) t c ¿ time units. long n = 10000; long sum = 0; for (long i = 1; i <= n; i++) sum = sum + i; System.out.println(sum); If each t is replaced by the largest of the three values, Algorithm A requires no more than (5n + 3)t time units. This algorithm’s required time is directly proportional to 5n + 3. Counting Basic Operations: - Additions, Subtractions, Multiplications, Divisions - Relative Magnitudes of Growth Rate Functions: 1 < log ¿ - An algorithm’s average case is most useful but hard to estimate. It is not the average of the best case and worst case times. 1 Daniel T. Eisert CS-2114 Algorithm Efficiency Big Oh Notation: - O ( n ) means that the algorithm’s time requirement is proportional to n . This is read as “Big Oh of n ” or “order of at most n .” - O ( n 2 ) can also be said. - O ( 1 ) means that regardless of the problem size n , the algorithm always requires the same time (independent of the number of entries). - Formal definition: A function f ( n ) is of order at most g ( n ) —that is, f ( n ) is O ( g ( n ) ) —if a positive real number c and a positive integer N exists such that f ( n ) ≤c ∗ g ( n ) for all n≥N . That is, c ∗ g ( n ) is an upper bound on f ( n ) when n is sufficiently large. - The upper bound of an algorithm’s time requirement should be as small as possible.  Example: Show that 4 n 2 + 50 n − 10 is O ( n 2 ) . 4 n 2 + 50 n − 10 ≤ 4 n 2 + 50 n for any n Since 50 n≤ 50 n 2 for n≥ 50 , 4 n 2 + 50 n − 10 ≤ 4 n 2 + 50 n = 54 n 2 for n≥ 50 Thus, with c = 54 and N = 50, we have shown that 4 n 2 + 50 n − 10 is O ( n 2 ) . The Complexities of Program Constructs: Construct Time Complexity Consecutive program segments S 1 , S 2 , …, S k whose growth-rate functions are g 1 , …, g k respectively. max ( O ( g 1 ) ,O ( g 2 ) ,…,O ( g k ) ) An if-statement that chooses between segments S 1 and S 2 whose growth-rate functions are g 1 and g 2 respectively. O ( condition )+ max ( O ( g 1 ) ,O ( g 2 ) ) A loop that iterates m times and has a body whose growth-rate function is g. m ∗ O ( g ( n ) ) - Big Omega refers to its lower bound/minimum time requirement. - Big Theta analysis assures that the time estimate is as good as possible. - When loops are nested, examine the innermost loop first. Growth-Rate Function for Size n Problems Growth-Rate Function for Size 2 n Problems Effect on Time Requirement 1 1 None log n 1 + log n Negligible n 2 n Doubles n log n 2 n log n + 2 n Doubles and adds 2 n n 2 ( 2 n ) 2 Quadruples n 3 ( 2 n ) 3 Multiplies by 8

CS | 2114 | Data Structures | lecture notes | 1 Daniel T. Eisert CS-2114 4 –

CS-1064: Week VIII MODULE VII: CS-1064: Day XX Monday, March 12 Snow Day Notes: Watch the video Dr. Austin Cory Bart sent out. CS-1064: Day XX Wednesday, March 14 While Loops Notes: command = True while command: command = input(“Give me a word”) print(command)  This works despite command having different types; this is allowed in Python, but NOT other langu

All courses in CS

Popular Documents