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

■ General


● Date:  11/04/2024 (Monday).

● Duration: 80 minutes.

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

● Specifying/implementing/utilizing container ADTs in C++ - some aspects (kept out of Exam 1 previously):

● Templating.

● 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: 308ContainerClassBagSequence and 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 3, 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:


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

● 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).




♯ For examples on how to clearly write pseudocode involving stacks and queues, see "STL_Stack_Queue_Example", "Implementing Queue Using 2 Stacks" and "StackQueueAppEg02_LevelTravOfLLofLL_Pseudocode" posted under Examples.



○ 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 (chk_pal).


► Implementations using array and linked list.



○ Using either to implement stack is pretty straightforward and mundane - stack has "only 1 door".



○ Using either to implement queue is more complicated and interesting - queue has "2 doors":




♯ Circular array.





◊ size_type next_index(size_type current_index, size_type capacity)
{ return (current_index + 1) % capacity; }




♯ Circular linked list.





◊ Where should front and rear be and why (especially in regard to push and pop)?

( and whatever recursion-related aspects below we get to cover up to and including the 10/30/24 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.