CSC 225 Final exam Study Aid: Fall 2013

You are responsible for the material covered in class. You also are responsible for all the assignment questions. This will be updated closer to the time of the final exam. The course curriculum for CSC 225 has been changed since the last time I taught this class. As a result, some of the old final exam questions may no longer be relevant.

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, worst and sometimes average running times and space requirements.
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 psuedocode or JAVA code to figure out what it is doing.
8. Analyse the space complexity.

Lower bounds

1. Omega(n log ₂ n) for any sorting algorithm
2. n-1 key comparisons to find the max of n data items

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. Partial orders and Hasse diagrams
3. Finding upper and lower bounds by under and over estimating each term in a sum
4. Proving Big Oh relationships
5. Trick for evaluating sum for i = 0 to n of 2 ⁱ
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

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. Two algorithms for concatenating lists (one O(1) and the other O(n)
4. Delete from a list given a previous pointer O(1)
5. Reverse a list.

Find the maximum (4 algorithms):

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

Sorting algorithms:

1. Four sorting algorithms based on these 4 algorithms for finding the max.
2. Mergesort
3. Quicksort
4. Radix sort
5. Max sort
6. Heapsort

Heaps:

1. Two algorithms for builing a heap- O(n) and O(nlogn)
2. Bubble up and bubble down in heaps
3. Heapsort
4. Array storage which avoids use of pointers.

Binary search trees:

1. Insert
2. Traverse in preorder, post order, in order
3. Binary tree sort: insert the keys then traverse in order.

Graphs:

1. Traverse using adjacency matrix/adjacency list for BFS and DFS.
2. Add edge
3. Check is an edge is present
4. Stacks and Queues in arrays (mentioned during BFS/DFS)

Hashing:

1. Open addressing
2. Closed addressing

Minimum Weight Spanning Trees

1. Kruskal's algorithm (the greedy approach that first sorts the edges by weight and then adds edges in order if they do not make a cycle with the edges already in the tree).
2. The union/find data structure for connected components.

Some material now in CSC 226

The curriculum has changed for CSC 225. The following algorithms appear on old final exams will not be on your final exam.

1. The Dijkstra/Prim algorithm for minimum weight spanning trees.
2. Boruvka's algorithm for minimum weight spanning trees.
3. Shortest Path problem