Searching and Sorting

Learn How to Efficiently Process Data

Exploration

• Read chapters 11 through 14 in A First Course on Data Structures in Python
• Explore algorithms that perform searching and sorting in the ds2 package of donsheehy/datastructures. Can you add debugging statements to trace how these algorithms work? Can you prove the worst-case time complexity of these algorithms?
• Review chapters to confirm that you understand the worst-case time complexities

Activities

• Monday and Wednesday: Searching and Sorting
  • Explore how to implement searching and sorting algorithms Python
  • Apply a new algorithmic paradigm called dynamic programming
  • Learn more about the mergesort and quickselect algorithms
  • Examine Python source code segments to illustrate key points
• Thursday: Continue algorithm engineering project
• Friday: Start new algorithm all-hands project

Project

Goal

To build and use a Python program, called listconcatenator, that runs benchmarks to study the performance of combining data into different types of lists

Steps

• Use listconcatenator as your template repository
• Install the project’s dependencies using devenv
• Follow the instructions to complete the project:
  • Week 1: Implement all of the modules in listconcatenator
  • Week 2: Design and conduct experiments and document experimental results
• Schedule office hours if you have questions

Slides

Full Screen: Week Eleven: Searching and Sorting