\( \newcommand{\blah}{blah-blah-blah} \newcommand{\eqb}[1]{\begin{eqnarray*}#1\end{eqnarray*}} \newcommand{\eqbn}[1]{\begin{eqnarray}#1\end{eqnarray}} \newcommand{\bb}[1]{\mathbf{#1}} \newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\nchoose}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \newcommand{\defn}{\stackrel{\vartriangle}{=}} \newcommand{\rvectwo}[2]{\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \newcommand{\rvecthree}[3]{\left(\begin{array}{r} #1 \\ #2\\ #3\end{array}\right)} \newcommand{\rvecdots}[3]{\left(\begin{array}{r} #1 \\ #2\\ \vdots\\ #3\end{array}\right)} \newcommand{\vectwo}[2]{\left[\begin{array}{r} #1\\#2\end{array}\right]} \newcommand{\vecthree}[3]{\left[\begin{array}{r} #1 \\ #2\\ #3\end{array}\right]} \newcommand{\vecfour}[4]{\left[\begin{array}{r} #1 \\ #2\\ #3\\ #4\end{array}\right]} \newcommand{\vecdots}[3]{\left[\begin{array}{r} #1 \\ #2\\ \vdots\\ #3\end{array}\right]} \newcommand{\eql}{\;\; = \;\;} \definecolor{dkblue}{RGB}{0,0,120} \definecolor{dkred}{RGB}{120,0,0} \definecolor{dkgreen}{RGB}{0,120,0} \newcommand{\bigsp}{\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;} \newcommand{\plss}{\;\;+\;\;} \newcommand{\miss}{\;\;-\;\;} \newcommand{\implies}{\Rightarrow\;\;\;\;\;\;\;\;\;\;\;\;} \newcommand{\prob}[1]{\mbox{Pr}\left[ #1 \right]} \newcommand{\exval}[1]{\mbox{E}\left[ #1 \right]} \newcommand{\variance}[1]{\mbox{Var}\left[ #1 \right]} \)

How to prep for Exam 1

About the exam:

The exam is closed-book, closed-notes, closed everything, in the same room as our class (SEH 1300/1400) for all students including extended-time students.
You will need to put away everything (all devices, bags, laptop etc). You are advised to visit the facilities before starting, and to come early.
Structure of the exam (total time: 25 minutes)
- Three multiple-choice questions (suggested time: 9 minutes)
- Two written answers (suggested time: 16 minutes)
Questions will be distributed on paper and answers expected on an answer sheet.
You will need to turn in both the questions and answers. Note: the exam/questions will not be returned to you.

How to prep:

Review your own solutions to the non-programming module exercises. A slightly tweaked module exercise is fair game for the exam.
Recall from the quizzes the material you may need to review.
Likewise review based on the homeworks and assignments thus far.
Review at least the following core concepts:
- Module 1: Big-Oh, the well-known functions, the "upper triangle" argument, analyzing code snippets
- Module 2: The main sorts (bubble, quick, merge, heap), the binary heap data structure.
- Module 3: The main operations (insert, search) on the different trees in this module, and deletion for binary trees.
- Module 4: Hashing, tries.
- Module 5: Rabin-Karp, Boyer-Moore-Horspool, using DFAs, regular expressions, NDFAs.

Sample questions

One set of sample questions are the non-programming module exercises, or slightly modified versions of them.

See sample quiz questions for examples of multiple-choice questions

Here are examples of questions that need written answers:

Show that it's possible to have two functions \(f(n)\) and \(g(n)\) where neither \(f(n) = O(g(n)) \) nor \(g(n) = O(f(n)) \) is true.

Insertion-sort is generally faster than Mergesort for small arrays such as \(n \leq 10\). Write pseudocode to show how you can integrate Insertion-sort into Mergesort so that all array segments of length at most 10 get sorted by Insertion-sort.

Use an example to explain the difference between a Map and a Set.

Insert the following numbers into a Binary Search Tree in the order given: 50, 30, 70, 20, 40, 60, 80. Then show the steps in deleting 30.

Show with an example, how doubleRotateLeftChild works in an AVL tree.

What role does a stack play in a multi-way tree?

If 30,000 English words are to be stored in a hashtable, write pseudocode for insertion, assuming the hashtable uses arrays instead of linked lists.

Explain why a full trie has \(O(n)\) interior nodes.

If, in the Rabin-Karp algorithm with a pattern of size \(m\) and text of size \(n\), the first signature calculation in the text takes \(O(m)\) and each subsequent signature calculation in the text takes \(O(\log m)\), how long does the whole algorithm take?

Construct a DFA for the regular expression \((A|B)^*(AB|BA)\).

Note:

The above sample questions are only a guideline. Do NOT read anything into the particular topics selected above.
Answers to the above questions will not be provided, nor will the TAs do these in the lab. The idea is for you to develop confidence in answering the questions yourself.