CSC 225 Midterm exam Study Aid: Fall 2017

The best references for this material are:

1. The class notes.
2. The free book, Chapters 1-3.
3. Assignment and lab exercises: see the Assignments on connex.
4. Resources on connex.
5. Once we are past the mathematical preliminaries, the class text.

You are responsible for the material covered in class. You also are responsible for all the assignment questions.

For all algorithms in this class, you should be able to:

1. Give a high-level description of the algorithm.
2. Be able to convert the high-level description into more detailed pseudo-code (similar to JAVA or C but syntax is not important).
3. Create a correct JAVA program.
4. Use Big Oh and Omega notation to analyse the best and worst case running times.
5. Be able to describe the best and worst case inputs.
6. Be able to analyse similar algorithms in the same manner.
7. Be able to read pseudocode or JAVA code to figure out what it is doing.

Definitions

1. The comparison model
2. The sorting problem
3. Optimal
4. Big Oh, Omega, Theta
5. Worst, best and average cases
6. Maximum element of an array
7. Loop invariant
8. Complete binary tree, height of a rooted tree

Mathematical Concepts

1. Log, floor and ceiling functions.
2. Finding upper and lower bounds by under and over estimating each term in a sum
3. Proving Big Oh relationships
4. Trick for evaluating sum for i = 0 to n of 2 ⁱ
5. Trick for evaluating sum for i = 1 to n of i
6. Formulas for complete binary trees
7. Understand iteration and recursion
8. Inductive definitions
9. Induction for formulas and also to reason about programs
10. Proving loop invariants
11. Solving recurrences by repeated substitution
12. Determining the recurrence relations for time complexity or a program or for counting exact numbers of certain designated statements.

Some of the algorithms we have analysed are:

Linked list algorithms:

Make sure you can draw pictures to step through the operations of code that manipulates linked lists. Also, you should be able to do new things using lists (iteratively and recursively).

1. Add to front
2. Add to rear with a rear pointer
3. Concatenating lists
4. Reverse a list
5. Storing and manipulating big integers using linked lists.

Binary search

1. An iterative algorithm
2. A recursive algorithm

Find the maximum (4 algorithms):

1. Iterative find max
2. Begin_max
3. Middle_max
4. End_max

Sorting algorithms:

1. MaxSort
2. MergeSort
3. QuickSort