Computer Science 2210A/B- Midterm Exam Guide - Comprehensive Notes for the exam ( 75 pages long!)
12 Oct 2017
School
Department
Course
Professor
Document Summary
In this and next lectures we introduce the con-cepts of: Given a set s of elements and a particular ele-ment x the search problem is to decide whether x s. This problem has a large number of applications: For simplicity, let us assume that s is a set of n integers stored in non-decreasing order in an array l. Consider, for example, the method that is used to look-up a name xin the phone book: Compare x with any name y located near the middle of the phone book. If x precedes y in lexicographic order, then con-tinue the search for x on x = y the search ends. the first half of the phone book. Otherwise, continue the search for x on the second half of the phone book. Criteria that we can use to compare algorithms: Consequently, we define two types of complexity functions: Space complexity: amount of memory that the algorithm needs.
