B1, B2.2
Four concepts of computational thinking.
decomposition, pattern recognition, abstraction, algorithmic design
An integer that represents the position in a data structure
Index
Construct code read all the lines of a file into a list.
file = open("data.txt", "r")
lines = file.readlines()
Space complexity of Bubble Sort and Selection Sort
O(1)
Identify an application of recursion
Merge sort, tree traversal, fractal images, file traversal
To follow and record effects of an algorithm
tracing
The process of repeating steps
iterating
Construct a function in code for linear search.
def linear_serach(alist, target):
for x in alist:
if x == target:
return True
return False
Define a logical error.
Program compiles/runs, but does something you don't want it to do.
An possible error caused by recursion
stack overflow
traversing
Time complexity of binary serach
O(log n)
Finish the code for bubble sort.
for i in range(len(alist)-1):
for j in range(len(alist)-i-1):
# FINISH THE CODE
for i in range(len(alist)-1):
for j in range(len(alist)-i-1):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
Scalability of an algorithm it as the data size increases.
Define a balanced binary search tree.
The height of the left and right subtrees differ by at most one
State an advantage of dynamic data structures
flexibility; efficient memory usage;
sorted
Finish the code for selection sort.
for i in range(len(alist)):
min_index = i
for j in range(i+1, len(alist)):
#FINISH THE CODE
for i in range(len(alist)):
min_index = i
for j in range(i+1, len(alist)):
if mylist[j] < mylist[min_index]:
min_index = j
mylist[i], mylist[min_index] = mylist[min_index], mylist[i]
multiple threads are blocked because they are waiting for each other
This traversal method is best for copying a tree
Preorder Traversal
Define a static data structure
- Fixed size that cannot change
- Memory allocated at compile time
Best case time complexity of bubble sort
O(n)
Construct the code for binary search
binary_search(alist, target_value):
min = 0
max = len(alist) - 1
while min <= max:
mid = (min + max) // 2
if target_value == alist[mid]:
return True
elif alist[mid] < target_value:
min = mid + 1
elif alist[mid] > target_value:
max = mid - 1
return False
The formal definition of what a system must do before any design or coding begins.
problem specification
Describe the process of deleting a node with one child.
Get the parent of the node to delete. Set the parent's child node to node to delete's child.