1 of 31

Presented by�Guang Hu

2 of 31

DISCLAIMER

This workshop is not officially endorsed by the university or the teaching staff and may not fully reflect the assessable subject content. Any tutors that participate in this workshop have verbally chosen to do so voluntarily and are not expected to represent the teaching team.

3 of 31

4 of 31

TOC

General exam advice

Data structures

Sorting algorithms

Graphing algorithms

Q+A

Practice questions

5 of 31

General exam advice

  1. Practice performing all algorithms
    1. Goal: What makes a given algorithm unique or different to another? What is special about it?
  2. Learn the flow of all algorithms
  3. Practice writing C problems untimed and timed
  4. Do the Canvas practice exam, writing code in Canvas is challenging :(
  5. Implement each data structure

6 of 31

Data structures

Concrete data structures:

  1. Array
  2. Dynamic Array
  3. Linked List
  4. BST
  5. Hash Table
  6. Heap

Abstract data structures:

  1. Dictionary
  2. Stack
  3. Queue
  4. Priority Queue
  5. Graph

Algorithms:

  1. Sorting
    • Selection Sort
    • Insertion Sort
    • Quick Sort
    • Merge Sort
    • Heap Sort
    • Distribution Counting
  2. Traversal
    • Breadth First Traversal
    • Depth First Traversal
    • Dijkstra
      • Bellman-Ford
      • Floyd-Warshall
  3. Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Iterative Width (IW)
    • Uniform Cost Search
    • Heuristic Search (A*)
  4. Minimum Spanning Tree
    • Prim’s Algorithm
    • Kruskal’s Algorithm

Analysis

  1. Time Complexity
    • Recurrence
  2. Space Complexity

01

​

02

​

03

​

00

7 of 31

Concrete data structures:

Array & Dynamic Array

Operations:

  1. Insert (at the end):
    • Array: O(1); But fixed size
    • Dynamic Array: O(1) + O(n)=O(n); realloc
  2. Delete:
    • Find: O(n)
    • Delete: O(n)
  3. Search:
    • O(n)

8 of 31

Concrete data structures:

Sorted Array & Sorted Dynamic Array

Operations:

  1. Insert:
    • Find: O(log n)
    • Insert: Array: O(n); Dynamic Array: O(n)+O(n)=O(n)
  2. Delete:
    • Find: O(log n)
    • Delete: O(n)
  3. Search:
    • O(log n)

9 of 31

Concrete data structures:

Linked List

Operations:

  1. Insert:
    • From Head: O(1) with a pointer to the head
    • From Tail: O(1) with a pointer to the tail
  2. Delete:
    • From Head: O(1)
    • From Tail: O(n)
    • A specific element?
      • Find: O(n)
      • Delete: O(1)
  3. Search:
    • O(n)

10 of 31

Concrete data structures:

Sorted Linked List

Operations:

  1. Insert:
    • Find: O(n)
    • Insert: O(1)
  2. Delete:
    • Find: O(n)
    • Insert: O(1)
  3. Search:
    • O(n)

11 of 31

Concrete data structures:

Binary Search Tree (BST)

Operations:

  1. Insert:
    • Worst case: O(n)
    • Average case: O(log n)
  2. Search:
    • Worst case: O(n)
    • Average case: O(log n)
  3. Traversal (visited all nodes once):
    • Pre-order: Current -> Left -> Right
    • In-order: Left -> Current -> Right
    • Post-order: Left -> Right -> Current
  4. Delete:
    • Worst case: O(n)
    • Average case: O(log n)
      • Case 1: Node is a leaf
      • Case 2: Node has either a left or right child, not both
      • Case 3: Node has both a left child and a right child

12 of 31

Concrete data structures:

AVL Tree & Others

Operations:

  1. Insert: \Theta(log n)
  2. Delete: O(log n)
  3. Search: O(log n)

​

​

​

  • 2-3 Tree (Lecture Slides)
  • 2-3-4 Tree (Tutorial Slides)

​

13 of 31

Concrete data structures:

Hash Table

Operations:

  1. Insert:
    • Worst case: O(n)
    • Average case: O(1)
  2. Search:
    • Worst case: O(n)
    • Average case: O(1)
  3. Collisions
    • Linear Chaining
    • Linear Probing
    • Double Hashing

14 of 31

Concrete data structures:

Heap

Operations:

  1. Insert (Upheap):
    1. Insert at the end
    2. Then, upheap: O(log n)
  2. Delete (Downheap):
    • Swap Root with Last
    • Delete Last
    • Then, Downheap: O(log n)
  3. Construction
    • Top-Down (repeated insert)
      1. O(n log n)
    • Bottom-Up Heap Construction (recursively downheap)
      • O(n)

15 of 31

Abstract data structures:

Dictionary

  1. Static Array
    • Insert: O(1)
    • Find: O(n)
    • Cons: Fixed size
  2. Dynamic Array
    • Insert: O(1) + O(n)
    • Find: O(n)
  3. Sorted Dynamic Array
    • Insert: O(n) + O(n)
    • Find: O(log n)
  4. Linked List
    • Insert: O(1)
    • Find: O(n)

​

  1. Hash Table
    • Insert: O(1)
    • Find: O(1)
    • Cons: Space, hash function, collisions
  2. Balanced BST
    • Insert: O(log n)
    • Find: O(log n)
  3. Trie
    • Insert: O(m)
    • Find: O(m)
    • Cons: Depending on the key length

​

16 of 31

Abstract data structures:

Stack

  1. Dynamic Array
    1. Array head as Stack top:
      1. Push (Insert ): \Theta(n) + O(n)
      2. Pop (Delete): \Theta(n)
    2. Array tail as Stack top:
      • Push (Insert ): O(1) + O(n)
      • Pop (Delete): O(1)
  2. Linked List
    • Linked List head as Stack top:
      • Push (Insert ): O(1)
      • Pop (Delete): O(1)
    • Linked List tail as Stack top:
      • Push (Insert ): O(1)
      • Pop (Delete): O(n) (need to find second last)

​

17 of 31

Abstract data structures:

Queue

  1. Dynamic Array
    1. Array head as Queue head:
      1. Enqueue (Insert ): O(1) + O(n)
      2. Dequeue (Delete): \Theta(n)
    2. Array tail as Queue head:
      • Enqueue (Insert ): \Thera(n) + O(n)
      • Dequeue (Delete): O(1)
  2. Linked List
    • Linked List head as Queue head:
      • Enqueue (Insert ): O(1) (Enqueue from Linked List tail)
      • Dequeue (Delete): O(1) (Dequeue from Linked List Head)
    • Linked List tail as Queue head:
      • Enqueue (Insert ): O(1)
      • Dequeue (Delete): O(n) (need to find second last)

​

  1. Circular Dynamic Array
    1. Enqueue (Insert ): O(1) + O(n)
    2. Dequeue (Delete): O(1) (moving pointers)

​

​

18 of 31

Abstract data structures:

Priority Queue

  1. Dynamic Array
    • Enqueue (Insert ): O(1) + O(n)
    • Dequeue (Delete): O(n)
  2. Sorted Dynamic Array
    • Enqueue (Insert): O(log n) + O(n)+O(n)
    • Dequeue (Delete): O(1)
  3. Linked List
    • Enqueue (Insert ): O(1)
    • Dequeue (Delete): O(n) + O(1)

​

  1. Hash Table
    • Enqueue (Insert ): O(1)
    • Dequeue (Delete): O(1)
    • Cons:
      1. Key must be finite and bounded
      2. Same priority -> 1 address
      3. 1 address -> Same priority
      4. Space efficiency
  2. Heap
    • Enqueue (Insert ): O(log n)
    • Dequeue (Delete): O(log n)
    • Pros:
      • Construction in O(n)

​

19 of 31

Explicit Graph & Implicit Graph

G = (V,E):

  • Vertices
  • Edges

​

Properties:

  • Connectivity
    • Unconnected
    • Weakly Connected
    • Strongly Connected
    • Complete
  • Weightedness
  • Cyclicity
  • Directedness

​

20 of 31

Sorting algorithms

Selection sort

Insertion sort

Quicksort (slow sort) + Hoare’s partitioning scheme

Mergesort (top down + bottom up)

Heapsort (uses a priority queue)

Distribution Counting

01

​

02

​

03

​

04

​

05

​

06

​

21 of 31

Sorting algorithms: Selection sort

Find smallest item put at the beginning of the unsorted part of the array, then shrink size of unsorted part of array AND repeat.

  1. Time Complexity
    • Best: \Theta(n^2)
    • Average: \Theta(n^2)
    • Worst: \Theta(n^2)
    • Overall: \Theta(n^2)
  2. In-place?
    • Yes
  3. Stable?
    • No

​

22 of 31

Sorting algorithms: Insertion sort

Compare two items, if out of order swap, repeat until item in correct spot, then continue to next item until you reach the end of the array.

  1. Time Complexity
    • Best: O(n)
    • Average: O(n^2)
    • Worst: O(n^2)
    • Overall: \Theta(n^2)
  2. In-place?
    • Yes
  3. Stable?
    • Yes

​

23 of 31

Sorting algorithms: Quicksort (slow sort)

Recursively: Choose pivot then use Hoare’s partitioning scheme to partition elements to either side of the pointer, then call quicksort on either side until you get the singleton case.

  1. Time Complexity
    • Best: O(n^2)
    • Average: \theta(n log n)
    • Worst: \theta(n^2)
    • Overall: \Theta(n^2)
  2. In-place?
    • Yes
  3. Stable?
    • No

​

24 of 31

Sorting algorithms: Mergesort

Top down: recursively half repeatedly until you get to the singleton case, then merge the halves. USES A STACK.

Bottom up: iteratively breakup the container into singletons then merge two items repeatedly until everything is merged together. USES A QUEUE.

  1. Time Complexity (Recurrence)
    • Best: \Theta(n log n)
      1. Adaptive Merge Sort: \Theta(n)
    • Average: \Theta(n log n)
    • Worst: \Theta(n log n)
    • Overall: \Theta(n log n)
  2. In-place?
    • No
  3. Stable?
    • Yes

​

Space

  1. Bottom-Up
    • Dynamic Array: \Theta(n)
    • Linked List: \Theta(n)
      1. O(1) without Queue
  2. Top-Down
    • Dynamic Array: \Theta(n)
    • Linked List: \Theta(n log n) (stack calls)

​

​

25 of 31

Sorting algorithms: Heapsort

Exploit the heap data structure:

Make a heap

While PQ:

Delete min

Fix

Repeat

​

  1. Time Complexity
    • Best: \Theta(n log n)
    • Average: \Theta(n log n)
    • Worst: \Theta(n log n)
    • Overall: \Theta(n log n)
  2. In-place?
    • Yes
  3. Stable?
    • No

​

26 of 31

Sorting algorithms:

Distribution Counting

  1. Count frequency of each item (k of them)
  2. Store cumulative counts
  3. Traverse old array and use cumulative counts to copy in values

​

  1. Time Complexity
    • Best: \Theta(n + k)
    • Average: \Theta(n + k)
    • Worst: \Theta(n + k)
    • Overall: \Theta(n + k)
  2. In-place?
    • No (n + 2k)
  3. Stable?
    • Yes

​

27 of 31

Traversal Algorithms

Depth first (nose dive search)

Breadth first (layer by layer search)

Dijkstra’s

Bellman-Ford

Floyd-Warshall

01

​

02

​

03

​

04

​

05

​

28 of 31

Search Algorithms

Depth First Search (DFS)

Breadth First Search (BFS/BrFS)

Iterative Width (IW)

Uniform Cost Search

Heuristic Search (A*)

​

01

​

02

​

03

​

04

​

05

​

29 of 31

Minimum Spanning Tree (MST)

Algorithms

Prim’s Algorithm

Kruskal Algorithm

01

​

02

​

30 of 31

Q+A

31 of 31

Feedback form + sign ups

Feedback Form!