JCL

FEUP/DEI & INESC TEC

User Tools

Site Tools


teach:fpro:lectures:19

LE19: 04/01/2021

Master in Informatics and Computing Engineering
Programming Fundamentals
Instance: 2020/2021


Lecture #19 :: 04/01/2021

Goals

By the end of this class, the student should be able to:

  • Explain and implement linear search and binary search
  • Describe other algorithms that work with lists
  • Compare the performance of those algorithms working with a realistic problem

Content

  • List algorithms
    • The linear search algorithm [14.2]
    • A more realistic problem [14.3]
    • Binary Search [14.4]
    • Removing adjacent duplicates from a list [14.5]
    • Merging sorted lists [14.6]
    • Alice in Wonderland, again! [14.7]

Bibliography

  • Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers, How to Think Like a Computer Scientist — Learning with Python 3 (RLE), 2012 HTML (Chapter 14)
  • Brad Miller and David Ranum, Problem Solving with Algorithms and Data Structures using Python HTML (Section 6.3, Section 6.4)

Materials

Summary

  • Algorithms that work with lists. The linear search algorithm. Binary Search. Merging sorted lists.

FPRO, 2020/21

« Previous | Index | Next »

teach/fpro/lectures/19.txt · Last modified: 03/01/2021 17:43 by Correia Lopes