Data Structure and Algorithms
Q1. What are some practical examples of stacks, especially in computing?
Q2. Evaluate 24 * 3/8 + 7*8/9, (24 * 3)/8 + 7*8/9, (24 * 3/(8 + 7)*8/9, (24 * 3/8) + 7*8/9
Q3. Write Java code to evaluate the expressions in 2
Q4. How do stacks, queues and bags differ both in definition and implementation
Q5. Stacks can be implemented using different approaches such as resizing arrays or linked lists. Which is better and why?
Q6. Queues can be implemented using different approaches such as resizing arrays or linked lists. Which is better and why?
Q7. When is iteration used? What are its benefits?
Q8. Refer to Questions 4 and 5 looked at the efficacy of linked lists or resizing arrays for implementations of stacks and queues. Redo these 2 questions expressing each implementation in terms of operations using N.
Q9. Use the Java code provided for selection sort, insertion sort and shellsort to devise experiments to demonstrate the veracity of the propositions given for the analysis of selection sort , insertion sort
Q10. Implement the code on 7 – 12, in particular the trace on 12
Q11. Devise experiments to demonstrate the proposition on slides 16 and 20
Q12. Using your code for mergesort and previous code for insertion sort, find the cutoff point for your code when mergesort becomes more efficient than insertion sort
Q13.Why is quicksort efficient in general?
Q14.When is quicksort particularly efficient, and when is it particularly inefficient?
Q15. Slide 52 provides a useful summary of the different sorting algorithms.
For each algorithm, provide an application from real life for which you think the particular algorithm might be the most suitable sort for that application. Take into account, the speed of the algorithm, the space the algorithm requires, stability, the size of the data in the problem, the speed of your computer, etc.
Q16. What is the advantage of a binary search tree over a binary tree?
Q17. Define min( ), max( ), floor( ), ceiling( ) for a BST.
Q18. How do insertions and deletions differ in a BST? What are the practical implications of this.
Q19. Take an initially empty tree. Insert the keys DATASTRUCTURES into the tree, associating value i with the ith key. How many compares are needed?
Q20. What are the advantages and disadvantages for 2-3 trees for searching?
Q21. What approach can you use for overcoming some of the disadvantages and why is it more successful than straight 2-3 trees?
Q22. Draw the 2-3 tree that results from inserting the keys XMONYIBSADT in that order.
Q23. What will be the height of the tree drawn in 3?
Q24. Why use Hash Tables?
Q25. Experiment with hashCode() in Java on a large dataset (of size M) (find one on the web that you can use) to show that the hash functions distribute keys fairly evenly between 0 to M-1.
Q26. What are common problems of hashing?
Q27. Why are StringSorts stable?
Q28. Why are StringSorts efficient compared with other types of sorts?
Q29. Are there times when StringSorts are not efficient? If yes, when and why does this occur?
Q30. If the answer to 3 is yes, what, if anything, can be done to make the sort more efficient?