theabraham


Joined 2 years ago
Homeworks submitted:
Homework comments: 		1
1

About Me

No description provided.

Classes

Test

Class status: Unpublished
Role: Creator 		. 0% complete

Survey of Artificial Intelligence

Class status: Under Construction
Role: Student 		. 0% complete

MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming

Class status: Established
Role: Student 		. 5% complete

Submitted Assignments

MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 12, HW 1

With the first four problems, it helped me to watch lecture 8 again. I think I have them all right, but I may have deduced the answer incorrectly. My biggest concern is how to handle statements like if not in c that are in for loops (Does the search count as a loop in itself? If so, wouldn't it make it quadratic?) Any comments would be appreciated.

Problem 1 Has a complexity of O(n). It's a recursive function that has about 3n+f(i-n) steps in it.

Problem 2 Has a complexity of O(n). There are about 3+3n steps, making it have a linear growth.

Problem 3 Has a complexity of O(n). There are about 3+3n steps (unless the if statement counts as a loop within a loop, then it'd be quadratic)

Problem 4 Has a complexity of O(n). There are 3+2(3+3n)+3n, or 9+9n steps (because the makeSet function, which has a for loop within it is being used).

#
# Problem 5
#
def swap0(s1, s2): #Given s1 = [1] and s2 = [2]
    assert type(s1) == list and type(s2) == list #True
    tmp = s1[:] #tmp = [1], a new copy of s1
    s1 = s2[:] #s1 = [2]
    s2 = tmp #s2 = [1]
    return 

s1 = [1]
s2 = [2]
swap0(s1, s2) #Doesn't change anything because s1 and s2 are only changed
	      #locally in the function, and were not returned properly
print s1, s2  #Prints [1] [2]

#
# Problem 6
#
def swap1(s1, s2): #Given s1 = [1] and s2 = [2] 
    assert type(s1) == list and type(s2) == list #True
    return s2, s1 #Return them, with s2 being returned first
s1 = [1] 
s2 = [2] 
s1, s2 = swap1(s1, s2) #Translates to s2, s1 setting the values to swap
print s1, s2 #Prints [2] [1]

#
# Problem 7
#
def rev(s): #Given s = [1,2,3]
    assert type(s) == list #True
    for i in range(len(s)/2): #Loop through once (3/2 = 1)
        tmp = s[i] #tmp = 1
        s[i] = s[-(i+1)] #Change the first value, 1, to that of the last's, 3
        s[-(i+1)] = tmp #Change the last's value, 3, to the temporarily stored value, 1
s = [1,2,3] 
rev(s) #Reverses s
print s #Prints [3,2,1]

theabraham 1 year ago