# Memo for Examination for Data structure and Algorithms

This is not exactly what you will be expecting in the exam for Mr. Dodds. But this might help as these points were provided by himself. Also please note that there might be some spelling errors. I have tried my best to provide you guys with some of the links with in the document for the data structures.

Here it is:

## 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.

Advertisements

Posted on October 19, 2011, in Uncategorized and tagged Computer Science 212, Data structure and algorithm, examination, Final, Mr Dodds. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0