CSCI C243 Final Review

Version 21

Overview

See Oncourse Modules for exam locations and dates.

Format and reference: There will be a mixture of question types, possibly including multiple choice, true/false, short answer, essay. There will be some coding, but not nearly as much as on the midterm. The exam will be given in one part, closed book and notes—not even one sheet of notes. Students may use, but probably will not need, calculators during this exam.

Notation: Θ is capital Theta, in case your browser does not display it properly.

The exam will cover the following topics:

* = question recommended for in-class review.

Pre-Midterm Topics

(Drake, chapters 1–9)

Chapters 1–3: Know the meaning of “encapsulation”, “polymorphism”, and “inheritance”; why they are usually good, and when they might not be good.

Java packages, interfaces, abstract classes. Access qualifiers public, protected, and private. Dynamic method binding. Is-a and has-a relationships. Iterators and the enhanced for statement.

Chapters 4–6: Stack, queue, and list data types, their operations, implementations, and running times.

Chapters 7–8:

Common algorithms for searching and sorting:
Linear and binary search, insertion sort.
How they work.
Their preconditions and running times.
Analysis of algorithms:
Asymptotic (Θ) notation, common running time functions and their names (constant, exponential, linear, quadratic, cubic, polynomial, logarithmic).
How to analyze the running time of structured algorithms using if, while, and similar statements.

Chapter 9: concept of recursion, interpreting recursive functions, setting up (but not solving) recurrence relations, merge sort and quicksort

Sample questions:

  1. *Write statements to print every element in a list L by using an iterator. Assume that the list class of which L is an instance supports iterators as in the Java Collections Framework. (a) Use the enhanced for statement. (b) Use an explicit iterator.

  2. *Analyze the running time of this program fragment:

    sum = 0;
for (i = 0; i < p; i++) {
  if (i % 2 == 0) {
    for (j = 0; j < q; j++)
      sum = sum + i + j;
  }
}

  3. See the Midterm Review for additional questions.

Trees

(Drake, chapter 10)

Binary trees: terms, implementation, traversals (inorder, preorder, postorder, level order).

General trees: representations.

Applications of trees.

Sample questions:

  1. Trees are used to represent hierarchical data. Give two examples of such data.

  2. *In the figure “A General Tree”, identify: the root, the parent of 9, the children of 9, the proper ancestors of 12, the improper descendants of 4, the siblings of 4, the internal nodes, the terminal (leaf) nodes; and what is the height of the tree

    A General Tree

    A General Tree

  3. *State the recursive definition of “binary tree”.

  4. *Given a functional BinaryTree type with the Haskell data declaration

    data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) -- root, left, right
                  | Empty
                    deriving (Eq, Read, Show)

    complete the following function definitions:

    -- size t is the number of nodes in the binary tree t
size :: BinaryTree a -> Int
size Empty = ?
size (Node root left right) = ?

-- elem e t is True if e is present anywhere in binary tree t,
-- otherwise False.
elem :: (Eq a) => a -> BinaryTree a -> Bool
elem e Empty = ?
elem e (Node root left right) = ?

-- preorder t is a list of elements of binary tree,
-- in preorder traversal order
preorder :: BinaryTree a -> [a]
preorder Empty = ?
preorder (Node root left right) = ?

  5. Traversal

    Traversal

    Using the figure “Traversal”, list the nodes in the order they are visited in traversing the tree: (a) preorder; (b) inorder; (c) postorder; (d) level order.

Graphs

(Drake, chapter 15)

A Network
A Network

A Network

Graph terms, representations (adjacency list and adjacency matrix), basic graph search (depth first and breadth first search), topological sort, spanning tree, minimum spanning tree, greedy algorithm.

The exam will not cover specific algorithms for topological sort, shortest paths (Dijkstra, Floyd-Warshall), minimum spanning trees (Kruskal, Prim).

Sample questions:

A Digraph
A Digraph

A Digraph

  1. Terms: vertex, edge, directed graph, undirected graph, cyclic, acyclic, weighted graph, depth-first search, breadth-first search, heuristic search, topological sort, spanning tree, minimum weight spanning tree.

  2. Describe two applications of graphs.

  3. *Sketch the two principal representations for the graph shown in “A Digraph”: (a) adjacency matrix; (b) adjacency list.

  4. *Consider the subgraph of “A Digraph” consisting only of vertices 2, 3, 4, 5, 7, 8, and the edges between them. By any means you can, find a topological order of these vertices.

  5. *By any means you can, find a minimum spanning tree for the network (weighted graph) shown in the figure “A Network”.

Sets: Hash Tables, Binary Search Trees

(Drake, chapter 11; Liu, 2)

Sets: their operations; implementation using ordered lists, binary search trees, and hash tables.

Sample questions:

  1. ​(a) State the recursive definition of “binary search tree”. (b) Not every binary tree is a binary search tree. What is the difference?

  2. Write the recursive algorithm for searching a binary search tree.

  3. *Starting with an empty binary search tree, show the tree after each insertion and deletion: insert 10, insert 0, insert 40, insert 60, insert 35, insert 17, insert −8, insert 6, delete 35, delete 60, delete 10.

  4. *The running times of the insert, search, and remove algorithms for binary search trees are Θ(log N) on the average, but Θ(N) in the worst case. Explain why.

  5. *(a) Write a Java method to hash integer keys for a hash table with 1023 addresses (slots, buckets). (b) Explain how to extend such a method to hash keys consisting of four upper-case letters (A-Z).

  6. *Given an initially empty hash table with 11 buckets (numbered 0 through 10), using chaining, with linked lists for the buckets, and using the hash function h(k) = k mod 11, show the hash table after inserting the following sequence of keys: 799, 1020, 865, 343, 998,
    1. (The hash values are: h(799) = 7, h(1020) = 8, h(865) = 7, h(343) = 2, h(998) = 8, h(117) = 7.)

  7. *What are the best and worst case running times for the insert, search, and delete operations in a hash table? What conditions lead to each case?

  8. *Distinguish between open addressing and chaining.

  9. Which operations do hash tables not efficiently support?

Advanced Trees: Red-Black Trees, Heaps, Tries

(Drake, chapter 14; Liu, 3, 5)

Heaps: their defining properties, operations, and applications (priority queues, heap sort). Running time of these operations.

Tries (which Drake calls “digital search trees”).

Red-black trees: their defining properties; search and insert operations (delete will not be covered); running times.

Sample questions:

  1. *(a) How many nodes are there in a perfect (also called “full”) binary tree of height 10? (b) What is the minimum possible height of a binary tree of 21 nodes?

  2. ​(a) Sketch the array representation of the heap shown in the figure “A Heap”. (b) Formulate the relationships between parent and children’s indices.

    A Heap

    A Heap

  3. *What is a priority queue? What is a heap? What is the running time of the operations if the priority queue is implemented as a heap?

  4. *Show the heap after each insert and removeMin, starting with an empty min heap: insert 50, insert 10, insert 25, insert 35, insert 5, removeMin, removeMin, removeMin.

  5. *Starting with an empty red-black tree, show the tree after inserting each number in the following sequence: −8, 0, 6, 10, 17, 25.

  6. What guarantee is made for the running time of insert, search, and remove in red-black trees? Why is the worst case for red-black trees as good as the best case for binary search trees?

Disk Structures: External Sorting, B-Trees

(Drake, chapter 17; Liu, 7)

Just the general ideas.

*External sorting: the concept of an external merge sort using temporary disk files.

B-trees: their defining properties; operations search, applications. Special cases: 2-3, 2-3-4, and red-black trees. (Details of insert and delete operations will not be covered.)

Comprehensive Questions

These questions require students to integrate and organize their knowledge of data structures, so that they can propose and evaluate appropriate data structures as solutions to problems, based on the types of operations supported and the efficiency of the operations.

  1. *Consider the design of a program which reads a text file and outputs an alphabetized list of the words found in the file, showing the frequency of each word in the input file. For example, if the input file is

    baa baa black sheep
have you any wool
any black goat any cheese

    then the output would be something like this:

    any 3
baa 2
black 2
cheese 1
have 1
sheep 1
wool 1
you 1

    1. Which of the following data structures are totally inappropriate for this application: linked list, stack, queue, array, binary search tree, red-black tree hash table, trie, heap?

    2. Select three data structures from the above list that are not totally inappropriate. Propose and evaluate designs using the selected data structures. The evaluation should consider factors such as the running time, memory requirements, and code complexity of the three alternatives.

  2. *An operating system needs to keep track of the print jobs that are assigned to each printer, so that when one print job finishes, it can send the next one to the printer. Although there might be many printers, let us restrict our attention to the data structure that contains the jobs for one printer.

    1. Suppose that the print jobs are to be handled on a “first come, first serve” basis. What kind of data structure is most suitable? How does this data structure compare with a linked list for efficiency?

    2. Suppose that, instead, print jobs may be submitted with different priorities, and we always serve the job with highest priority next. What kind of data structure is most suitable? How does it compare in efficiency with a linked list?

Revision History