DOC PREVIEW
GSU CSC 2010 - LectureSlides905

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 46 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1The central role of algorithms in computer science: examplesLayering: physical communicationThe central role of algorithms in computer scienceChapter 5: AlgorithmsDefinition of AlgorithmIn-Class ExerciseSlide 8Figure 5.2 Folding a bird from a square piece of paperPseudocode PrimitivesFigure 5.3 Origami primitivesFigure 5.4 The procedure Greetings in pseudocodeIn-class ExerciseSlide 14Polya’s Problem Solving StepsGetting a Foot in the DoorAges of Children ProblemFigure 5.5ExerciseSlide 20Iterative StructuresFigure 5.6 The sequential search algorithm in pseudocodeFigure 5.7 Components of repetitive controlFigure 5.8 The while loop structureFigure 5.9 The repeat loop structureSlide 26Figure 5.10 Sorting the list Fred, Alex, Diana, Byron, and Carol alphabeticallyFigure 5.11 The insertion sort algorithm expressed in pseudocodeRecursionFigure 5.12 Applying our strategy to search a list for the entry JohnFigure 5.13 A first draft of the binary search techniqueFigure 5.14 The binary search algorithm in pseudocodeFigure 5.15Figure 5.16Figure 5.17Slide 36Slide 37Algorithm EfficiencyFigure 5.18 Applying the insertion sort in a worst-case situationFigure 5.19 Graph of the worst-case analysis of the insertion sort algorithmFigure 5.20 Graph of the worst-case analysis of the binary search algorithmSoftware VerificationChain Separating ProblemFigure 5.21 Separating the chain using only three cutsFigure 5.22 Solving the problem with only one cutFigure 5.23 The assertions associated with a typical while structureChapter 5Algorithms © 2007 Pearson Addison-Wesley.All rights reserved© 2007 Pearson Addison-Wesley. All rights reserved0-2The central role of algorithms in computer science: examples© 2007 Pearson Addison-Wesley. All rights reserved0-3Layering: physi cal communication applicationtransportnetworklinkapplicationtransportnetworklinkapplicationtransportnetworklinkapplicationtransportnetworklinknetworklinkdatadata© 2007 Pearson Addison-Wesley. All rights reserved0-4The central role of algorithms in computer science© 2007 Pearson Addison-Wesley. All rights reserved0-5Chapter 5: Algorithms•5.1 The Concept of an Algorithm•5.2 Algorithm Representation•5.3 Algorithm Discovery•5.4 Iterative Structures•5.5 Recursive Structures•5.6 Efficiency and Correctness© 2007 Pearson Addison-Wesley. All rights reserved0-6Definition of AlgorithmAn algorithm is an ordered set of unambigu ous, exec utable steps that defines a terminating process.© 2007 Pearson Addison-Wesley. All rights reserved0-7In-Class Exercise•In what sense do the steps described by the following list of instructions fail to constitute an algorithm?–Step1. Take a coin out of your pocket and put it on the table;–Step2. Return to step 1Return to step 1Return to step 1 if there is a coin in the pocket.© 2007 Pearson Addison-Wesley. All rights reserved0-8Chapter 5: Algorithms•5.1 The Concept of an Algorithm•5.2 Algorithm Representation•5.3 Algorithm Discovery•5.4 Iterative Structures•5.5 Recursive Structures•5.6 Efficiency and Correctness© 2007 Pearson Addison-Wesley. All rights reserved0-9Figure 5.2 Folding a bird from a square piece of paper© 2007 Pearson Addison-Wesley. All rights reserved0-10Pseudocode Primitives•Assignment name  expression•Conditional selection if condition then action•Repeated execution while condition do activity»repeat activity until condition•Procedure procedure name (generic names)© 2007 Pearson Addison-Wesley. All rights reserved0-11Figure 5.3 Origami primitives© 2007 Pearson Addison-Wesley. All rights reserved0-12Figure 5.4 The procedure Greetings in pseudocode© 2007 Pearson Addison-Wesley. All rights reserved0-13In-class Exercise•1. Does the following program represent an algorithm in the strict sense? Why or why not?Count 0;While (Count not 5) do(Count  Count + 2)© 2007 Pearson Addison-Wesley. All rights reserved0-14Chapter 5: Algorithms•5.1 The Concept of an Algorithm•5.2 Algorithm Representation•5.3 Algorithm Discovery•5.4 Iterative Structures•5.5 Recursive Structures•5.6 Efficiency and Correctness© 2007 Pearson Addison-Wesley. All rights reserved0-15Polya’s Problem Solving Steps•1. Understand the problem.•2. Devise a plan for solving the problem.•3. Carry out the plan.•4. Evaluate the solution for accuracy and its potential as a tool for solving other problems.© 2007 Pearson Addison-Wesley. All rights reserved0-16Getting a Foot in the Door•Try working the problem backwards•Solve an easier related problem–Relax some of the problem constraints–Solve pieces of the problem first (bottom up methodology)•Stepwise refinement: Divide the problem into smaller problems (top-down methodology)© 2007 Pearson Addison-Wesley. All rights reserved0-17Ages of Children Problem•Person A is charged with the task of determining the ages of B’s three children.–B tells A that the product of the children’s ages is 36.–A replies that another clue is required.–B tells A the sum of the children’s ages.–A replies that another clue is needed.–B tells A that the oldest child plays the piano.–A tells B the ages of the three children.•How old are the three children?© 2007 Pearson Addison-Wesley. All rights reserved0-18Figure 5.5© 2007 Pearson Addison-Wesley. All rights reserved0-19Exercise•Homework 1, 2, 4 in Page 213© 2007 Pearson Addison-Wesley. All rights reserved0-20Chapter 5: Algorithms•5.1 The Concept of an Algorithm•5.2 Algorithm Representation•5.3 Algorithm Discovery•5.4 Iterative Structures•5.5 Recursive Structures•5.6 Efficiency and Correctness© 2007 Pearson Addison-Wesley. All rights reserved0-21Iterative Structures•Pretest loop:while (condition) do (loop body)•Posttest loop:repeat (loop body) until(condition)© 2007 Pearson Addison-Wesley. All rights reserved0-22Figure 5.6 The sequential search algorithm in pseudocode© 2007 Pearson Addison-Wesley. All rights reserved0-23Figure 5.7 Components of repetitive control© 2007 Pearson Addison-Wesley. All rights reserved0-24Figure 5.8 The while loop structure© 2007 Pearson Addison-Wesley. All rights reserved0-25Figure 5.9 The repeat loop structure© 2007 Pearson Addison-Wesley. All rights reserved0-26•Convert the pseudocode routinZ 0X 1while (X<6) do (ZZ+X; X X+1) to an equivalent routine using a repeat statement.answer: Z 0X 1re peat (ZZ+X; X X+1) until (X=6)•(Extra Point Question) Page


View Full Document

GSU CSC 2010 - LectureSlides905

Download LectureSlides905
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view LectureSlides905 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view LectureSlides905 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?