Textbook Notes (369,205)
United States (206,227)
Chapter 8

Chapter8.docx

3 Pages
130 Views

Department
Computer Science
Course Code
CMPT 120L-115
Professor
Matthew Johnson

This preview shows page 1. Sign up to view the full 3 pages of the document.
Description
A Balanced Introduction to Computer Science, 3 Edition David Reed Chapter Eight: Algorithms and Programming Languages A. Algorithms – step-by-step sequences of instructions for carrying out some task 1. Programming is the process of designing and implementing algorithms for a computer or program to carry out a. JavaScript programs instruct the browser to carry out particular tasks (or displaying a message) 2. Algorithms in the Real World a. Should not be vague or misleading b. Computers require algorithmic steps to be stated precisely B. Designing and Analyzing Algorithms 1. Four steps to solving problems created by George Polya a. Understand the problem b. Devise a plan c. Carry out your plan d. Examine the solution 2. Problems can be solved multiple different ways 3. Algorithm Analysis a. When more than one algorithm is available, analyze each to find the “better” one i. Based on personal preference (simplicity vs. accuracy) b. Algorithm’s performance is measured by the speed at which the algorithm or program running it accomplishes it 4. Big-Oh Notation – represent an algorithm’s performance in relation to the size of the problem a. O(N) – requires time proportional to the size of the problem b. O(logN) – requires time proportional to the log of the problem size C. Algorithm Example: Searching a List 1. Computers store and maintain large a mounts of information and search through the data for particular values 2. Sequential search – examine each list item in sequential order until desired item is found (simplest algorithm) a. Steps for a sequential search: i. Start at the beginning of the list ii. For each item: 1) examine it. If it’s the item you’re looking for, you’re done. 2) if it’s not, move on to the next b. If you get to the bottom and cannot find it, it’s not in the list c. Simple algorithm that is time consuming 3. Binary search – each check cuts the list that must be searched in half a. More efficient b. Only for ordered lists c. Steps for a binary search: i. Inspect the entry in the middle of the list (if this is what you’re looking for, you’re done) ii. If this middle point is before your item, search the second half of the list iii. If it is after, search the first half of the list d. Repeatedly cutting the list in half makes it converge on the item you’re searching for 4. Algorithm Analysis a. Time required to locate a list item using a sequential search is proportional to the size of the list i. It is an O(N) algorithm, where N is the number of items in the list b. In a binary search, each examination of an entry rules out an entire range of entries i. It is an O(logN) algorithm, which times the time required to find a list item
More Less

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.