algorithms

avatar
Created by
Abi

Cards (26)

  • What are the two searching algorithms we are required to know?
    Binary
    Linear
  • What is a search algorithm?

    Algorithm to find a specified element in a data structure
  • Describe the binary search
    Algorithm that finds the middle element in the list, evaluates where the elements general location is based on if the element should be higher or lower than the list at that point, the process continues until the element is found
  • What is the primary condition needed to conduct a binary search?
    Data structure has to be sorted
  • What is the time complexity of a binary search?
    O(log n)
  • What does the pseudocode look like for a binary search?
    lower = 0
    higher = array.length -1
    while lower <= higher
    mid = (low + high) / 2
    if array[mid] == value;
    return mid
    elif array[mid] > value;
    higher = mid - 1
    else
    lower = mid - 1
    end if
    end while
    return "value not in list"
  • Describe a linear search

    Most basic searching algorithm, goes in order through the list to find the value
  • What is the time complexity of a linear search?
    O(n)
  • What does the pseudocode look like for a linear search?

    i = 0
    while i < array.length
    if array[i] == value;
    return i
    else
    i ++
    endif
    endwhile
    return "value not found"
  • What are sorting algorithms?
    Algorithms that take elements and output them in a logical order
  • Describe a bubble sort

    Algorithm that makes comparisons and swaps between element pairs, the elements are arranged in a pre-set way (ascending or descending)
  • What does the noSwap variable do in a bubble sort?

    Evaluates when a swap is made, if a pass is made with no swap, the algorithm terminates
  • What is the time complexity of a bubble sort?
    O(n^2)
  • Describe an insertion sort

    Starts at it's second element and compares it to the element at it's left, if the elements are in the wrong order, the smaller element is placed in the lower position, the index increments until the end of the list
  • What does the pseudocode for an insertion sort look like?
    for i = 1 to array.length - 1
    element = array[i]
    j = i - 1
    while j > 0 and array[j] > element
    array[j+1] = array[j]
    j = j - 1
    array[j+1] = element
  • What is the time complexity of an insertion sort?
    O(n^2)
  • What are the two algorithms associated with stacks?
    pop
    push
  • What pointers are included in the algorithms for stacks?

    Single pointer, keeps track of the top of the stack
  • How do you add a new item to a stack?
    push algorithm, the item must be passed as a parameter first
  • How do you remove an item from a stack?
    pop algorithm, the element at the position of the top pointer must be recorded first before being removed
  • What does the pseudocode for a push look like?

    if top == MAXSIZE
    print("Stack is full")
    else
    top = top + 1
    arrstack[top] = value
    endif
  • What does the pseudocode for the pop algorithm look like?
    int rtnValue = -1
    if top < 0 then
    print("Stack is empty")
    else
    rtnValue = arrStack[top]
    top = top - 1
    endif
    return rtnValue
  • What are the two algorithms associated with queues?
    enqueue
    dequeue
  • What does the pseudocode for an enqueue look like?
    if size == MAXSIZE then
    print("Queue is full")
    else
    size = size + 1
    rear = (rear + 1) MOD MAXSIZE
    arrQueue[rear] = value
    endif
  • What does the pseudocode of a dequeue look like?

    int rtnValue = -1
    if size == 0
    print("Queue empty")
    else
    rtnValue = arrQueue[front]
    front = front + 1
    size = size - 1
    endif
    return rtnValue
  • Bubble sort pseudo code

    for j < data.length - 2
    swapped = true
    while(swapped)
    swapped = false
    for i = 0 to j
    if data[i] > data [i + 1]
    data (i) = temp
    data(i) = data(i+1)
    data(i+1) = temp
    end if
    end for
    j = j -1
    endwhile
    return data