| In General |
| ■ | Date: 12/09/2024 (Monday) for Section 002 12/11/2024 (Wednesday) for Section 001 |
|||||
| ■ | Time: 11:00 am for Section 002 Time: 11:00 am for Section 001 (Note the 11:00am exam start time, which is different from the 12:30pm class start time.) | |||||
| ■ | Time allowed (in class): 2.5 hours. | |||||
| ■ | Exam will be closed books / notes / online-resources / discussions. | |||||
| ● | All allowed reference material will be provided as part of the exam or during the exam. | |||||
| ■ | Exam will be comprehensive (i.e., cumulative) but expect more emphasis on the topics covered during the later part of the course, including: | |||||
| ● | Recursion (continued) |
|||||
| ● | Trees | |||||
| ● | More advanced sorting algorithms (heapsort, mergesort and quicksort) | |||||
| ● | Hashing (to the extent that we have time to cover) | |||||
| ● | Graphs (to the extent that we have time to cover) | |||||
| For earlier (previously tested) topics: refer to Exam 1 Study Guide and Exam 2 Study Guide previously posted. |
| ■ | Recursion (continued) |
|||||
| ● | Apt/expedient application of recursion in more advanced/complex structures/situations. | |||||
| ■ | Trees | |||||
| ● | General properties of trees and specific properties of special trees covered | |||||
| ► | Tree versus graph | |||||
| ► | 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 | |||||
| ● | Search trees. | |||||
| ► | add/search/remove operations for BST | |||||
| ● | Heap and priority queue: | |||||
| ► | maxheap and minheap | |||||
| ○ | 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. | |||||
| ● | Graph fundamentals: | |||||
| ► | 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) | |||||
| ○ | Dijkstra's algorithm |
|||||
| ● | Graph spanning algorithms: | |||||
| ► | Minimum spanning tree - minimally spanning a weighted graph (that is undirected and connected) | |||||
| ○ | Prim's algorithm | |||||
| ● | 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) | |||||
| Other Tips: |
| ■ | You may want to check out the Sample
Past Exam Questions (under Other Resources).
(You should not however, expect the questions to be identical in number, kind, coverage, etc. |
|||||
| ■ | It is only fair that you need not have to worry about questions being written on topics that have not been covered/discussed. However, somewhat indirect question(s) may be written that test(s) your understanding of and your ability to apply the concepts covered/discussed during the semester, individually (involving a single concept) or in combination (involving multiple concepts). | |||||
| ■ | If you are eligible and intend to use extended time accommodation: | |||||
| ● | Do the following: | |||||
| ► | Follow proper procedure to request taking the exam at the ATSD. | |||||
| ○ | You typically need to do the request at least a certain number of (non-weekend?) hours in advance. | |||||
| ○ | The exam date of your request should be the same as the (regularly) scheduled date of the exam. | |||||
| ○ | The exam start time of your request should be closest to the (regularly) scheduled start time of the exam. | |||||