Midterm Melodrama – Data Structures with Java

CSC251 Study Guide

Midterm Melodrama


Index

  • Array Properties
    • overview
  • Stack Properties
    • overview
    • defintion
    • diagram
    • conceptual implementation
    • operations
  • Queue Properties
    • overview
    • defintion
    • diagram
    • conceptual implementation
    • operations
  • Stack Code & Algorithms

    uses arrays for implementation

    • is stack empty
    • is stack full
    • add to stack
    • delete from stack
    • print in order
    • find an element in stack
  • Comparing Stacks & Queues
    • overview
    • advantages
    • disadvantages
    • examples of how they can be used
  • Queue Algorithms

    uses arrays for implementation

    • shift queue
    • circular queues
  • [Basic Definitions & Phrases][section-defintions]

Array Properties

  • overview
    • fixed size
    • more efficient b/c it uses less memory
    • easier to manage
    • collection
    • linear
    • can add/remove at any position

Stack Properties

  • overview
    • example of a collection SDT
    • since stacks are lists, any list implementation will do
    • Last In, First Out data structure
    • can be implemented as an array
    • can only access the top
    • harder to manage b/c only top can be accessed
  • defintion
    • data structure of ordered items such that items can be inserted and removed only at 1 end (called the top)
  • diagram

  • conceptual implementation
    • First In, First Out (FIFO)
      • add to rear and remove from front
  • operations
    • push – adds item to stack
    • pop – deletes item from stack
    • peek – looks at top item in stack
    • size – returns # of elements in stack by examining top
    • isEmpty – tests for emptiness in stack by examining top

Queue Properties

  • overview
    • example of a collection SDT
    • operations: enqueue (add), dequeue (delete)
  • defintion
    • data structure of ordered items that can be inserted only at end (rear) and removed at other end (front)
  • diagram

  • conceptual implementation
    • First In, First Out (FIFO)
      • add to rear and remove from front
  • operations
    • enqueue – adds item to queue
    • dequeue – removes item from queue
    • first – looks at top item in stack – so front
    • size – returns # of elements in queue by examining top
    • isEmpty – tests for emptiness by examining top

Stack Code & Algorithms

isEmpty

int top = -1; //or 0
public boolean isEmpty () {
    return (top == -1);
}

isFull

public boolean isFull() {
    return (top == size-1);
}

add to stack

public void add (int element) {
    if (isFull() == true)
        System.out.println("Stack full, cannot add element.");
    else
        stack[++top] = element;
}
  1. check if stack is not full
  2. set top position of array to element being added to stack
  3. increment values of top and count (if partially filled array)

delete from stack

public int delete () {
    if (isEmpty() == true)
        System.out.println("Stack empty, cannot delete element.");
    else
        return stack[top--];
}
  1. check if stack is not empty
  2. decrement top
  3. set return value to top position of array

print in order

public void printOrder() {
    while(!isEmpty()) {
        int value = remove();
        System.out.print(value + " ");
    }
}

find an element in stack

public boolean find(int element) {
    System.out.print("Please enter element to find: ");
    element = keyboard.nextInt();
    for (int i = 0; i < size; i++) {
        if (stack[i] == element)
            return true;
    }
    return false;
}

Comparing Stacks & Queues

  • overview
    • stacks and queues are similar data structures
    • they’re different only by how an item is removed first
    • both can be implemented as arrays or linked lists
  • advantages
    • implementing a stack as an array is easy, but implementing a queue as an array is more difficult because you have to dequeue from front and enqueue at end
    • TL; DR
      • when you want to be able to add or remove values from any position, arrays are the way to go because any value can be accessed through indexes
  • disadvantages
    • main limitations of arrays is that they cannot be extended or shrunk so you want to use an array when you know your max upper limit
    • TL; DR
      • if you’re not sure how many values there will be in your data structure, then it’s better to not use an array and stick with a linked list (ergo, queues) because arrays always have a fixed size
  • examples of stacks
    • CD storage case
    • cafeteria tray
    • batteries in a flashlight
    • cars in a single car garage
    • Towers of Hanoi
  • examples of queues
    • waiting line for a roller coaster
    • hamburger processing line at Mickey D’s
    • vehicles on a toll bridge
    • luggage checking machine
    • phone answering system for most big tech companies

Queue Algorithms

  • shift queues
    • enqueue operation
      1. save value at first index to item you want to enqueue
      2. increment size
      3. if array fills up, all n elements have to be copied to a new, larger array
    • dequeue operation
      1. save value at first index
      2. shift all elements left
      3. decrement size
  • circular queues
    • advance queue indexes front (to delete an item) and back (to insert an item) by moving them both clockwise around array


Basic Definitions & Phrases

  • abstract data type

    taken straight from the textbook

    • a data structure is the underlying programming construct used to implement a collection
  • abstractions
    • ignores or hides certain details at certain times, e.g. collection is abstraction where details of implementation are hidden
  • “abstract” in abstract data type
    • means that there are many different ways of implementing data type
  • algorithm
    • step by step instructions on how to execute a program or set of instructions
  • data structure
    • memory structure with associated representation mapping, e.g. a collection is a type of data structure that acts as an object that gathers & organizes other objects
  • a data type is specified by describing both
    • its set of values & operations used for implementation
  • implementing an abstract data type proceeds in 2 stages
    • declaring necessary variables of data types
    • writing methods & procedures to implement operations of data for given data types

TO NOTE

Although stack and queues have been implemented using an array – these ADTs are not accessed as an array.

No actual code for a queue on this test; but you should be able to write an algorithm to demonstrate the concept of a queue.


Tips or Tricks?

Contact me @fvcproductions

Coding Interview Tips and Tricks

tumblr_nd30ogjKdp1qcrg73o1_500

So I decided to compile a bunch of fun interview topics of interest and questions. This will be updated as I myself learn more about the whole proceess.


So For Those Who Are Looking Forward To Technical Interviews For Software Developer Internships…

Here we go! :grin:


Overview


General Topics Covered

  • hash maps
  • heaps
  • reverse linked lists
  • arrays vs hash
  • bit manipulation
  • string manipulation

Sample Technical Q’s

  • Write code to test the endianness of a code. Optimitize this code to fit 1 line.
  • Write code to print all the factors of a given number.
  • What is the definition of RAM?
  • What is the keyword volatile used for?
  • When is the autorelease pool flushed?
  • What techniques can be used to design a spam filter?
  • What features should so and so server provide?

Sample Personal Q’s

  • What makes you most interested in this company? (AH DERP)
  • Describe yourself.
  • What is your largest problem with this company or its software?
  • How often do you code?
  • Have you worked on projects outside of class? If so, why?

Questions to Ask Your Interviewer

  • How much of your day do you spend coding?
  • How many meetings do you have every week?
  • How does project planning happen on the team?
  • What is the ratio of software developers to program managers or what is the student to mentor ratio?
    • What is the interaction between them like?
  • Were you ever an intern yourself?

Tips or tricks?

Tweet me at @fvcproductions!

TI-89 TitaniumTricks for Calculus II

  • find terms of a sequence

seq(2^n/n!, n, 1, 10)

  • summation function

∑ ((2^k + 5)/3^k, k , 0 , 4)

  • ratio test

Define a(x) = 2^x+5/3^x
limit (a(x+1)/a(x), k, ∞)

  • basic convergence

limit (((n+1)/(n))^n, n, ∞)

  • taylor series

taylor(expression, var, order)

e.g. taylor(e^x, x, 2) = (x^2)/2 + x + 1