Deck 1

Question 1

Linear Structures

Answer 1

Data structure that is thought of having two ends, left and right or sometimes front and rear. Top and bottom. Distinguished by how data is added and removed.

Question 2

stack

Answer 2

push-down stack. top to base linear data structure. LIFO. For example, every web browser has a Back button. As you navigate from web page to web page, those pages are placed on a stack (actually it is the URLs that are going on the stack).

Question 3

Stack Code

Answer 3

class Stack:
  def \_\_init\_\_(self):
      self.stack = []

  def push(self, value):
      return self.stack.append(value)

  def pop(self):
      if self.is_empty():
          return None
      else:
          return self.stack.pop()

  def peak(self):
      if self.is_empty():
          return None 
      else:
          return self.stack[-1]

  def size(self):
      return len(self.stack)

  def is_empty(self):
      return self.size() == 0

Question 4

Queue Code

Answer 4

class Queue:
    def \_\_init\_\_(self):
        self.queue = []

    def enqueue(self, val): # critical differnce between stack and queue
        self.queue.insert(0,val)

    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop()

    def size(self):
        return len(self.dequeue)

    def is_empty(self):
        return self.size() == 0

Question 5

Binary Search Code

Answer 5

class BinarySearch(alist, val):
    if len(alist) == 0:
        return False 
    else:
        midpoint = len(alist)//2
        if val == alist[midpoint]:
            return True
        else:
            if val < alist[midpoint]:
                return BinarySearch(alist[:midpoint], val)
            else:
                return BinarySearch(alist[midpoint+1:], val)

Question 6

Queue Data Structure

Answer 6

FIFO. front to rear. basically every line you can think of. Common function are insert(queue) or pop(dequeue)

Question 7

Hash Table Get Function

Answer 7

def hashFunction(self, key, size):
        return key%size

    def rehash(self, oldhash, size):
        return (oldhash+1)%size 

def get(self, key):
startingslot = self.hashFunction(key, len(self.slots))
data = None
stop = False
found = False
position = startingslot
while self.slot[position] != None and not stop and not found:
if self.slot[position] == key:
found = True
data = self.data[position]
else:
position = self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data

Question 8

Hash Table put function

Answer 8

def hashFunction(self, key, size):
        return key%size

def rehash(self, oldhash, size):
        return (oldhash+1)%size 

def put(self,key,data):
      hashvalue = self.hashfunction(key,len(self.slots))

  if self.slots[hashvalue] == None:
    self.slots[hashvalue] = key
    self.data[hashvalue] = data
  else:
    if self.slots[hashvalue] == key:
      self.data[hashvalue] = data  #replace
    else:
      nextslot = self.rehash(hashvalue,len(self.slots))
      while self.slots[nextslot] != None and \
                      self.slots[nextslot] != key:
        nextslot = self.rehash(nextslot,len(self.slots))

      if self.slots[nextslot] == None:
        self.slots[nextslot]=key
        self.data[nextslot]=data
      else:
        self.data[nextslot] = data #replace

Question 9

Deque

Answer 9

Deques are data structures that allow hybrid behavior like that of stacks and queues. Double-ended queue order collection. allow for LIFO and FIFO mixture of stack and queue
adding an removing from the front is O(1) whereas adding or removing from the end is O(n)

Question 10

Deque code

Answer 10

class Deque:
    def \_\_init\_\_(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

Question 11

Linked List

Answer 11

Unordered list. The location of the next item is stored in the item so the relative position doesn’t matter. First item is know as the head. Basic building block is a node. Node will contain data and the next node reference. None indicates there is no next node.

Question 12

Node function names

Answer 12

__init__, getData, getNext, setData, setNext

Question 13

Node Code

Answer 13

class Node:
    def \_\_init\_\_(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

Question 14

UnorderedList functions

Answer 14

__int__, isEmpty O(1), add O(n), size O(n), search O(n), remove O(n)

Question 15

UnorderList Code

Answer 15

class Node:
    def \_\_init\_\_(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

class UnorderedList:

    def \_\_init\_\_(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()

    return count

def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()

    return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

mylist = UnorderedList()

Question 16

ordered list add function

Answer 16

def add(self,item):
    current = self.head
    previous = None
    stop = False
    while current != None and not stop:
        if current.getData() > item:
            stop = True
        else:
            previous = current
            current = current.getNext()

    temp = Node(item)
    if previous == None:
        temp.setNext(self.head)
        self.head = temp
    else:
        temp.setNext(current)
        previous.setNext(temp)

Question 17

Stack Functions

Answer 17

The fundamental operations for a stack are push, pop, and isEmpty.

Question 18

Queue Functions

Answer 18

The fundamental operations for a queue are enqueue, dequeue, and isEmpty.

Question 19

Recursion

Answer 19

a method of solving a problem by breaking it down into smaller pieces. Usually calls itself.

Question 20

3 laws of recursion

Answer 20

A recursive algorithm must have a base case.
A recursive algorithm must change its state and move toward the base case.
A recursive algorithm must call itself, recursively.

Question 21

Sequential search

Answer 21

O(n) for ordered and unordered lists. Check each value along the way.

Question 22

binary Search

Answer 22

O(log n) half the list each time and go to the half the item belongs in

Question 23

hash table

Answer 23

constant time searching or O(1) the idea is that if you give me an item i can use the hash function to find its location in the hash table. Collison resolution aside

Question 24

remove punctuation and split words from string

Answer 24

[word.strip(string.punctuation) for word in data.split()]

Question 25

difference of two vectors code

Answer 25

def inner_product(d1, d2):
    sum = 0.0
    for word in d1:
        if word in d2:
            sum += d1[word]* d2[word]
    return sum

def angle_difference(d1, d2):
    numerator = inner_product(d1, d2)
    denominator = math.sqrt(inner_product(d1, d1)* inner_product(d2, d2))
    return math.acos(numerator/denominator)

Question 26

Count word occurrence from document code

Answer 26

def count_word(d):
    count = {}
    for word in d:
        if word in count:
            count[word]+=1
        else:
            count[word] = 1
    return count

Question 27

merge sort

code

Answer 27

O(n)

def merge_sort(alist):
    if len(alist)>1:

    half = len(alist) //2 # split the deck
    lefthalf =alist[:half]
    righthalf = alist[half:]
    print("halves", lefthalf, righthalf)
    left = merge_sort(lefthalf) # recursive call on the left side
    right = merge_sort(righthalf) # recursive call on the right side

    i=0
    j=0
    k=0
    while i < len(lefthalf) and j < len(righthalf): # while the indexes are less than the length
        if lefthalf[i] < righthalf[j]: # if left is less than right
            alist[k]=lefthalf[i] # add the left to the sorted list
            i=i+1
        else:
            alist[k]=righthalf[j]
            j=j+1
        k=k+1

    while i < len(lefthalf):
        alist[k]=lefthalf[i]
        i=i+1
        k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [20,14,1,3,2,7,9,6,4]

x = merge_sort(alist)

Question 28

merge sort

Answer 28

divide the list down to prime left and prime right then reassemble the list based on which is bigger.
Recursive formula with O(n)

Question 29

implement an algorithim to test if a string is unique

Answer 29

def unique(string):
    # Assuming character set is ASCII (128 characters)
    if len(string) > 128:
        return False

    char_set = [False for _ in range(128)] # create False spots for possible characters
    for char in string: # character by character 
        val = ord(char) # get the positional value 
        if char_set[val]: # if you have already added that positional value it is not unique
            # Char already found in string
            return False
        char_set[val] = True # otherwise add it

return True # if you make it through the list it is unique

Question 30

Heap code

Answer 30

class BinHeap:
    def \_\_init\_\_(self):
        self.heapList=[0] # intialize a list at 0
        self.currentSize = 0 # size at zero

'''
given i i//2 is the left child, i//2+1 is the right child
'''
def minChild(self,i):# so given a node return its smaller child
    if i*2+1> self.currentSize: #if there is no right child just return the left
        return i*2 # return the node
    else:
        if self.heapList[i*2]< self.heapList[i*2+1]: # if the child to the right is smaller return it
            return i*2
        else:
            return i*2+1 #otherwsie give me the left child

    def percDown(self, i):
        while (i*2)<= self.currentSize: # while staying on the current level
            mc = self.minChild(i) # find the lowest child
            print("Checking", self.heapList[i], self.heapList[mc])
            if self.heapList[i] > self.heapList[mc]:
                print("It was bigger flipping", self.heapList[i], self.heapList[mc])
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i= mc

def buildHeap(self, alist):
    i = len(alist) // 2 # start at n/2
    self.currentSize = len(alist) # Looking at the whole tree
    self.heapList = [0]+alist[:] # combined the heap list with the list
    while(i > 0):
        self.percDown(i)# swap nodes to achieve max heap
        i -=1

    def sort(self):
        result = []
        while self.currentSize >= 1:
            retval = self.heapList[1]
            self.heapList[1] = self.heapList[self.currentSize]
            self.currentSize =  self.currentSize -1
            self.heapList.pop()
            self.percDown(1)
            result.append(retval)
        return result

    def \_\_str\_\_(self):
        return str(self.heapList)