main page — COMP 526 Applied Algorithmics

Unit 2: Fundamental Data Structures – Extra Material

**
This is an archived version of this module from Spring 2022.
**
Click here for the current iteration.

This page collects additional material for Unit 2 to deepen your understanding.

Here we use the lecture videos from the online course *Algorithms*
by Robert Sedgewick and Kevin Wayne
which are available on CUvids.io.
Alternatively, there is an eponymous textbook by the same authors
(see below)

### How to watch the videos

Staying focused and learning effectively from videos is not easy.
To help you overcome surface learning, I added
a list of *guidance questions* resp. short tasks to every video.

*
Try to answer all guiding questions while watching the videos and
take notes.
*

(I encourage you to handwrite these: The Pen Is Mightier Than the Keyboard (pdf).

In addition, CUvids tests your in-depth understanding with question prompts.

**Important:**
Speed up or slow down the videos (in the player) so that you
are neither bored nor lost.
CUvids.io also has a (searchable!) transcript of all videos, as well as subtitles.

### 1 – Stacks

Content: intro to ADTs, stacks and their implementations

**Guiding questions:**

- What is an abstract data type (according to Sedgewick)? What is a data structure?
- What operations does a stack support?
- What does FIFO and LIFO mean?
- What type of linked list is the presented implementation of a stack based on?
- How much space does the stack implementation use?
- What is the second implementation of stacks? Does it fully satisfy the specification of stack?
- What is loitering?

### 2 – Resizable Arrays

Content: doubling arrays, amortized costs

**Guiding questions:**

- First, a simplistic method is presented for obtaining arrays of variable sizes. How does it work? Why is it (usually) not useful?
- What are
*amortized*costs? Describe the concept using`push`

as an example. - When do we shrink the array again? Why do we do that?
- Do resizing-array stacks fulfill all API requirements?
- When should we use resizing arrays resp. linked lists to implement stacks according to Sedgewick?

### 3 – Queues

Content: queues and their implementations

**Guiding questions:**

- What operations does a queue support?
- How does the linked-list implementation of queues differ from that for stacks?
- How does the resizing-array implementation of queues differ from that for stacks?

### 4 – Java Generics

Content: Java *generics* for parametric types

**Guiding questions:**

- What options did programmers have in the original Java (before version 1.5)?
- What is the advantage of generics as introduced in Java 1.5?
- What caveats does Sedgewick mention in connection with Java generics?

### 5 – Iterators

Content: (Java’s) iterator concept, Bag ADT

**Guiding questions:**

- What operations does an iterator support?
- How can we implement an iterator for linked lists?
- How can we implement an iterator for arrays?
- For both cases, think about what happens when we add elements to the underlying stack while iterating over it. What happens to elements that are deleted?

### [Optional] Stack and Queue Applications

Content: some interesting applications of stacks and queues; not vital for following COMP 526, but worthwhile knowing.

**Guiding questions:**

- What operations does Java’s
`List`

interface support? - Briefly describe the running-time complexity of these methods in
`ArrayList`

and`LinkedList`

. - What application for stacks does Sedgewick present?
- Which problem does Dijkstra’s two-stack algorithm solve? Which assumption does Sedgewick make for the input? (hint: parentheses!)
- How does Sedgewick justify the correctness of Dijkstra’s two-stack algorithm?

### 6 – Priority Queues

Content: The priority queue ADT, its applications and elementary implementations

**Guiding questions:**

- What operations do
`MaxPQ`

resp.`MinPQ`

offer? - Why does the
`topM`

test client use a*Min*PQ to find the M*largest*transactions – is that a mistake? - Which elementary implementations are presented? What are their running-time complexities?

### 7 – Binary Heaps

Content: binary-heap implementation (without change key)

**Guiding questions:**

- What is a
*binary tree*(according to Sedgewick)? Be precise and give examples. - What is a
*complete*binary tree? How many (topologically, i.e., ignoring node labels) different complete binary trees with N nodes are there? - What does it mean that a binary tree is
*heap-ordered?*What does heap order imply for the key at the root? - How does Sedgewick encode a complete binary tree in an array? How is that possible without explicitly storing where the child nodes of a node are stored?
- What does the
*swim*operation do? Which preconditions must be fulfilled to run swim, and which postconditions does swim guarantee upon termination? - What does sink do? What are pre- and postconditions?
- How does insert work for a binary-heap MaxPQ?
- How does
*delMax*work for a binary-heap MaxPQ? - What is the running-time complexity of these two operations?
- What does
*immutability*mean? What could go wrong when keys of a PQ are not immutable?

### 8 – Symbol Table API

Content: symbol table ADT, requirements for keys, applications of symbol tables, and test clients.

**Guiding questions:**

- What operations does every symbol table (ST) support?
- What are similarities and differences between ST and mathematical functions?
- How should a typical implementation of Java’s
`equals`

method for a data type with several fields look like? What requirements have to be met? - Explain how the frequency counting test client uses STs.

### 9 – Elementary Symbol-Table Implementations

Content: functional, but inefficient ST implementations based on lists.

**Guiding questions:**

- What are the two implementations that are presented?
- How does
`get`

and`put`

work for these two implementations? - What is the running-time complexity of
`get`

and`put`

in these implementations?

### 10 – Ordered Operations

Content: Ordered ST ADT

**Guiding questions:**

- What are the (additional) operations in an
*ordered ST*?

### 11 – Binary Search Trees

Content: (unbalanced) binary search trees (BSTs): definitions, search, insert, and analysis

**Guiding questions:**

- (again) What is a
*binary tree*according to Sedgewick? - What is a binary
*search tree*(BST)? Draw a BST for the keys 10, 20, 30, 40, 50. - How is a BST represented in Java? Draw a box-and-arrow diagram for your example BST.
- How does search in a BST work? Describe it on your example.
- How does insertion into a BST work? Again, give an example on your tree.
- How does the best-case tree w.r.t. search costs look like? (more precisely, the best case w.r.t. to searching each key once)
- What is the worst possible search cost? How does a tree look like where these occur?
- What statement does Sedgewick make about typical / average-case search costs in BSTs?

### 12 – Ordered Operations in BSTs

Content: augmented BST implementation of Ordered ST.

**Guiding questions:**

- How can we implement
*min*and*max*in BSTs? - How can we implement
*floor*and*ceiling*? - What do we have to do to maintain correct subtree sizes in all nodes?
- How does the
*rank*operation work in BSTs?

## Further reading and sources

The textbook corresponding to the lecture videos has some more details and many exercise problems. Summaries and code are available on the booksite.