Exam theory Flashcards
Which of the following is not true in case of a Python dictionary?
A. Matches “keys” to “values”
B. We can look up one item by another item
C. Order is guaranteed
D. Key can be any immutable type (dictionary mutable)
C. Order is NOT guaranteed
CLASSES OF TESTS
Unit testing • testing each function separately Regression testing • catch reintroduced errors that were previously fixed Integration testing • does overall program work?
SIMPLIFICATION EXAMPLES
• drop constants and multiplicative factors • focus on dominant terms O(n^2): n^2 + 2n + 2 O(n^2): n^2 + 100000n + 31000 O(n): log(n) + n + 4 O(n*logn) : 0.0001*n*log(n) + 300n O(3^n) : 2n^30 + 3^n
BUBBLE SORT
• compare consecutive pairs of elements
• swap elements in pair such that smaller is first
• largest unsorted element always at end after the pass, so at most n passes
• complexity is O(n^2) where n is len(L)
(swap and for)
SELECTION SORT
- extract minimum element
- swap it with element at index 0 (1,2, … and so on)
- at i’th step, first i elements in list are sorted (all other bigger)
- O(n^2) where n is len(L)
MERGE SORT
- if list is of length 0 or 1, already sorted
- if list has more than one element, split into two lists, and sort each by comparing first elements
- merge sorted sublists (add smaller element to the result list)
• complexity O(n * log(n)) where n is len(L) - Overall complexity of similar Quick sort = O(n*log(n)) - average; O(n^2) - worst case
range() find() list[::] .append(item) .extend(item) round()
range(start, stop, step) - not including stop (spaces in strings also indexed; when numbers wrongly specified, just does not execute (range(10,1,2)); when floats=TypeError )
find(value, start, end) - not including stop; finds first occurrence of specified value
list[ Initial : End : IndexJump ] - not including end
.append(item) - [ , , , [ , , ]]
.extend(item) - [ , , , , , ]
round(number, digits) - number of digits after dot
BLACK BOX TESTING
- It is designed without looking at the code.
- Can be done by someone other than the implementer.
- Testing can be reused if implementation changes.
- Paths through specification (docstring)
GLASS BOX TESTING
- Code is used directly to guide design of the test cases
- Testing cannot be reused if implementation changes
- Explores paths through the code
- It is called path-complete if every potential path through the code is tested at least once
Bisection/binary search
divide and conquer
- list MUST be sorted to give correct answer
- linear search => O(n)
- binary search => O(log n)
(assumes the list is sorted!)
Monkey Sort
aka bogosort - stupid sort - slowsort - permutation sort - shotgun sort
is a random sort, every time through the list get randomly sorted and if lucky it is ordered!
Monkey Sort - complexity
Best case:
O(n) where n is len(L)
Worst case:
O(?) is unbound if really unlucky
LOGIC OPERATORS ON bools (a and b)
not a -> True if a is False
False if a is True
a and b -> True if both are True
a or b -> True if either or both are True
Syntax
arrangement of words and phrases to create will-formed sentences in a language.
Static semantics
whether syntactically valid string has any meaning
Tuples
ordered sequence of elements, can mix element types.
represented with Parentheses
Immutable (cannot change element values)
Lists
ordered sequence of information, accessible by index.
represented by Square brackets
mutable
class Deque(): a_list.append(item) insert a_list.insert(i,item) pop a_list.pop() pop a_list.pop(i) sort a_list.sort() reverse a_list.reverse() del del a_list[i] index a_list.index(item) count a_list.count(item) remove a_list.remove(item)
append a_list.append(item) – Adds a new item to the end of a list
insert a_list.insert(i,item) – Inserts an item at the 𝑖th position in a list
pop a_list.pop() – Removes and returns the LAST item in a list
pop a_list.pop(i) – Removes and returns the 𝑖th item in a list
sort a_list.sort() – Modifies a list to be sorted
reverse a_list.reverse() – Modifies a list to be in reverse order
del del a_list[i] – Deletes the item in the 𝑖th position
index a_list.index(item) – Returns the index of the first occurrence of item
count a_list.count(item) – Returns the number of occurrences of item
remove a_list.remove(item) – Removes the first occurrence of item
- what is the output when print(office == home) in which __eq__ not specified
- what is the output when print(workstation.set_brand(‘DELL’))
- As __eq__ not specified, python checks if both refer to same object and since two different calls of classes => False is the output
- When try to simultaneously call for two procedural attributes, output is None (except special operators like __add__; and dot notations like self.age())
Overall complexity? def genSubsets(L): \_\_\_smaller = genSubsets(L[:-1]) \_\_\_for small in smaller: \_\_\_\_\_\_new.append(small+extra)
Know that for a set of size k there are 2^k cases. So overall complexity O(2^k) – exponential
Overall complexity? def isSubset(L1, L2): \_\_\_for e1 in L1: \_\_\_\_\_\_matched = False \_\_\_\_\_\_\_\_\_for e2 in L2: \_\_\_\_\_\_\_\_\_\_\_\_if e1 == e2: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_matched = True \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_break \_\_\_\_\_\_\_\_\_\_\_\_if not matched: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_return False \_\_\_\_\_\_\_\_\_return True
nested loops, each iterating n times. So O(n^2)
O(1) O(log n) O(n) O(n * log n) O(n^c) O(c^n)
O(1) – code does not depend on size of problem
O(log n) – reduce problem in half each time through process
O(n) – simple iterative or recursive programs
O(n * log n) – merge sort
O(n^c) – nested loops or recursive calls
O(c^n) – multiple recursive calls at each level
Big O() – growth of program’s run time as input size grows
- Stack()
- push(item)
- pop()
- peek()
- is_empty()
- size()
- Stack() – creates a new stack that is empty. It needs no parameters and returns an empty stack.
- push(item) – adds a new item to the top of the stack. It needs the item and returns nothing.
- pop() – removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
- peek() – returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
- is_empty() – tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
- size() – returns the number of items on the stack. It needs no parameters and returns an integer.
What are the outputs?
a = '05'
print(a[1] == 5)
print('5'== 5)
print('aba'==5)False
False
False
- BinaryTree()
- get_left_child()
- get_right_child()
- set_root_val(val)
- get_root_val()
- insert_left(val)
- insert_right(val)
- BinaryTree() – creates a new instance of binary tree.
- get_left_child() – returns the binary tree corresponding to the left child of the current node.
- get_right_child() – returns the binary tree corresponding to the right child of the current node.
- set_root_val(val) – stores the object in parameter val in the current node.
- get_root_val() – returns the object stored in the current node.
- insert_left(val) – creates a new binary tree and installs it as the left child of the current node.
- insert_right(val) – creates a new binary tree and installs it as the right child of the current node.
Overall complexity? def f(x): \_\_\_assert type(x)==int and x>=0 \_\_\_answer = 0 \_\_\_s = str(x) \_\_\_for c in s: \_\_\_\_\_\_answer += int(c) \_\_\_return answer
def intToStr(i): \_\_digits = '0123456789' \_\_if i == 0: \_\_\_\_return '0' \_\_res = '' \_\_while i > 0: \_\_\_\_res = digits[i%10] + res \_\_\_\_i = i//10 \_\_return result
x/i is a integer!
overall complexity is O(log(n)) where n is the number of digits ( len(str(i)) = log(n) where n = 10^(# of digits))
Overall complexity? def addDigits(s): \_\_val = 0 \_\_for c in s: \_\_\_\_val += int(c) \_\_return val
s is a string!
overall complexity is O(n) where n=len(s)
Overall complexity of:
fibonacci iterative
fibonacci recursive
for loop, so O(n)
recursion, so O(2^n); but when use dictionary also becomes O(n) as number of iterations is 2*n-3
Insertion sort
The insertion sort always maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger.
Overall complexity is O(n^2)
