Daily Problems

Working on these problems is the best way to practice the lessons you learn in the lecture. They are here as a service to you.

• 8/28 Problem 1-6
• 9/2 Problem 2-12
• 9/4 Problem 2-20
• 9/9

  Suppose you want to design a dictionary class, D, using a stack class, S, as your underlying structure. (Perhaps you are working in a restricted environment.)

  You may assume S.push(pointer), S.pop(), and S.isEmpty() in \( \mathcal{O}(1) \) time, you may make \( \mathcal{O}(1) \) stacks, and you need not worry about overflow. What would be the asymptotic worst-case complexity of your D.Search(key), D.Insert(pointer), D.Delete(pointer), D.Successor(pointer), D.Predecessor(pointer), D.Minimum(), and D.Maximum()? (Given a pointer to an object you can access that object's key.)

• 9/11 Problem 3-12
• 9/16 Problem 3-8
• 9/18 Problem 4-2
• 9/23

  Given n points in three dimensions, e.g. [(1,2,3), (6,5,4)], design an algorithm which finds the closest two. What is the complexity of your approach?

• 9/25 Problem 4-14
• 10/7 Problem 5-8
• 10/9 Problem 5-1
• 10/14 Problem 5-2
• 10/21 Problem 6-2
• 10/23 Problem 6-6
• 10/28 Problem 6-20
• 10/30 Problem 6-24
• 11/13 Problem 7-2
• 11/18 Problem 7-7
• 11/20 Problem 8.3 a or b
• 11/25 Problem 9-16
• 12/2 Problem 9-26