IT279: Algorithm and Data Structures Recap 1/3

Course Contents from IT279 Syllabus of Illinois State University

Recursion Review

what is the output of this program?

#include <iostream>
using namespace std;

int mysteryFunc(int num1,int num2)
{
    
    if (num1 == 0)
        return num2;
    else
        return mysteryFunc(num1 / 10,num2*10+num1%10);
}
 
int main()
{
    cout << mysteryFunc(1234,5)<<endl;
}

 

 

answer: 54321

 

C++ Review, Dynamic Memory Management

What is a memory leak?

- Losing track of dynamically allocated memory so that it is not freed or deallocated.

- 메모리 누수란, 동적으로 할당된 메모리를 추적하지 못해 해당 메모리가 해제되거나 할당 해제되지 않는 상황

 

What is a dangling pointer?

- A pointer that points at memory that has already been freed (or deallocated).

- 이미 해제된 메모리를 가리키는 포인터

 

What is the purpose of a destructor in C++?

- To free any dynamically allocated memory that the object uses before the object itself is deallocated.

- 객체가 할당 해제되기 전에 객체가 사용하는 모든 동적으로 할당된 메모리를 해제하는 것

 

Avoiding Buffer Overflow

buffer overflows are a critical class of vulnerabilities that arise from improper handling of memory buffers, often leading to security breaches and system instability. Proper coding practices and modern security mechanisms are essential to prevent such vulnerabilities.

버퍼 오버플로우는 메모리 버퍼를 부적절하게 다루어 발생하는 중요한 취약점 유형으로, 보안 위반과 시스템 불안정성을 초래할 수 있습니다. 취약점을 방지하기 위해서는 적절한 코딩 관행과 현대의 보안 메커니즘을 사용하는 것이 필수적입니다.

 

Algorithm Analysis

In order from Lowest to Highest

O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)

 

The actual running time of a given function is determined by the expression 3n + 4 + 5n^2.

What is the Big-Oh notation that accurately describes the function?

O(n^2)

 

// What is the complexity of the following code segment:

for (int i = 0; i < n; i++)
{ 
  for (int j = 0; j < n; j++)
  { 
    cout << "I am a loop" << endl; 
  } 
  for (int k = 0; k < n; k++)
  { 
    cout << "I am also a loop" << endl; 
  } 
}

Answer: O(n^2)

 

Lists, Stacks, Queues

// Assume you have the following C++ Node class:

class Node
{
public:
    int dataVal;
    Node* next;

    Node(int data = 0; Node* next = nullptr) : dataVal(data), next(next) {}
};
// Which of the following correctly creates a new node with the value 6 and inserts it at the front of a list? Assume the variable head points to the beginning of the list.

Node* temp = new Node(6, head);

head = temp;

 

List:
Description) A list is a collection of elements, where each element has a position in the sequence. Lists can be of any length and elements can be added or removed from any position.
Operations)
- Insert: Adds an element at a specified position.
- Delete: Removes the element at a specified position.
- Find: Retrieves an element by its position or value.
- Size: Returns the number of elements in the list.
Variants) Single-linked list, double-linked list, etc.

Stack:
Description) A stack is a collection of elements with a Last-In-First-Out (LIFO) structure. The last element added is the first one to be removed.
Operations)
- Push: Adds an element to the top of the stack. O(1)
- Pop: Removes and returns the top element of the stack. O(1)
- Top: Returns the top element without removing it. O(1)
- IsEmpty: Checks if the stack is empty.

Use Cases) Undo mechanisms in applications, function call management in programming, etc.

Queue:
Description) A queue is a collection of elements with a First-In-First-Out (FIFO) structure. The first element added is the first one to be removed.
Operations)
- Enqueue: Adds an element to the end of the queue. O(1)
- Dequeue: Removes and returns the first element of the queue. O(1)
- Front: Returns the first element without removing it. O(1)
- IsEmpty: Checks if the queue is empty.
Variants) Circular queue, priority queue, etc.

 

 

Data Structure

Abstract data types(ADT)

- an ADT does not include implementation-specific details such as a head pointer for a stack (which could be implemented as either an array or a linked list).

- ADTs are always implemented as classes. (X) -> often, but they don't have to be.

- We can create an ADT for an integer.

- ADTs are not specific to any particular language.

 

Advanced Search Trees

BST(Binary Search Tree): subtree의 오른쪽은 더 크고 왼쪽은 더 작음 (a sorted dictionary implementation)

Operations: find, insert(as a leaf), remove(when the removing node has more than two children, replace with the largest subtree's node on the left side)

 

 

Height and depth of the search tree From Stack Overflow

Figure that I made using the textbook image

 

AVL Tree

- a self-balance Binary Search Tree

- Search is the same with BST

- With insertion, we must check balance factors and rotate once if out of balance

- With deletion, we must check balance factors and may have to rotate up to O(log n) times

balance factor: height of the left subtree - height of the right subtree

As long as it is -1, 0, or 1, all is well.

else, we rotate.

 

When we insert the node, check the bigger subtree side child of the node which is out of balance.

rotation: If a bigger subtree side of the child and the side previously checked are the same, we rotate

double rotation: if the sides are different we need to do double rotation.

 

Splay Tree

Insertion and deletion are the same as basic binary search trees

Search time: O(log n) to O(n)

But

When we search we will rearrange the tree so that

- O(n) searches will result in an improved tree structure

- Recently and very frequently accessed items will cluster toward the top of the tree

The structure changes will guarantee the m searches will take O(m log n) time as long as m is reasonably large.

 

Search: Find and rotate to the root.

using double rotation (zig-zig, zig-zag) and single rotation.

 

Splay trees have an amortized search cost of O(log n).

This means that If we do m searches, where m is sufficiently large, the average time to search will be O(log n) even though individual searches may take up to O(n) time.

 

Watch the videos of the AVL tree and Splay tree again (to get familiar yourself with rotations).

I could see the parent of the inserting node is moving first in AVL.

 

Hash Tables

Search(best case): O(1)

space concerns

- The array will have extra space.

 

Hash Function

- A function to convert a key to an appropriate index

- Typical hash function is "key mod table size": hash(key) = key % tableSize

-  Important to minimize collisions (to scatter values across the array)

- Table size should be prime

 

Handling Collisions

- make a linked list (Separate chaining): Search and deletion can end up being O(n), unpredictable space use

- Pick a different location (Open addressing)

     - linear probing: Deletion uses a 3-value flag(Empty(never used), In use now - search keeps going unless this is the item, Deleted - search keeps going; we can insert here), prone to clumping.

     - Quadratic Probing (to reduce the clumping of linear probing): The first collision ends up 1 away from the original hash index, the second -> 2^2 away, nth collision -> n^2 away

     - Offset from the current location:

currentLocation <- (currentLocation + offset) mod tableSize

offset <- offset + 2

     - Double Hashing: The second hash function computes an offset, not a location!

 

Priority Queue / Heaps

Insertion, Deletion, Heapify: O(log n)

Find Min/Max: O(1)

Not FIFO.

Percolate Up: it occurs when inserting.

Percolate Down: it occurs when deleting. buildHeap: heapify O(n)

 

Elementary Sorts

Insertion Sort(divide list into 2 parts: sorted and unsorted)- best(sorted): O(n), always better than bubble sort, stable

Selection Sort(find smallest item, swap with the first item in the array) - best: O(n^2), unstable

Bubble Sort(sort neighbors, the last element is sorted in each stage) - best(sorted): O(n), stable

worst for all - O(n^2)