Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Searching11-11-2011Opening DiscussionMinute essay comments:You kids use computer search for EVERYTHING!(Even answering how many seconds are in a year.)Binary SearchIf the data is sorted, we can do something much better.We check the middle to see if it matches. If it does, return it. Otherwise, see if what we want is above or below the middle and repeat the process on only that half.This continually divides the things we are searching in half.Order?Performance of Binary SearchDividing something by a fixed fraction repeatedly leads to O(log n) speed.O(log n) is much better than O(n) when n is large. To see this, consider a base 2 log for 1000, 1000000, or 1000000000.Computer MemoryThe memory that a program uses is broken into two different parts.Stack – This holds local variables. Every function/method call gets a new “frame” on the stack. Efficient, but limited.Heap – All objects in Scala are allocated on the heap. It is big and flexible, but disorganized.Other languages allow you more direct control over memory. This has the potential to lead to errors.Classification of BugsWe classify the errors that occur in programs in three broad groups.Compile Errors – Found by the compiler. Gets a reasonable error message and line number.Runtime Errors – Program crashes while running for a particular input. Gives type of error and line.Logic Errors – Code runs fine, but does wrong thing. No information given to help you.You want to have your errors be higher up on this list because it gives you more information and makes it easier to fix.MotivationWe have been using “flat” text files to store things.Advantage: it is human readable and simple.Disadvantages: everything else.SlowLargeLacks meaningHard to editHard to debugXMLThe eXtensible Markup Language (XML) is a standard for text encoding of data.If you have ever done HTML, XML is similar. XHTML is HTML that follows the XML standard.The advantage of XML is that it can encode pretty much anything and it is human readable text.The downside is that it can be very verbose.Composed of markup (between < and > or & and ;) or content (anything not markup).TagsThe primary markup used in XML is the tag.A tag begins with a < and ends with a >.There are three types of tags.Start-tag: <student>End-tag: </student>Empty-element tag: <quiz/>ElementsThe structure of XML documents comes primarily from elements.An element is one of the following:Everything from a start-tag to the matching end-tag.An empty-element tag.Elements have to be properly nested. The nesting can imply information.AttributesAn attribute is a name value pair.They can be put in start-tags or empty-element tags.Examples:<student name=”Jason” id=”0123456”><quiz grade=”55”/>XML DeclarationAn XML file can begin with a declaration telling information about it.<?xml version="1.0" encoding="UTF-8" ?>We won't worry about these in this class.Minute EssayWhat are examples when you use a computer to “search” in your
View Full Document
Unlocking...