REM 100 Lecture Notes - Lecture 24: Binary Tree, Memory Stick, Linear Search

• School: Simon Fraser University
• Department: Resource & Environmtl Mgmt
• Course: REM 100
• Professor: Jonn Axsen

Document Summary

Answers to homework 1: 13 1. 2 3 what is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine? . Find the smallest n > 0 such that 100n2 < 2n. Use a calculator and do a binary search . I tried n = 10, 20, 15, . n. At n = 15 you will nd that 2n exceeds 100n2: 21 2. 1 3 consider the searching problem: Input: a sequence of n numbers a = ha1, a2, . Output: an index i such that v = a[i] or the special value nil if v does not appear in a. Write pseudocode for linear search, which scans through the sequence, looking for v. 5. i 1 while i < length[a] and a[i] 6= v if a[i] 6= v do i i + 1 then i nil.