CS 3358 (Data Structures and Algorithms) by Lee S. Koh
Final Exam Study Guide 

In General

■ Date: 05/05/2025 (Monday) for Section 253
         05/07/2025 (Wednesday) for Section 252
■ Time: 02:00 pm for Section 253
Time: 02:00 pm for Section 252 (Note the 02:00pm exam start time, which is different from the 03: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.

For later topics, following outlines (most if not all) the things you are expected to know and/or know how to do/apply:
■ 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.