December 20, 2024 1

REVIEW
EECS 2101
 2

Algorithm Analysis
• Given an algorithm, compute its running time in terms of O, , and
 (if any).
• Usually the big-Oh running time is enough.
• Given f(n) = 5n + 10, show that f(n) is O(n).
• Find c and n0

• Compare the grow rates of 2 functions.

• Order the grow rates of several functions.
• Use slide 17.
• Use L’Hôpital’s rule.
 3

Running Times of Loops

Nested for loops:
•If the exact number of iterations of each loop is known, multiply the
numbers of iterations of the loops.

•If the exact number of iterations of some loop is not known, “open”
the loops and count the total number of iterations (as in Assignment
2).
 4

Running Time of Recursive Methods

• Could be just a hidden “for" or “while” loop.
• See “Tail Recursion” slide.
• “Unravel” the hidden loop to count the number of iterations.
• Logarithmic
• Examples: binary search, exponentiation, GCD
• Solving a recurrence
• Example: merge sort, quick sort
 5

Recursion
Know how to write recursive functions/methods:
•Recursive call
• Adjusting recursive parameter(s) for each call
•Base case(s)

1.Use the definition (factorial, tree depth, height)

2.Cut the problem size by half (binary search), or by k elements at a
time (sum, reversing arrays).
3.Divide and conquer (merge sort, quick sort)
 6

Recursion and Running Time

• Examples: problems in Assignment 3.
 7

Arrays and Linked Lists

Linked lists
•Singly linked
•Doubly linked
•Implementation
•Running times for insertion and deletion at the two ends.
 8

Running Times of Array and Linked List Operations

Array Array DL list DL list
Operation unsorted sorted unsorted sorted
search O( ) O( ) O( ) O( )

insert O( ) O( ) O( ) O( )

delete O( ) O( ) O( ) O( )
 9

Stacks, Queues and Deques

• Operations
• Array implementation
• Linked list implementation
• Running times for each implementation
 10

Trees
 Definitions, terminologies
 Traversal algorithms and applications
• Preorder
• Postorder
 Computing depth and height of a tree or node.
 Assignment 5
 11

Binary Trees
• Linked structure implementation
• Array implementation
• Traversal algorithms
• Preorder
• Postorder
• Inorder
• Properties: relationships between n, i, e, h.
• Definitions:
• complete binary tree
• full binary tree
 12

Linked Structure of Binary Trees

• A node is represented

by an object storing
• Element
• Parent node
B
• Left child node
• Right child node
 

B A D

A D    

C E C E
12
 13

Array Implementation of Binary Trees

Each node v is stored at index i defined as follows:

• If v is the root, i = 0
• The left child of v is in position 2i + 1
• The right child of v is in position 2i + 2
• The parent of v is in position ?
 14

Space Analysis of Array Implementation

• n: number of nodes of binary tree T
• pM: index of the rightmost leaf of the corresponding full binary tree (or size of
the full tree)
• N: size of the array needed for storing T; N = pM + 1
Best-case scenario: balanced, full binary tree pM = n
Worst case scenario: unbalanced tree
• Height h = n – 1
• Size of the corresponding full tree:
pM = 2h+1 – 1= 2n – 1
• N = 2n
Space usage: O(2n)
 15

Arrays versus Linked Structures for Binary

Trees
Linked lists Arrays
• Slower operations due to pointer • Faster operations
manipulations
• Use less space if the tree is • Use less space if the tree is
unbalanced balanced (no pointers)
• Rotation (restructuring) code is • Rotation (restructuring) code is
simple complex
 16

Binary Search Trees and AVL Trees

BST AVL trees
Properties •Properties
Searching •Searching
Insertion •Insertion: as BST plus
Distinct keys • restructuring (once)
Duplicate keys •Deletion: as BST plus
Deletion (3 cases) • restructuring (maybe more
Running times than once)
•Running times
 17

BSTs versus AVL Trees

Operation BSTs AVL Trees

search

insert

delete

findMin

findMax
 18

Implementations of Priority Queues

• Unsorted linked list • Unsorted array
• insertion O( ) • insertion O( )
• deleteMin O( ) • deleteMin O( )
• Sorted linked list • Sorted array
• insertion O( ) • insertion O( )
• deleteMin O( ) • deleteMin O( )
• AVL trees • Heaps
• insertion O( ) • insertion O( )
• deleteMin O( ) • deleteMin O( )
 19

Heaps
• Properties
• Array implementation
• Insert
• upheap percolation
• Delete
• downheap percolation
• Running time
Heap Sort
Using a temp heap T In-place sorting

for (i = 0; i++; i < n) run buildHeap on A;

T.insert(A[i]); repeat
for (i = 0; i++; i < n) deleteMax;
A[i] = T.deleteMin(); copyMax;
until the heap is empty;

Running time = ? Running time = ?

 21

buildHeap
• Bottom-up heap construction runs in O(n) time.
• Bottom-up heap construction is faster than n successive insertions, which
take O(nlogn).
 speeds up the first phase of heap-sort.
 22

Sorting Algorithms
• Insertion sort
• Merge sort
• Quick sort
• Heap sort
• Lower bound of sorting algorithms
• O(NlogN)
• When to use which sorting algorithm?
 23

Hashing
• Table size (a prime number) Collision handling
• Hash functions •Separate chaining
• Hash codes: •Probing (open addressing)
• Memory address
• Linear probing
• Integer cast
• Component sum • Quadratic probing
• Polynomial accumulation • Double hashing
• z = 33, 37, 39, 41 (English dictionary)
• Compression functions:
• division (modulo)
•Probing: 3 types of cells (null, in
• MAD use, defunct)
 24

Comparing Collision Handling Schemes

• Separate chaining: • Linear probing: items are
– simple implementation clustered into contiguous runs
(primary clustering).
– faster than open addressing in
general
• Quadratic probing:
– using more memory
secondary clustering.
• Open addressing:
• Double hashing: distributes keys
– using less memory
more uniformly than linear
– slower than chaining in general probing does.
– more complex removals
 25

Graphs
• Definitions (terminology) • Running time of graph methods
• Properties (with respect to V and E) • Graph traversal algorithms
• Data structures • BFS
• Adjacency matrix • DFS
• Adjacency lists • Applications of BFS and DFS
• Assignment 6
 26

Properties of Undirected Graphs

Property 1 Notation
v deg(v) 2E V number of vertices
Proof: each edge is counted twice E number of edges
deg(v) degree of vertex v
Property 2
In an undirected graph with no loops Example
E V (V  1)2  V 4
Proof: each vertex has degree at most
(V  1)  E 6
 deg(v) 3
What is the bound for a directed
graph?
 27

Applications of BFS and DFS

• Is there a path from source s to a vertex v?
• Check array flag[ ]
• Is an undirected graph connected?
• Check array flag[ ]
• To output the contents (e.g., the vertices) of a graph
• Call BFS( ) or RDFS( ) if graph is connected
• Call BFSearch( ) or DFSearch( ) if the property is not known
• To find the connected components of a graph
• Call BFSearch( ) or DFSearch( )
 28

Office Hours before Exam

• Instructor’s: Thursday, 2pm – 3pm

• TA’s tutorial/office hour: Wednesday and Friday

• Check eClass for announcements
 29

After Exam
• There will be office hours for students to review their exam.
• Check eClass and email for time and date

• Final grades will be posted on ePost.