CSci 271 Lecture Notes

Week Four, Wednesday: Algorithms and their Complexity

Introduction

Example 1: Find the largest element in a sequence of integers.

Example 2: Show that Algorithm 1 has the all the properties:

• Input
• Output
• Definiteness
• Finiteness
• Effectiveness
• Generality

Does the bogo sort have these properties?

Searching Algorithms

Binary search: split a sorted list in half, determine which half the target is in, and repeat.

Example 3: binary search.

Algorithm 3: binary search.

Complexity

Example 1: Describe the time complexity of Algorithm 1 (finding the max) of section 2.1.

Example 2: Describe the time complexity of the linear search algorithm.

Example 3: Describe the time complexity of the binary search algorithm.

Example 4: Describe the average-case performance for the linear search algorithm.

Homework Assignment

Chapter 1.8: 6, 20.
Chapter 2.1: 4
Chapter 2.2: 2, 10.