J. Correia Lopes

FEUP/DEI & INESC TEC

User Tools

Site Tools


teach:fpro:lectures:15

T: 20/11/2018

Master in Informatics and Computing Engineering
Programming Fundamentals
Instance: 2018/2019


Lecture #15 :: 20/11/2018

Goals

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

  • 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

  • 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]
  • Exercises

Bibliography

  • Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers, How to Think Like a Computer Scientist — Learning with Python 3 (RLE), 2012 (Chapter 14) HTML

Materials

  • J. Correia Lopes, Script and illustrations, 15-list-algorithms.pdf
  • FPRO, 2018/19, Python code, Lecture's on GitHub
  • Brad Miller and David Ranum, Problem Solving with Algorithms and Data Structures using Python (Section 5.3, Section 5.4) HTML

Summary

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

FPRO, 2018/19

« Previous | Index | Next »

teach/fpro/lectures/15.txt · Last modified: 21/11/2018 11:26 by Correia Lopes