# 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.
• Find kth smallest element using Heaps. Will you use a Heap or Hoare’s partition?
• Hoare’s partition will take O(nlog n)
• Quick sort: timing O(nlog 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(2n), and O(nn), and an O(Nn^n)  algorithm.
• 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.