Searching and Sorting

Learn How to Efficiently Process Data
Published

March 24, 2025

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

  • Tuesday and Thursday: 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
  • Friday: Submit algorithm engineering project five, start algorithm engineering project six, and give presentations for the second algorithm all-hands session

Project

Goal

To build and use a Python program, called lcsfinder, that runs benchmarks to study the performance of finding the longest common sub-sequence of data values

Steps

  • Click the link provided in Discord to get started on this project
  • Use Longest Common Subsequence Finder as your template repository
  • Install the project’s dependencies using devenv and/or poetry
  • Follow the instructions to complete the project:
    • Week 1: Implement all of the modules in lcsfinder
    • Week 2: Design and conduct experiments and document experimental results
  • Schedule office hours if you have questions
Student Insights

Students who completed this project shared these insights:

  • “A key takeaway is that while a simple recursive implementation may seem straightforward, it can lead to inefficient code with poor time complexity.” Alish Chhetri

  • “In this project we learned about finding the longest common subsequence (LCS). We evaluated our algorithm’s performance by running a doubling experiment. We explored a dynamic function and a recursive function, along with a third that simply calculated the length of the computed LCS. Finally, we compared the pros and cons of these different methods, revealing some surprising results!” Rebekah Rudd

Slides

Full Screen: Week Eleven: Searching and Sorting

Back to top