Week 8- Introduction to Data Structures and ADTs

Reading Guide

For this week we are going to do some reading from a Data Structures textbook written by Brad Miller and Dave Ranum at Luther College up in Wartburg.  The materials are available free online.  I have tried to give you direct links to the materials.  But if what you see below doesn't seem to mesh with what you see when you click the link, please let me know and I will fix it.

• 1.5. Why Study Data Structures and Abstract Data Types?
• 1.6. Why Study Algorithms?
  • In some ways this section is late - we have already studied two searching and five sorting algorithms.
  • But we also will study a lot more.  So this reintroduces the course
• 2.1. A Basic implementation of the MSDie class
  • You can glance at the material at the top of the page but ignore the bullets labeled "Each class should" because, frankly, we rarely will address this except, possible, for the comparables.
  • Instead, revisit how classes work in Python and study the Die Class (which we will use next week).
  • Note, this is from the 2nd edition of the book rather than the 3rd edition like the other sections. But I think it is really good.
• 3.1. Objectives
• 3.2. What Are Linear Structures?
• 3.3. What is a Stack?
• 3.4. The Stack Abstract Data Type
  • To me, this is the key section of the discussion about a Stack. 
  • You will need to become very familiar with the primary operations of a Stack.
• 3.5. Implementing a Stack in Python
  • There is a lot of material here.  Don't rush this section
• 3.6. Simple Balanced Parentheses
• 3.7. Balanced Symbols (A General Case)
• 3.10. What Is a Queue?
• 3.11. The Queue Abstract Data Type
  • To me, this is the key section of the discussion about a Queue. 
  • You will need to become very familiar with the primary operations of a Queue.
• 3.12. Implementing a Queue in Python
  • Similarly, give this section some time.
• 3.13. Simulation: Hot Potato
• 3.14. Simulation: Printing Tasks

Video Resources

• Crash Course CS: Data Structures

Activity

• Get together with a partner.
• Discuss any questions you had.  See if you can work through them together.
• If not, PLEASE send me an email and let's chat.