Prelims Reviewer - Data Structures and Algorithm

Data Structure

Particular way of storing and organizing data in a computer so that it can be used efficiently

Data Structure

Based on the ability of a computer to fetch (retrieve) and store data at any place in its memory, specified by an address

Address

Bit string that can be itself stored in memory and manipulated by the program

Data Structure

Requires writing a set of procedures that create and manipulate instances of that structure

Data Structure Types

• Primitive (ex. int, char)

• Non-Primitive (ex. Array, Vector)

Data Structure Classification (Element)

• Homogenous (Singular type, ex Array)

• Heterogenous (Multiple type, ex Structure)

Data Structure Classification (Size)

• Static (Immutable, ex. matrix)

• Dynamic (Mutable, ex. list)

Data Structure Classification (Relationship)

• Linear (ex. array)

• Non-Linear (ex. tree)

Main Memory (RAM)

• Where instructions (programs and data are stored

• Volatile

Cache Memory

• Used to store frequently used instructions and data that either is, will be, or has been used by the CPU

• Fastest access speed

Register

• Segment of CPU Cache

• Small amount of memory that is used to temporarily store instructions and data

Persistent Storage

• Used to store instructions and data in external devices such as a hard disk

• Non-volatile, commonly used by the operating system as virtual memory

• Slowest access speed

Reserving Memory

• Data is stored in memory and manipulated by various data structure techniques

• Organized into groups of eight bits called a byte, enabling 256 combinations of zeroes and ones that can store numbers from 0 through 255

• Before storing, tell the computer how much space to reserve for data using an abstract data type

Abstract Data Type

Keyword of a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location

Abstract Data Type Examples

• Java ADT

• C & C++ ADT

Data Type Groups

• Integers

  • byte - 8

  • short - 16

  • int - 32

  • long - 64

• Characters

  • char - 16 (Unicode)

• Floating-Point

  • float - 32

  • double - 64

• Boolean

  • bool - 1

Algorithm

Step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output

Algorithm Categories

• Search

• Sort

• Insert

• Update

• Delete

Algorithm Characteristics

• Unambiguous

• Input

• Output

• Finiteness

• Feasibility

• Independent

Algorithm Analysis Types

• Priori

• Posterior

Priori Analysis

Efficiency of an algorithm is measured by assuming that all other factors are constant and have no effect on the implementation

Posterior Analysis

Analysis where actual statistics like running time and space required, are collected

Algorithm Complexity Factors

• Time factor

• Space factor

Algorithm Complexity f(n)

Gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data

Space Complexity

Represents the amount of memory space required by the algorithm in its life cycle

Space Complexity Parts

• Fixed part

• Variable part

Time Complexity T(n)

• Amount of time required by the algorithm to run to completion

• Measured as the number of steps, provided each step consumes constant time

Asymptotic Analysis

Defines the mathematical foundation/framing of its run-time performance

Asymptotic Analysis

Used to conclude the best case, average case, and worst-case scenario of an algorithm

Asymptotic Analysis

Computes the running time of any operation in mathematical units of computation

O Notation

Worst-case time complexity

Ω Notation

Best-case time complexity

θ Notation

Average-case time complexity

Common Asymptotic Notation

• Constant - O(1)

• Logarithmic - O(log n)

• Linear - O(n)

• n log n - O(n log n)

• Quadratic - O(n²)

• Cubic - O(n³)

• Polynomial - n^O(1)

• Exponential - 2^O(n)

Rate of Growth

How fast a function grows with input size

Data Abstraction

• Simplify code by displaying only essential details to the user

Interface

• Special block containing method signatures

• Defines method signatures without body

• Defines standard and public specification of class behavior

• Allows classes, regardless of hierarchy, to implement common behaviors

• May exhibit polymorphism

Abstract Class

• Declared using “abstract”

• No implementation

• None, abstract, and/or concrete methods

Abstract Method

• Redefined in subclass

• Always overridden

• Container class must be declared with “abstract”

• No object

Interface vs Abstract Class

• Interface

  • Methods have no body

  • Define constants

  • No direct inheritance

Tree

Which of the following is NOT a linear data structure?

Hiding implementation details and showing essential features

Abstraction in data structures means:

ArrayIndexOutOfBoundsException

What happens if you access an index of an array that is out of bounds in Java?

Abstract classes can have implemented methods, but interfaces cannot

In Java, which of the following statements about abstract classes and interfaces is true?

It reduces complexity by hiding implementation details

How does abstraction improve software development processes?

30

It initializes an array with 5 elements

[0, 2, 4, 6, 8]

It limits the number of iterations based on the array length

The loop would access an invalid index

System.out.print(numbers[i] + " ");

Type

Integer is a primitive, while Array is a non-primitive. Under which classification of data structures does this fall?

1 2 3 4 5

True

An algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.

False

To implement a data structure, it requires writing set of array that create and manipulate instances of that structure.

Interfaces

In Java, which of the following can be used to implement multiple inheritance?

abstract void methodName();

Which of the following is the correct way to declare an abstract method in Java?

HU/M*ILI^-TY^+

CONVERT FROM INFIX TO POSTFIX:

H / U * M - (I ^ L I) + T ^ Y

CO+M-P*UTE^/R-

CONVERT FROM INFIX TO POSTFIX:

(C + O - M) * P / (U ^ T E) - R

((A+B)+(((C+(D*E))/(F-G))+H))

CONVERT FROM POSTFIX TO INFIX:

A B + C D E * + F G - / H ++

ArrayList

• Part of collection framework and is present in java.util package

• Provides a dynamic way of manipulating data

• Slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed

ArrayList Characteristics

• Inherits AbstractList class and implements List interface

• Initialized by size, however, the size can increase if collection grows or shrunk if objects are removed from the collection

• Allows random list access

• Use a wrapper class if an ArrayList can not use primitive types, like int, char, etc.

• Similar to a vector in C++

ArrayList Constructors

• ArrayList() - empty array list

• ArrayList(Collection c) - initialized with the elements from collection c

• ArrayList(int capacity) - initial capacity being specified

ArrayList Methods

• add(int index, Object element)

• add(Object o)

• addAll(Collection C)

• addAll(int index, Collection C)

• clear()

• clone()

• contains? (Object o)

• ensureCapacity?(int minCapacity)

• forEach?(Consumer<? super E> action)

• get?(int index)

• indexOf(Object O)

• isEmpty?()

• lastIndexOf(Object O)

• listIterator?()

• listIterator?(int index)

• remove?(int index)

• remove?(Object o)

• removeAll?(Collection c)

• removeIf?(Predicate filter)

• removeRange?(int fromIndex, int toIndex)

• retainAll?(Collection<?> c)

• set?(int index, E element)

• size?()

• spliterator?()

• subList?(int fromIndex, int toIndex)

• toArray()

• toArray(Object[] O)

• trimToSize()

add(int index, Object element)

Insert a specific element at a specific position index in a list

add(Object o)

Append a specific element to the end of a list

addAll(Collection C)

Append all the elements from a specific collection to the end of the mentioned list

addAll(int index, Collection C)

Insert all of the elements starting at the specified position from a specific collection into the mentioned list

clear()

Used to remove all the elements from any list

clone()

Used to return a shallow copy of an ArrayList.

contains? (Object o)

Returns true if this list contains the specified element.

ensureCapacity?(int minCapacity)

Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument

forEach?(Consumer<? super E> action)

Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception

get?(int index)

Returns the element at the specified position in this list

indexOf(Object O)

The index the first occurrence of a specific element is either returned or -1 in case the element is not in the list

isEmpty?()

Returns true if this list contains no elements

lastIndexOf(Object O)

The index of the last occurrence of a specific element is either returned or -1 in case the element is not in the list

listIterator?()

Returns a list iterator over the elements in this list (in proper sequence)

listIterator?(int index)

Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list

remove?(int index)

Removes the element at the specified position in this list

remove?(Object o)

Removes the first occurrence of the specified element from this list, if it is present

removeAll?(Collection c)

Removes from this list all of its elements that are contained in the specified collection

removeIf?(Predicate filter)

Removes all of the elements of this collection that satisfy the given predicate

removeRange?(int fromIndex, int toIndex)

Removes from this list all of the elements whose index is between fromIndex, inclusive, and toIndex, exclusive

retainAll?(Collection<?> c)

Retains only the elements in this list that are contained in the specified collection

set?(int index, E element)

Replaces the element at the specified position in this list with the specified element

size?()

Returns the number of elements in this list

spliterator?()

Creates a late-binding and fail-fast Spliterator over the elements in this list

subList?(int fromIndex, int toIndex)

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive

toArray()

This method is used to return an array containing all of the elements in the list in the correct order

toArray(Object[] O)

It is also used to return an array containing all of the elements in this list in the correct order same as the previous method

trimToSize()

This method is used to trim the capacity of the instance of the ArrayList to the list’s current size

Stack

• Way to group things together by placing one thing on top of another and then removing things one at a time from the top

• Last-In, First-Out

push()

Adds to the top of the list

pop()

Removes an item from the top of the list and returns this value to the caller

Stack

Restricted data structure because only a small number of operations are performed on it

Stack

Linear data structure that follows a particular order in which the operations are performed

Stack

Extends Vector which implements the List interface

Stack Hierarchy