College of Computer & Information Science Fall 2003 Northeastern University Handout 2 CS G713: Advanced Algorithms 10 September 2003

Questionnaire

Name:

Email address (please write legibly):

Major:

1. Have you taken an undergraduate course on the design and analysis of algorithms?

2. Have you taken MTH 3001 (Foundations in Mathematics & Theory) or an equivalent course in discrete mathematics? Have you taken COM 3150 (Algorithms and Data Structures) or equivalent? (If your answer to the above question is “yes”, then you may skip these questions)

3. Are you familiar with the following data structures?

• Linked lists:

• Stacks and queues:

• Binary search trees:

• Balanced binary search trees (e.g., AVL trees, 2-3 trees, red-black trees, B-trees):

• Hash tables:

4. Which sorting algorithms have you learned? (List up to five algorithms.) For each one, write “yes” if you also analyzed the running time and “no” if not.

5. Are you familiar with the following graph algorithms?

• Depth-first search:

• Breadth-first search:

• Topological sort:

6. Are you familiar with asymptotic analysis – the O(·), o(·), and Ω(·) notation, and techniques for solving recurrences?

7. Are you comfortable with elementary probability theory: the notions of random variable, expectation, and conditional probability?