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

■ General


● Date:  04/01/2026 (Wednesday).

● Duration: 80 minutes.

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

● Templating.

● Introduction to algorithm analysis.

● Linked list.

● Stacks/queues (and applications).

Test will be closed books / notes / online-resources / discussions.

● All allowed reference material will be provided as part of the exam or during the exam.

● All electronics off during the exam.

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


● Specifying/implementing/utilizing container ADTs in C++ - some aspects:


► Iterators.



○ What are and why.


► Enhanced scoping (name-conflict prevention) using custom namespace.


► Symbolic representation of data type using typedef.


► Use of size_t for sizing/counting/iterating.



○ Pitfalls of using size_t.

● Templating.


► What it essentially enables one to do.



○ What must hold true to make it possible.


► Template function and template class.



○ Provision data types must meet for successful use with templates.


► Relatively simple example illustrating C++ templating mechanics/quirks.



○ How to specify, implement, and use.



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


► Aspects of STL.



○ What the 3 key components are.




♯ containers (template classes), iterators, algorithms.



○What left-inclusive metaphor is.


► How templating can be put to good use to develop generic containers.

○ What key feature containers should have for class template to be useful.

● 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 access (in contant time) versus sequential access (in linear time) , 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.


► Select implementation consideration: queue using circular (singly-)linked list.


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

■ Others


● Reference material.


► Class Recordings page (on Canvas), especially the Key Resource briefs from 02/25/26 through 03/30/26 that point to items located elsewhere:



○ Lecture Notes



○ Examples



○ Drills and Challenges



○ Assignments

● You may want to check out sample past exam questions posted on the class homepage (under Other Resources).


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


► Notion very ill-advised to harbor:
     I take it I will do well in current exams if I can do the sample past exam questions well.


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

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