# Memo for Examination 2011

Exam for the COS 212

- Chapter 4 or three on big O notation (From the text book).
- Linear search– must be able to give or describe the algorithm and its timing.
- Suppose 85% of the search takes place in the first 5% of the list, what is the average time?
- 0.85(5+1/2)+0.15(5+(95+1)/2)
- Can linear search be fine tuned?
- Binary search– be able to give or describe algorithm and timing.
- E.g. how long does it take to find an element not in the list?
- How many probes does it take to look 123455 …
- Heaps/priority queues.
- Be able to explain the time complexity of the building a heap top-down and building a Heap bottom up and code them.
- Explain sorting with heap and explain its space and time complexity.
- Be able to program sorting using a Heap.
- What algorithm do you know that use Heaps to speed them up, give a list.

- E.g. how long does it take to find an element not in the list?

- Find kth smallest element using Heaps. Will you use a Heap or Hoare’s partition?
- Hoare’s partition will take
*O*(*n*log*n*) - Quick sort: timing
*O*(*n*log*n*) ,partition, timing was dealt with in details in class notes. Merge sort, Timing. Find the kth smallest/largest element in the list with out sorting hint use partition or use a Priority list built bottom up. - Boyer Moore, Knuth Morris Pratt, Rabin Karp versus Brute force, know all timing. Know details of algorithms, be able to fill in a gaps in given programs.
- Tries
- Huffman encoding and decoding, know the property Huffman. (How does Wayner encryption- based on Huffman coding- work. No to Stress J )
- Be able to describe efficient spelling checkers given constrains such as: “Using a preprocessed dictionary the checking algorithm must independent of the size of the dictionary” or “The program may not use a method that relies on hashing(use rather Tries).” Or “The dictionary and data must be processed at the same time.”
- Longest common subsequence (LCS). What is the dynamic programming?
- Graphs: Definition, Depth-first search DFS for trees, Breadth First Search( BFS) for trees. DFS,BFS for graphs traversal. Dijkstra shortest path algorithm, Krushkal algorithm and Prim-Jarnik Algorithm for Minimal spanning Trees. Timing of each, you must be able to explain the timing.
- For graphs also be able to explain the data structure to store them: edge list, node list, adjacency, etc.
- Topological sorting
- Be able to demonstrate all the algorithms, given a small set of data.
- Give and explain an
**O(2**, and^{n})**O(n**algorithm.^{n}), and an O(N^{n^n}) - What is log base b of any number given as a base b number in term of its digits?
- What is the biggest unsigned/signed number that can be represented using 16, 32, 64 or 128 bits – give the answer without using calculator.
- How long will the Towers of Hanoi using 64 disks. Estimate with out using a calculator. Be able to derive the time complexity T(N)=2^n -1 for the Tower of Hanoi.
- Understand and able to derive and explain.
- T(N)= 2T(N/2) +cN = O(N log N) – the time taken by divide and conquer algorithms.
- Be able to prove that the Halting problem is non-computable.
- Define totality, equivalence.
- What is meant by partial computability?
- What is proof system?
- Give a class of algorithms that are considered efficient?
- When do we consider an algorithm intractable?
- What is meant by NP completeness?
- Understand and be able to explain what the practical implication are of knowing that an algorithm is NP complete.
- Give a list of at least 5 problems that are NP complete.
- Be able to explain how to go about proving that a given problem is NP complete.

PS: I do not stand liable for any incorrect information since i have collected this information as it is.

I see the Jigmaster is at it again. Thx, buddy.

No problem, As long as it helps…