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.
Advertisements
  1. I see the Jigmaster is at it again. Thx, buddy.

  2. No problem, As long as it helps…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: