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

■ General


● Date:  04/02/2025 (Wednesday).

● Duration: 80 minutes.

Questions will be based on the topics covered since Exam 1, ending with the 03/31/2025 lecture):

● Templating (continued).

● Introduction to algorithm analysis.

● Linked list.

● Stacks/queues (and applications).

● Recursion.

Test will be closed books and closed notes.

■ Relevant Material


● Most relevant Lecture Notes: 311Templating through 317Recursion.


► (Focus on topics/material we spent much time on - diligence in keeping up with classes is significant here.)

● Examples (significant number of them posted under Examples) covering topics indicated above.

● Assignments 4, 5 (both parts), and 6 Part 1.

■ Other Resources


● You may want to check out sample past test/exam questions already posted on the class homepage.


► You should not however, expect the questions to be identical in number, kind, topic coverage, etc.


► You should not have to worry about questions being written on topics we have not yet covered; some such questions may appear as sample past questions because the associated topics were appropriate at that time.

■ Checklist (exhaustiveness not guaranteed) of some things you are expected to know and/or know how to do/apply:


● Templating (continued).


► How templating is put to good use in Assignment 4.



○ What particular situation (that makes templating advantageous) is illustrated in Assignment 4.


► How to develop a template class.
(exercised via Assignment 4)



○ How to specify, implement, and use.



○ How to organize (including work-around used to effect separation of interface from implementation).

● Introduction to algorithm analysis.


► Nature-of-input-dependent scenarios: worse case, average case and best case.


► Big-O notation/characterization.



○ Upper bound (order on resource requirement growth rate), asymptotic ("in-the-big", "settled-down"), order of magnitude ("broad-brushing").



○ What it can (is intended to) capture (and what is not captured): implications and common misconceptions.



○ Common categories and their growth-rate behavior and relative ordering: O(1), O(log n), O(n), O(n log n), O(n2).



○ Be able to quickly inspect a code segment (involving the basic flow-of-control constructs - sequence, selection, repetition) and characterize it (as "tightly" as can be inferred).

● Linked list.


► Array versus linked list: strengths and weaknesses.



○ Random (versus sequential) access, insertion/deletion anomaly, resizing woe.



○ When to use which to take advantage of the strength(s) and minimize/avoid the weakness(es).




♯ (There's no one "panacean data structure" -> use the right tool for the right problem.)


► Be able to design/implement functions that manipulate linked list(s).



○ Manipulate: add, delete, modify, search, inspect, ... (may be in combination within a function).



○ Common coding idioms/"patterns": what they mean and when to use.




♯ cursor = cursor->link;




♯ while (cursor != 0) { ... }




♯ while (cursor->link != 0) { ... }




♯ ...



○ How head pointer(s) should be passed to a function: by value or by reference.



○ Be cognizant of and know how to avoid null-pointer exception.




♯ When writing code that dereferences a pointer (at some point), always check that the pointer will never contain the null address (at that point).




♯ Be careful when writing relational expression involving short-circuit evaluation.



○ Know when to say no:




♯ Don't use memory that's not allocated.




♯ Don't access memory that's already deallocated (if that memory access must be done, do it before deallocation).




♯ Don't leak away memory.


► Be able to read/understand C++ code that manipulates linked list(s) and identify any bugs (and associated key problems that can arise from them).



○ Example associated key problems: null-pointer exception, stale pointer, illegal memory access, memory leak, head (list handle) unintentionally lost, . . .

● Stacks/queues and applications.


► Containers restricted in specific ways (especially wrt addition and removal of data items) to support commonly required operational characteristics.



○ LIFO with stacks and FIFO with queues


► Fundamental operations (besides construction and destruction), STL-style.



○ Stacks: push, pop, top, empty, size.




♯ top + pop for traditional pop.



○ Queues: push, pop, front, empty, size.




♯ push for traditional enqueue.




♯ front + pop for traditional dequeue.


► Error conditions: underflow (always possible) and overflow (implementation and system resource dependent).


► Keys reasons for their usefulness: LIFO and/or FIFO buffering, reversal and echoing capabilities.


► Applications (all related to LIFO and/or FIFO buffering).



○ Reversal and echoing.




♯ How to put these effects to use (expressing algorithms involved in pseudocode).



○ Invocation (function-calling) flow of control support/management: system/call/run-time stack.




♯ (in more depth when covering recursion)



○ Level (breadth-first) traversal of non-linear data structures.


► STL in perspective.



○ How to use STL stack and queue templated containers.

( and whatever recursion-related aspects below we get to cover up to and including the 03/31/25 lectures )

● Recursion.


► Recursive thinking



○ 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)



and how to use that to trace 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



○ Indirect recursion


► Advantages/disadvantages



○ Conceptual elegance/clarity and code compactness



○ Function-call overhead and stack-overflow risk




■ Still Others


● Do the following if you are eligible and intend to use extended time accommodation:


► 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.