### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ELEMENTS OF COMPUTER SCIENCE COMP 200

Rice University

GPA 3.72

### View Full Document

## 62

## 0

## Popular in Course

## Popular in ComputerScienence

This 12 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 200 at Rice University taught by Staff in Fall. Since its upload, it has received 62 views. For similar materials see /class/224963/comp-200-rice-university in ComputerScienence at Rice University.

## Similar to COMP 200 at Rice University

## Reviews for ELEMENTS OF COMPUTER SCIENCE

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15

x COMP 200 Elements of Computer Science 39 Fall 2004 39 I Lecture 13 September 24 2004 5 More Abstractions Trees amp Graphs On the Board Homework 3 Due Monday First Test Due Wednesday at 5PM DH 2065 Abstraction Last class we talked about the general issue of abstraction and about two specific data structures a stack and a queue Because stacks and queues inherently incorporate the notion of state the outcome of an operation on a stack or queue depends on the history of prior actions we had to use an assignment written 6 in our pidgin Algol or written set in Scheme in our implementation of the stack primitives push and pop In a similar way arrays and vectors recall Keys in our bubblesort algorithm from lecture 11 are inherently stateful We could design a funky constructor that built a new array from an old array and a single new element or a single new row but the result would be unnatural inelegant and for those reasons difficult to use Scheme s support for arrays is clumsy both notation and operation so we won t use Scheme when we talk about arrays However we can build interesting data structures from the combination of language features that led to lists the combination of de nestruct and recursion Trees As an example consider the problem of representing your ancestry Draw an example on the board including at least four generations of family Explain cousin relationships 1quot cousin 2 cousin once removed twiceremoved etc We call this a family tree Why is it a tree This tree encodes a single relationship MyParents The tree has roots the children and leaves the great grandparents Of course we can move the leaves back much farther in time with research but one can assume that we have a finite supply of humans Looking at more members of the family we can see that human families form multiple overlapping trees and that we understand the complexity inherent in such structures What is a cousin A second cousin We can also derive trees that encode the relationship MyChildren The two trees are related and the overall family trees are interwoven in a complex way Still we can see the relationship between them and navigate them As an abstract data structure a tree consists of a set of nodes where each node can have zero or more children In Scheme we might write a tree is a structure make node tree data children where data holds a name whatever that means and children is a list of trees define st ct tree data children a list of trees is a structure cons first rest where first is a tree and rest is a list of trees we will use Sche uiltin 39 If we want to write programs with these trees we need a template for the tree structure and a template for list of trees The templates are interwoven along the lines of the arrows Draw the templates Programs written along these lines take on the complexity of the templates If you apply the methodology and work through examples it really is as easy as working with the lists that we have seen Binary Trees To simplify the picture computer scientists often work with a restricted class of trees called binary trees A binary tree contains nodes that have at most two children historically designated as left and right children Limiting the definition to a small number of children avoids the need for a list in the definition which in turn simplifies the template and all the programs a binary tree node btn is either empty or a structure make node data left right where data is a name or whatever and left and right are binary tree nodes define struct node data left right This definition leads to a much simpler template than the arbitrary trees we saw earlier for ancestry template for btn define BTNProg fee cond empty fee else node data btn BTNProg node left btn BTNProg node right btn If data holds a number we can easily write a program that sums all the numbers in a tree work it out at the board The book goes into tree sort as a natural use for trees On the board COMP 200 Elements of Computer Science Fall 2004 Lecture 8 September 10 2004 Structures and Aggregates Continued On the Board Homework 2 due 9152004 Read Chapter 2 as of today you have the background No class on Monday Writing Programs with Structures When we start using structures the methodology for writing programs becomes more complex in two ways First we need to think actively about the kind of data that the program will encounter will need and how to represent that data This requirement adds a step before contract header and purpose called data analysis Second to remind ourselves of the possible selectors that we may need we also write a template for each structure a skeleton of a function that accesses that structure It includes all the selector functions that we may need in manipulating instances of that structure Now the methodology is as follows 1 Analyze the data and develop any structures that are needed39 for each structure write a function templatte J Write a contract purpose and header for the program 3 Develop a table of test data and expected answers Work out the expressions required for the body of the function HINT This problem requires a number line as did FirstClassMail 5 Code up the program 6 Test the program on your data from step 3 Applying the methodology to another program we can develop a program that calculates the distance between two points the length of a line drawn between them Step 1 Analyze the Data Input is two points We can use the definition of point given earlier in the lecture a point is a structure makepoint X y where X and y are numbers definestruct point X y Template for functions that deal with instances of point define ApointFunction ThePoint pointX ThePoint pointy ThePoint Step 2 Contract Purpose Header Template LineLength point point a number Purpose given two points compute the length of a line drawn between them define LineLength a b Step 3 TestData Inputs Results makepoint 0 0 makepoint 3 4 5 makepoint 0 0 makepoint 2 4 sqrt 20 makepoint l l makepoint l l 0 Step 4 Work out the code body Apply the Pythagorean Theorem Can compute the side lengths using subtraction and absolute value Can compute hypotenuse as square root of sum of squares of the side lengths 0 Use point selectors to get the relevant coordinates refer back to the template Something along the lines of abs pointx a pointx b yields the size of the X dimension Similar expression yields the size in the y dimension The expression should get a length in the X dimension a length in the y dimension square them sum them and take their square root abs pointx a pointx b abs pointx a pointx lb abs pointy a pointy b abS POIHty aP01ntY b Now we add those numbers and take their square root sq abs pointx a pointx b abs pointx a pointx b abs pointy apointy b D abs pointy ap0inty b Step 5 Code up the program 39 LineLength point point a number 39 Purpose given points that define the upper left and lower right 39 comers of a rectangle compute the rectangle s area define LineLength a b sqrt abs pointx a pointx b abs pointx a pointx b abs pointy a pointy b D abs pointy a pointy b Step 6 Test the program on the data from Step 3 Try it yourself in Dr Scheme or hand evaluate the expressions using the rewriting semantics Expect to have a hand evaluation on the first test The rewriting semantics for a selector function are simple replace the selector and its argument such as pointx ul with the value of that field in the structure Show the Stepper working on an example of LineLength gt type LineLength 3 4 in the de nitions pane of Dr Scheme gt Click your mouse on the Step button the one with the foot icon gt Repeatedly click on the gt Step button to move forward in the rewriting semantics or the lt Step to move backward Relating Class Back to the Book Chapter 2 begins to talk about programming language constructs and data structures It mentions sequencing executing one command after another conditional execution Scheme s cond and iteration Each of these has a place in Scheme Sequencing We have not seen a need for this in the programs we have written in class because they are stateless that is they always return the same answer when given the same inputs Some programs think of Google or the registrar s database retain internal state that causes them to produce different results when invoked on the same inputs at different points in time In Scheme we can use a begin expression to sequence multiple Scheme expressions In Dr Scheme it is in the advanced language Given the amount of Scheme we have learned you have no application for it yet However in your sorting algorithms Homework 1 you used sequencing as a natural part of expressing your algorithms Some of you went so far as to introduce variables state and modify it as your algorithm executed assignment to that state Conditional Execution We have seen one Scheme construct for conditional execution the cond expression Scheme also offers an if construct that looks like the ifthenelse in the book if we believe that syntax is only skin deep Scheme s if is written if gt a b c d where gt a b is a conditional expression that evaluates to true or false If the expression evaluates to true the result is c otherwise it is d if gt a b c d is equivalent to cond gt a b C else d Of course d can be an if creating opportunities to nest conditionals In the cond expression the result of one condclause can be a cond creating the opportunity for similarly complex and difficult to read code Any nested cond can be converted to a singlelevel cond by combining the conditions Iteration Iteration is one of the fundamental paradigms of computation So far we have not seen it In Scheme most iteration is performed Via recursion a mathematical formulation that uses a selfreferential formula A classic example is the factorial function Factn is The book tries to introduce recursion using a classic game called the Towers of Hanoi If that example confuses you ignore it We will develop recursion next week and reach the point where it makes sense 1 if n l n Factn l otherwise The mechanism is unfamiliar which may make you nervous The intuitions are pretty straightforward and reach back to concepts that you encountered in High School Algebra g R COMP 200 Elements of Computer Science Fall 2004 Lecture 21 October 18 2004 E More on Algorithmic Complexity On the Board Homework 4 I need to write the solution key Next homework ready Friday Will talk about the final project next class Back to Complexity amp BigO Notation Last class we talked about the efficiency of algorithms and introduced the big O notation pronounced big Oh In essence big O notation tells us how the time required by an algorithm grows as a function of the size of its input In particular we are interested in the asymptotic behavior as N grows toward infinity what function of N describes the algorithm s running t1me Remember if the running time of an algorithm is bounded from above by c fN then we say that the algorithm is OfN where N is a measure of the size of the input Further we expect that fN is the smallest function for which we can prove the bound running time lt c fN Consider for example our simple program for finding the maximum value in a list max 6 list1 fori e 2 to n if max lt listi then max 6 listi If the list has n elements the loop iterates n I times Each operation in the loop s body is simple that is each operation should take constant or 01 time It has one operation outside the loop a simple 01 operation as well Thus the running time should be 01 On I 1 which simplifies to 0n time Remember big O notation is intended to provide an upper bound and On I is effectively 0n as It grows large If we replace one of the operations in the inner loop with a more expensive operation such as a mergesort a 0n2 operation then the complexity will become On 0n2 0n3 Notice that our notion of complexity depends quite heavily on the set of operations that we allow as elementary operations in our model of computation So far in COMP 200 we have used simple arithmetic comparisons and evaluating conditionals as 01 operations along with whatever overhead a loop requires to perform its repetitions amp its book keeping This issue gets a little subtle max of two or three or any small number of arguments can be done in 01 time but max of an arbitrary list of numbers takes Olenglh oflisl time Some simple operations take longer than is reasonable to count as 01 For example computing n using the na39139ve algorithm takes 0m time n It It n multiply n by itselfm consecutive times Logarithms sin cosine tangent and many other functions are actually computed using series approximations It might be unfair to count these as 01 operations In general when designing software we want to use the lowest complexity algorithm possible Lower complexity means faster running times as the size of the input grows Of course if we know how big the input will be we can make comparisons based not only on the asymptotic complexity but also on the size of the constants In general an algorithm with a smaller constant will run faster Algorithms with low order polynomial complexity are considered practical for most problems The algorithm to paint a menu in Windows or Mac OS X takes time that is 0number ofmenu entries It is linear in the number of menu entries Each entry is a fixed height and a bounded width so the number of pixels is roughly a constant for each menu entry Many problems that are routinely solved have 0n2 or 0n3 complexity for example matrix matrix multiply has 0n3 cost Sometimes linear cost is too much When you boot your computer it usually checks the integrity of the file system On your machine this might take as long as a minute or two Unless major problems are found the process makes a couple of linear passes over the file systems structure It only examines the structure it does not look inside every byte on the disk It must however make sure that every sector on the disk belongs to some file or in the pool of unallocated sectors Thus the file system check has a complexity that is proportional to the number of sectors in the file system A sector is typically 1024 or 4096 bytes so the number of sectors is the proportional to the number of bytes of space in the file system Recently we bought a file server with two and one half terabytes of disk space Running fsck the Linux or Mac OS X le system che er on two and one half terabytes takes a couple of hours Thus rebooting the system would take hours Any computer crash would make the system unavailable for hours not a good property for a server Imagine CNNcom or the OwlNet file server going down for three hours to check its disks The answer of course is to use another method to maintain the file system s integrity In this case the system is journalled it records each write to the disk and marks them off the list when they are known to be completed After a crash the system can simply replay the writes in order that have not been certified as complete Replaying the journal takes time proportional to the length of thejoumal As long as the time required for writing the file system has a small upper bound say a minute the joumaling process takes much less time than checking the entire file system The cost of checking is paid on each write rather than on each crash The cost of checking becomes proportional to the amount of disk write activity rather than being proportional to the size of the file system Over a long period of time you might pay more for the journaling However at any point in time the amount of time required to replay the journal is small

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.