|
|
|
|
○ |
Dealing with the seemingly infinite in finite fashion |
|
|
|
○ |
"Divide/reduce-and-conquer" WHEREIN "results of division/reduction are identical and smaller versions of the original (what gets divided/reduced)" |
|
|
|
○ |
4 criteria for successful
application: recursively decomposible, base case(s), making
progress, ultimate reachability of base case(s) |
|
|
► |
How function-calling
(recursive functions included) is typically implemented with the help
of system/call/run-time stack ... |
|
|
|
○ |
Activation records (stack frames) |
|
|
|
(knowing it should be helpful in mastering recursion, including tracing recursive functions). |
|
|
► |
Design/implement recursive
algorithms for given problems (including problems that involve arrays,
linked lists and trees) |
|
|
|
○ |
Most important first hurdle - express/formulate problem in terms of smaller problems of the same type |
|
|
► |
Advantages/disadvantages |
|
|
|
○ |
Conceptual elegance/clarity and code compactness |
|
|
|
○ |
Function-call overhead and stack-overflow risk |
|
● |
Apt/expedient application of recursion in more advanced/complex structures/situations. |
|
● |
General properties of trees and
specific properties of special trees covered |
|
|
► |
n-ary tree -> binary
tree -> heap, binary search tree (BST) and height-balanced (such as AVL) search trees |
|
|
► |
Most (if not all) "traits" related to a tree must be recursively applied (for certain descriptions such as balanced, binary search tree, in-order traversal, etc. to apply) |
|
● |
Representation of binary tree |
|
|
► |
Pointer-based representation |
|
|
► |
Efficient representation of complete
binary tree using array |
|
● |
Traversal (breadth-first,
depth-first) and processing of trees |
|
|
► |
Most tree manipulations would
be very difficult (at best) for us to track if we don't do it recursively |
|
|
► |
add/search/remove operations
for BST |
|
● |
Heap and priority queue: |
|
|
|
○ |
which one for which situation (especially in the contexts of priority queue and sorting) |
|
|
► |
add/remove operations for heap |
|
|
|
○ |
reheapification upward and reheapification downward (heapifying semiheap) |
|
|
|
○ |
(enqueue/dequeue
in the context of priority queue and Assign07).
|
| ■ |
More advanced sorting concepts/algorithms covered |
|
● |
what and how about
the concepts/algorithms, such as (CAUTION: these are just some examples,
not
a complete listing): |
|
|
► |
Should it be min heap or max heap for heapsort |
|
|
► |
What's accomplished in heapsort's
first phase and how it can be efficiently accomplished |
|
|
► |
What become of the two (sorted and unsorted) regions each time an item is placed at where it should be during the second phase of heapsort |
|
|
► |
What happens to the order of the
values involved (relative to the pivot) in each of quicksort's stages/phases
when the stage/phase finishes and how it's accomplished |
|
|
► |
What's the "basis" for and how it's
applied in mergesort
(What happens to the order of the
values in each of the 2 halves involved when the 2 recursive calls made during each halving step finish?)
|
|
● |
Efficiency characteristics associated with basic and more advanced sorting algorithms.
(E.g.: which has quadratic time complexity under worst case scenario.)
|
| ■ |
Hashing
concepts/algorithms - don't have to worry about those not ("time-permittingly") covered. |
|
● |
what and how about
the concepts/algorithms, such as (CAUTION: these are just some examples,
not
a complete listing) |
|
|
► |
How do sequential, ordered
(sorted) and hashed approaches (of storing/accessing collections
of data items) compare |
|
|
► |
What load factor, collision,
collision
resolution strategy, chained hashing (separate chaining) etc.
is (in hashing) |
|
|
► |
What (things) about linear probing, quadratic probing
and double hashing and how they are applied |
|
|
|
○ |
probe sequence, probe function (and "step size"), primary clustering, secondary clustering, relatively prime and twin primes |
|
|
► |
What kinds of problems are not particularly
good for hashing |
|
|
► |
What properties characterize a good
hash function and be able to use such properties to evaluate the suitability/quality
of a given hash function under a certain environment |
|
|
|
○ |
Especially the most critical ones (from Lecture Note 324s01HelpingHandNotesOnHashing): |
|
|
|
|
| To be candidate: (1) hash-value range must cover entire hash-table range, (2) must be cheap/fast to calculate. |
| ■ |
Graphs concepts/algorithms - don't have to worry about those not ("time-permittingly") covered. |
|
● |
Big-picture notions about graphs - previewed as part of prelude to trees |
|
|
► |
Importance of data modeling when solving complex (especially data-heavy) problems |
|
|
► |
In data modeling context: tree for hierarchical relationships, graph for network relationships |
|
|
► |
In CS3358 context: graph as most general (and non-linear) data structure |
|
|
|
○ |
A tree is a graph but a graph is not necessarily a tree (unless the graph is connected and acyclic). |
|
|
|
○ |
A tree can structurally degenerate into a linked list. |
|
|
► |
Big picture: graph <--> problem-solving
|
|
|
|
○ |
Including definition and some terminology
|
|
|
► |
Typical representaions: adjacency matrix (array of arrays), edge lists (array of lists), array of sets
|
|
|
|
○ |
Especially the first two
|
|
|
► |
Traversal: depth-first (DFS) and breadth-first (BFS).
|
|
● |
Path finding algorithms: |
|
|
► |
Path of minimum length (# of edges)
|
|
|
|
○ |
edges visited during breadth-first traversal |
|
|
► |
Path of minimum cost/distance (sum of edge weights) |
|
● |
Graph spanning algorithms: |
|
|
► |
Minimum spanning tree - minimally spanning a weighted graph (that is undirected and connected) |
|
● |
Cautious/guarded appreciation for greedy approach in problem-solving (seen in Dijkstra's and Prim's algorithms) |
|
|
► |
Going for locally optimal choices can but doesn't always result in globally optimal outcome.
|
| ■ |
Relative strength(s)/weakness(es)
of the various storage/access techniques covered and assess their
viabilities for specific situations |
|
● |
Know about relative strength(s)/weakness(es) |
|
● |
Know how to apply knowledge to given problem situations |
|
|
► |
General guideline: maximize strength(s), minimize weakness(es) |
|
