New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

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

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Ransom Blanda


Ransom Blanda
GPA 3.63

Charles Stewart

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Charles Stewart
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 55 page Class Notes was uploaded by Ransom Blanda on Monday October 19, 2015. The Class Notes belongs to CSCI 1200 at Rensselaer Polytechnic Institute taught by Charles Stewart in Fall. Since its upload, it has received 12 views. For similar materials see /class/224847/csci-1200-rensselaer-polytechnic-institute in ComputerScienence at Rensselaer Polytechnic Institute.

Similar to CSCI 1200 at RPI

Popular in ComputerScienence




Report this Material


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
Data Structures Lecture 1 Introduction and Reveiw 1 Discussion of Syllabus o Instructor TAs office hours 0 The course web site httpwwwcsrpieduCoursesspringllds is up and running 0 Material textbooks lecture notes and examples posted on the web 0 Learning outcomes Students who have successfully completed this course will be able to 7 Demonstrate strong problem solving skills in constructing C programs to address exercises inspired by real world problems 7 Analyze the performance of algorithms and data structures 7 Select and use the most appropriate data structure from the C standard library STL for a particular programming task 7 Design and implement e icient customized data structures 0 Prerequisites o Lectures and lecture notes 0 C vs Java 0 Requirements 7 Labs 13 Note Lab 1 is posted You are very strongly urged to start before your actual lab on Wednesday 7 Homeworks 37 7 Four tests 50 Important note Test 2 is Thursday March 10 at 12 noon This is the last Thursday before Spring Break 0 Late policy 0 Schedule of material 0 Academic integrity 2 Overview of Lectures 1 2 and 3 0 Review of CSci I level material7 focus on C constructs and small scale problem solving 0 Background on additional concepts that we will use during the semester 0 Built around examples Source code is posted on line Extra practice problems and solutions are also posted 0 Students who nd this material challenging need to work hard to catch up Practice is the key 3 Background Reading Much of what is covered here is basic background for C programming and is covered in virtually any introductory text The material on the order notation at the end the lecture is covered in FordampTopp7 pages 128 139 4 Example 1 Hello World Here is the standard introductory program a small C program include ltiostreamgt int main stdcout ltlt quotHello worldquot ltlt stdendl return 0 Small though it is7 it may be used to illustrate a number of important points7 as we now discuss 41 Basic Syntax 0 Comments are indicated using for single line comments and and for multi line comments 0 include asks the compiler for parts of the standard library that we wish to use eg the inputoutput stream function std cout int main is a necessary component of all C programs it returns a value integer in this case and it could have parameters Lecture 2 o the curly braces indicate to C to treat everything between them as a unit 42 The Standard Library 0 The standard library is not a part of the core C language Instead it contains types and functions that are important extensions 7 In our programming we will use the standard library to such a great extent that it will feel like part of the C core language 0 streams are the rst component of the standard library that we see 0 std is a namespace that contains the standard library 0 std cout and std endl are de ned in the standard library in particular in the standard library header le iostream 43 Expressions 0 Each expression has a value and 0 or more side effects 0 An expression followed by a s l n is a L L L The s l n tells the computer to throw away the value of the expression 0 The line stdcout ltlt quotHello worldquot ltlt stdendl is really two expressions and one statement 7 The rst expression is std cout ltlt quotHello worldquot 7 The value of this expression is std cout and the side effect is that Hello world is output 7 Using the value of the rst expresssion the second expression is just std cout ltlt std endl 7 Perhaps this can be better understood by writing the original statement equivalently as stdcout ltlt quotHello worldquot ltlt stdendl 0 quotHello worldquot is a string literal 44 Aside C vs Java The following is provided as additional material for students who have learned Java and are now learning C 0 In Java everything is an object and everything inherits from java lang0bject In C functions can exist outside of classes In particular the main function is never part of a class 0 Source code le organization in C does not need to be related to class organization as it does in Java On the other hand7 creating one C class when we get to classes per le is the preferred organization7 with the main function in a separate le on its own or with a few helper function 0 Compare the hello world77 example above in C to the same example in Java public class HelloWorld public static void mainString args U System out printlnquotHello Worldquot The Java object member function declaration public static void mainString args U Plays the same role as int main in the C program A primary difference is that there are no string arguments to the C main function Very soon next week we will start adding these arguments7 although in a somewhat different syntactic form The statement System out println quotHello Worldquot is analogous to stdcout ltlt quotHello worldquot ltlt stdendl The std endl is required to end the line of output and move the output to a new line7 whereas the Java println does this as part of its job 5 Example 2 Temperature Conversion Our second introductory example converts a Fahrenheit temperature to a Celsius temperature and decides if the temperature is above the boiling point or below the freezing point inc lude ltiostreamgt using namespace std Eliminates the need for stdzz int main Request and input a temperature cout ltlt quotPlease enter a Fahrenheit temperature quot float fahrenheittemp cin gtgt fahrenheittemp Convert it to Celsius and output it float celsiustemp fahrenheittemp 32 50 90 cout ltlt quotThe equivalent Celsuis temperature is quot ltlt celsiustemp ltlt quot degreesnquot Output a message if the temperature is above boiling or below freezing const int BoilingPointC 100 const int FreezingPointC 0 if celsiustemp gt BoilingPointC cout ltlt quotThat is above the boiling point of waternquot else if celsiustemp lt FreezingPointC cout ltlt quotThat is below the freezing point of waternquot return 0 U 1 Variables and Constants o A variable is an object with a name a C identi er such as fahrenheitltemp or celsiusltemp 0 An object is computer memory that has a type c A type is a structure to memory and a set of operations 0 Too abstract Think about float variables 7 Each variable has its own 4 bytes of memory and this memory is formatted according oating point standards for What represents the exponent and mantissa 7 Many operations are de ned on oats including addition subtraction etc 7 A oat is an object o A constant 7 such as BoilingPointC and FreezingPointC 7 is an object with a name7 but a constant object may not be changed once it is de ned and initialized Any operations on integer types may be applied to a constant int7 except operations that change the value 0 Note that the use of capitals and in the identi er is merely a matter of style 52 Expressions Assignments and Statements Consider the statement float celsiustemp fahrenheittemp 32 50 90 o The calculation on the right hand side of the is an expression 7 You should review the de nition of C arithmetic expressions and operator precedence The rules are pretty much the same in C and in Java 0 The value of this expression is assigned 7 stored in the memory location 7 of the newly created oat variable celsiusitemp 53 Conditionals and IF statements lntuitively7 the meaning of the code if celsiustemp gt BoilingPointC cout ltlt quotThat is above the boiling point of waternquot else if celsiustemp lt FreezingPointC cout ltlt quotThat is below the freezing point of waternquot should be pretty clear 0 The general form of an if else statement is if conditionalexpression statement else statement 0 Each statement may be a single statement7 such as the cout statement above7 a structured statement7 or a compound statement delimited by 7 The second if is actually a structured statement that is part of the else of the rst if 0 Students should review the rules of logical expressions and conditionals 0 These rules and the meaning of the if else structure are essentially the same in Java and in 6 Example 3 Julian Day include ltiostreamgt using namespace std const int DaysInMonth13 0 31 28 31 30 31 30 31 31 30 31 30 31 The following function returns true if the given year is and returns false otherwise bool isleapyear int year a leap year return year Z 4 0 ampamp year Z 100 0 II year Z 400 0 Calculate and return the Julian day associated with the given month and day of the year int julianday int month int day int year int jday O for unsigned int m1 mltmonth m jday DaysInMontth if m 2 ampamp isleapyearyear jday February 29th jday day return jday int main cout ltlt quotPlease enter three integers a month a day and a year quot39 int month day year cin gtgt month gtgt day gtgt year cout ltlt quotThat is Julian day quot ltlt julianday month day year ltlt endl return 0 61 Arrays and Constant Arrays 0 An array is a xed7 consecutive sequence of objects all of the same type 62 The following declares an array of 15 double values double a15 The values are accessed through subscripting operations int i 5 ai 314159 This assigns the value 314159 to location i5 of the array Here i is the subscript or index C array indexing starts at O Arrays are xed size and each array knows NOTHING about its own size The programmer must write code that keeps track of the size of each array 7 During Lecture 2 we will discuss a standard library generalization of arrays called vectors which are full edged objects and do not have any of these restrictions 1n the statement const int DaysInMonth13 0 31 28 31 30 31 30 31 31 30 31 30 31 7 DaysInMonth is an array of 13 constant integers 7 The list of values within the braces initializes the 13 values ofthe array so that DaysInMonth 0 0 DaysInMonth1 31 etc 7 The array is global meaning that it is accessible in all functions within the code after the line in which the array is declared Global constants such as this array are usually ne whereas global variables are generally a VERY bad idea Functions and Arguments Functions are used to 7 Break code up into modules for ease of programming and testing and for ease of reading by other people never ever under estimate the importance of thisl 7 Create code that is reusable at several places in one program and by several programs Each function has a sequence of parameters and a return type For example int julianday int month int day int year has a return type of int and three parameters each of type int The order of the parameters in the calling function the main function in this example must match the order of the parameters in the function prototype 63 for loops 0 The basic form of a for loop is for exprl expr2 expr3 statement where 7 exprl is the initial expression executed at the start before the loop iterations begin 7 expr2 is the test applied before the beginning of each loop iteration the loop ends when this expression evaluates to false or O 7 expr3 is evaluated at the very end of each iteration 7 statement is the loop body77 0 The for loop from the julianday function for unsigned int m1 mltmonth m jday DaysInMonthm if m 2 ampamp isleapyearyear jday February 29th adds the days in the months 1month 1 and adds an extra day for Februarys that are in leap years c for loops are essentially the same in Java and in C 64 A More Di icult Logic Example Consider the single statement in the function isleapyear return year 70 4 0 ampamp year 70 100 0 II year 70 400 0 This is important to understand 0 If the year is not divisible by 4 the function immediately returns false without evaluating the right side of the Mr 0 For a year that is divisible by 4 if the year is not divisible by 100 or is divisible by 400 and is obviously divisible by 100 as well the function returns true 0 Otherwise the function returns false 0 The function will not work properly if the parentheses are removed in large part because ampamp has higher precedence than I 7 Example 4 Julian Date to MonthDay o The source code is attached to these notes We ll examine some of the structure and then focus on the monthiandiday function 0 The main function is the rst function in the le as opposed to the last This is a stylistic choice 0 Function prototypes are inserted above the main function in the le 0 The name of the month is output using the function outputJnonthJiame7 which is just a big switch statement 7 Note the use of the break statement at the end of each case 7 See Chapter 4 of Malik for detailed discussion of switch 71 Month And Day Function Compute the month and day corresponding to the Julian day within the given year void monthandday int julianday int year int amp month int amp day bool monthfound false month 1 Loop through the months subtracting the days in this month from the Julian day until the month is found where the number of remaining days is less than or equal to the total days in the month while monthfound Calculate the days in this month by looking it up in the array Add one if it is a leap year int daysthismonth DaysInMonthImonth if month 2 ampamp isleapyearyear daysthismonth if julianday lt daysthismonth monthfound true Done else julianday daysthismonth month day julianday We will assume you know the basic structure of a while loop and focus on the underlying logic 0 A bool variable which can take on only the values true and false called monthiound is used as a ag to indicate when the loop should end The rst part of the loop body calculates the number of days in the current month starting at one for January including a special addition of 1 to the number of days for a February month in a leap year The second half decides if we ve found the right month If not the number of days in the current month is subtracted from the remaining Julian days and the month is incremented Understanding the logic of functions such as this one is important for developing your programming skills 72 Value Parameters and Reference Parameters Consider the line in the main function that calls monthandday monthandday julian year month dayinmonth and consider the function prototype void monthandday int julianday int year int amp month int amp day Note in particular the amp in front of the third and fourth parameters 0 The rst two parameters are value parameters 7 These are essentially local variables in the function whose initial values are copies of the values of the corresponding argument in the function call 7 Thus the value of julian from the main function is used to initialize julianday in function monthandday 7 Changes to value parameters do NOT change the corresponding argument in the calling function main in this example 0 The second two parameters are reference parameters as indicated by the amp 7 Reference parameters are just aliases for their corresponding arguments No new variable are created 7 As a result changes to reference parameters are changes to the corresponding variables arguments in the calling function 0 Rules of thumb77 for using value and reference parameters 7 When a function eg isleapyear needs to provide just one result make that result the return value of the function and pass other parameters by value 7 When a function needs to provide more than one result eg monthandday these results should be returned using multiple reference parameters We will see minor variations on these rules as we proceed this semester 11 73 Arrays as Function Arguments Consider the following function void doit double a int n for int i0 iltn i if ai lt O ai 1 o What does it do 0 The important point about this function is that the changes made to array a are permanent7 even though a is a value parameter 0 Reason What7s passed by value is the memory location of the start of the array The entries in the array are not copied7 and therefore changes to these entries are permanent o The number of locations in the array to work on 7 the value parameter n 7 must be passed as well because arrays have no idea about their own size 74 Exercises Here are some practice problems Solutions will be posted on the course web site7 and we will review them in class if we have time 1 What would be the output of the above program if the main program call to monthandday was changed to monthandday julian year dayinmonth month and the user provided input that resulted in julian 50 and year 2007 What would be the additional output if we added the statement cout ltlt month ltlt endl immediately after the function call in the main function 2 What is the output of the following code void swap double x double ampy double temp x x y y temp int main double a 150 b20039 cout ltlt quot21 quot ltlt 21 ltlt quot b quot ltlt b ltlt endl swap a b cout ltlt quot21 quot ltlt 21 ltlt quot b quot ltlt b ltlt endl return 0 8 Scope The following code will not compile We want to understand why not7 x the code minimally so that it will7 and then determine what will be output int main inta5b10 intx 15 double a 15 b 1 int x 20 int y 25 cout ltlt quot21 quot ltlt 21 ltlt quot b quot ltlt b ltlt n ltlt quotx quot ltlt x ltlt quot y quot ltlt y ltlt endl cout ltlt quot21 quot ltlt 21 ltlt quot b quot ltlt b ltlt n ltlt quotx quot ltlt x ltlt quot y quot ltlt y ltlt endl return 0 o The scope of a name identi er is the part of the program in which it has meaning 0 Curly braces7 7 establish a new scope 7 this includes functions and compound statements 7 This means scopes may be nested 7 ldenti ers may be re used as long as they are in different scopes o Identi ers variables or constants within a scope hide identi ers within an outer scope having the same name This does not change the values of hidden variables or constants 7 they are just not accessible 0 When a is reached7 a scope ends All variables and constants and other identi ers declared in the scope are eliminated7 and identi ers from an outer scope that were hidden become accessible again in code that follows the end of the scope o The operator establishes a scope as well For example7 std cout refers to the identi er cout within the scope of namespace std 9 Summary Course overview Four review examples Basic structure of C code and the C main function iostreams and the standard library Java vs C Variables constants operators expressions and statements if else arrays functions for loops logic switch statements and while loops Value parameters and reference parameters Arrays as function parameters Scope All of this material should be review of your C knowledge or should be easily transferred from your experience with other programming languages Data Structures i Spring 2011 Lab 2 i Word Search Overview We re all familiar with the Word Search game For example can you nd any ofthe words cartoon frozen blizzard or bounce in the following h f f an ar en cl ad ro to of of DDIIZXDVIWGG e uy r ner h ens d hbl h pfo f epr e pea e roz i eta a rue d39OQHHaGmHmSLt I aa ad tr t iz a av z ud f In k en r yc e tr r d d f a z c l l c r nd y All but blizzard right In this lab we will implement a program to solve the word search game Start by creating a folder to hold your Lab 2 work and then download the zip le http www cs rpi eduacademicscoursesspringl1ds1abs1ab02wsdata zip This has example grids as well as search words The command line for the program you will write is ws gridtxt wordstxt where o gridtxt is the le containing the grid similar to the example above but with the spaces removed 0 wordstxt contains the words to search in the grid All output should go to std cout Checkpoint I 7 File Input and Checking Write the main function to open and check the les to read the grid into a vector of strings to check that the strings are all the same length and to count and output the number of occurrences of the letter a in the grid This counting step is a throw away77 exercise to make sure you understand how to access information in the grid While this sounds like a lot most of it can be found in other code we ve already provided particularly at the end of Lecture 2 You are welcome to cut and paste code and then modify it to suit your needs To complete Checkpoint 1 please demonstrate your code in three ways 0 One of the command line les is not found 0 One of the grids has uneven length strings Your program should stop if the lengths are uneven 0 Counting letter a Checkpoint 2 7 Testing for Words Write two functions wordjicross and worddown The rst should check to see if a word a string occurs left to right in the grid starting from a particular grid location row and column The second should check to see if a word a string occurs top to bottom in the grid starting from a particular grid location row and column Each function should have four arguments o the grid to search 0 the word to nd 0 the row in the grid to test 0 the column in the grid to test What type of parameters should each of these be The function should return true if the word is found and false otherwise As an example calling wordjicross with the grid shown abouve with the string frozen and with row 7 and column 3 should return true calling it with any other starting row or column should return false To complete checkpoint 2 Demonstrate your code on both successful and unsuccessful searches Testing calls to wordjicross and worddown should be coded into the main function Data Structures i Spring 2011 Lab 1 i Getting Started Organization and Rules Three points are associated with each lab These are checkpoints for completion of work When you have completed each checkpoint raise your hand and one of the TAs will quickly check your work We have few signi cant organizational issues and rules for all labs 0 Note that this is a change from the handout posted online You may use the network to search for help in addressing C questions and data structure issues Do not hesitate to type questions into a Google or Bing search engine On the other hand use of the network for non class activities will be frowned upon and may lead you to get much less help than you might expect if you are working diligently Get to know the other students in the lab Introduce yourself to your neighbors You may ask your fellow students questions about the lab This will help reduce the burden on the TAs and will reduce your waiting time in lab Even though students may give and receive help each student must produce hisher own solution Part of earning a checkpoint for a lab may involve answering a short question that the TA asks you If you have done the checkpoint and understood it you should have no trouble earning this credit If you have relied on help from other students too much you may nd the question hard to answer Getting Started The rst checkpoint involves getting started with the C development environment that you plan to use for all the labs and homeworks in this class You may use whatever operating system compiler editor and general environment that you choose for code development in lab and for the homeworks However for the homework assignments we ask you to submit code that compiles with gceg 42x By doing so you will help us streamline the grading process This will allow the TAs to spend more time giving you constructive feedback on programming style individual tutoring and debugging help Let s get started 0 Create a directory aka folder on your laptop to hold Data Structures course les Create a sub directory to hold labs And nally create a sub directory named labl Please make sure to save your work frequently and periodically back up all of your data 0 Using a web browser copy the following le to your labOl directory httpwwwcsrpieduacademicscoursesspringl1ds1abs1ab01introjuliancpp Compiling Using g on Linux FreeBSD or WindowsCygwin Even if you intend to use Visual Studio to write your programs you should learn to compile them using the g compiler This will prevent problems when submitting your programs H Open a shellterminalcommand prompt window If you have never used cygwin before you should be able to nd it in your list of programs Within the cygwin directory you want the bash shell If you are on a Windows machine and if you can not nd cygwin please contact a lab TA immediately to Change directories into your new labl directory Use the command Cd 6 to get to the top level of your C drive Use ls to list the contents of the directories Then you can use Cd to move down in these directories In doing so remember that directory names are separated by 77 and when you have a space in the name ofthe directory then bash requires that you precede the blank with a Thus on my Windows machine I type Cd Documents and SettingsStewartdslabo1 in order to get to the directory containing my code 3 Now you are ready to attempt to compilebuild the program for this lab or other simple one le projects by typing g juliancpp o julianexe F If you will be using g on a regular basis for later labs and assignments you may eventually want to learn to use a Make le U Note To check which version of gcc is installed on your machine type g V If you are not using g 42x you may notice slight differences between your compiler and the version on the homework submission server when we get to advanced topics When Using the Microsoft Visual C Development Environment The following instructions show you how to get started using the Visual Studio development envi ronment 1 Start up Developer Studio Spend some time exploring the user interface especially the online help Help can be easily accessed through the HelpSearch menu Also notice that if you leave the mouse over an icon for a second or two a tool tip77 will pop up telling you what the icon does Work within Developer Studio is organized around projects and solutions Projects are col lections of les used to create an executable program a solution is a collection of one or more projects Browse the online help on solutions and projects 2 Create a workspace Use the File gtNew gtProject menu and click the Visual C Projects folder There are multiple kinds of projects but you only need to worry about the one named Win32 Project Make this choice select the folder you created for your Data Structures labs as the Location and then give your project a name such as Lab 1 as you type Visual Studio will con rm what the actual path of your project will be on your computer which will make nding the executable program much easier Click OK You will then see a very short wizard dialog that makes sure the project that is being created ts all of your needs 7 click on Applications Settings and change the program from a Windows Application to a Console Application using the row of check boxes You should also check the Empty Project option to make sure that you are starting from a completely clean slate Click OK 3 Add your le to the project Use the Project gtAdd Existing Item menu and browse to the location where you made your local copies of the lab le julian Cpp Select the le that you want to add note you can select multiple les by holding down the Ctrl key while clicking and click OK Then go to the Solution Explorer window if it does not appear on the screen you can open it from View menu of the workspace click the next to your project s Source Files folder and you should see the le listed F Attempt to build the project Go to the Build menu and select Build Lab 1 This is the Developer Studio term for compiling and linking Checkpoint I The process of compiling a program translates the high level C code into machinelevel object code The compiler itself is a complicated program and is the most important part of any program ming environment The linking step gathers the object code from your program together with other code libraries that your program needs which has already been compiled pre compiled and stored elsewhere For your program this is just the standard library which includes code for i o streams and strings Once the linking step is complete you have an executable program We have introduced a number of errors into this program so that it will not compile correctly to produce an executable program If you are using g the compile and link errors will be displayed in the terminalshellcommand prompt Within Visual Studio these errors are directed to the status pane along the bottom of your screen If you double click on an error the status pane will scroll to the error and the position of the cursor in the editing pane will move to the le and line number where the error occurred Submit the buggy version of the lab code to the homework server Go to the course webpage http www cs rpi eduacademicscoursesspringllds then click on the Homework link and follow the instructions under the Electronic Submission section substitute labl for hwl After submitting the buggy code you should receive con rmation of your submission and be noti ed of the compile time errors in the program To complete Checkpoint 1 Show one of the TAs both 1 the compiler errors that you obtained in your chosen development environment on your ma chine and 2 the response from the homework submission server Checkpoint 2 The compiler errors we have introduced are pretty simple to x Please do so and then compile the program Once you have removed all of the errors you are ready to execute the program If you are using g you can run the program by typing julian exe Within Visual Studio you can do this by clicking on the Debug menu and selecting the X This will produce a new pane on which you will have to type the input to the program option Resubmit the xed version of the lab code to the homework server Assuming your xes are cross platform compatible the re submission should successfully compile and run without error Save this submission result you will need to show it to a TA as part of completing this checkpoint not now though there is more below You will not need the network for the remainder of this lab Please disable your internet connection now For the rest of this lab we are going to review more about arrays and the logic of manipulating them We will also practice a bit with functions and with input and output Modify the main program so that it de nes two arrays that hold 10 integer values each One of these arrays should store months and the other should store days Assume the year is 2011 Write a for loop that reads 10 month day combinations into these two arrays Create a third array that holds Julian days Now write another for loop that computes the Julian day from the month day combinations and stores it in the array Finally write a for loop that outputs the Julian days To complete Checkpoint 2 show a TA your debugged extended and tested program and the results of submitting your debugged code for the single date problem to the homework server Checkpoint 3 Note that solving the Checkpoint 2 problem did not actually require arrays You were asked to solve the problem in this manner just to give you some practice Checkpoint 3 however will require the use of arrays and will give you practice with functions Checkpoint 3 will also require using the function fabs which returns the absolute value of the expression it is passed The prototype for this function is in header le cmath Thus for the problem in Checkpoint 3 the complete set of headers is include ltiostreamgt include ltcmathgt using namespace std If you did not have the using namespace std statement you would have to refer to fabs as std fabs Here is an example snippet of code using fabs float x 35 y 74 float diff fabsxy cout ltlt diff ltlt n Data Structures 7 Lecture 3 Order Notation and Recursion 1 Overview 0 The mediangrade Cpp program from Lecture 2 and background on constructing and using vectors 0 Algorithm analysis order notation o Recursion The material on the order notation at the end the lecture is covered in FordampTopp pages 128139 2 Algorithm Analysis What Why How 0 What 7 Analyze code to determine the time required7 usually as function of the size of the data being worked on 0 Why 7 We want to do better than just implementing and testing every idea we have 7 We want to know why one algorithm is better than another 7 We want to know the best we can do This is often quite hard 0 How There are several possibilities 1 Don t do any analysis just use the rst algorithm you can think of that works Implement and time algorithms to choose the best 03w Analyze algorithms by counting operations While assigning different weights to different types of operations based on how long each takes F Analyze algorithms by assuming each operation requires the same amount of time Count the total number of operations7 and then multiply this count by the average cost of an operation 0 What happens in practice 7 99 of the time rough count similar to 4 as a function of the size of the data Use order notation to simplify the resulting function and even to simplify the analysis that leads to the function 7 1 of the time implement and time What follows is a quick review of counting and the order notation 21 Exercise Counting Example Suppose foo is an array of 11 doubles initialized with a sequence of values 0 Here is a simple algorithm to nd the sum of the values in the vector double sum O for int i0 iltn i sum foo i o How do you count the total number of operations 0 Go ahead and try Come up with a function describing the number of operations 0 You are likely to come up with different answers How do we resolve these differences 22 Order Notation The following discussion emphasizes intuition That s all we care about in Data Struc tures For more details and more technical depth see any textbook on data structures and algorithms 0 De nition Algorithm A is order fn 7 denoted Ofn 7 if constants k and no exist such that A requires no more than k x f n time units operations to solve a problem of size n 2 no As a result algorithms requiring 3n 2 5n 7 3 14 1771 operations are all On ie in applying the de nition of order notation fn Algorithms requiring 71210 1571 7 3 and 10000 35712 are all 0n2 ie in applying the de nition of order notation fn n2 Intuitively and importantly we determine the order by nding the asymptotically dominant term function of n and throwing out the leading constant This term could involve logarithmic or exponential functions of n Implications for analysis 7 We do not need to quibble about small differences in the numbers of operations 7 We also do not need to worry about the different costs of different types of operations 7 We do not produce an actual time We just obtain a rough count of the number of operations This count is used for comparison purposes In practice this makes analysis relatively simple quick and sometimes unfortunately rough 23 Common Orders of Magnitude Here are the most commonly occurring orders of magnitude in algorithm analysis 0 01 Constant time The number of operations is independent of the size of the problem 0 Olog n Logarithmic time 24 Signi cance of Orders of Magnitude o On a computer that performs 108 operations per second 7 An algorithm that actually requires 157i log n operations requires about 3 seconds on a problem of size n 1 000 000 and 50 minutes on a problem of size n 100 000 000 7 An algorithm that actually requires n2 operations requires about 3 hours on a problem of size n 1000000 and 115 days on a problem of size n 100 000 000 0 Thus the leading constant of 15 on the n logn does not make a substantial difference What matters is the n2 vs the nlogn 0 Moreover in practice the leading constants usually do not vary by a factor of 15 25 Back to Analysis A Slightly Harder Example 0 Here s an algorithm to determine if the value stored in variable x is also in an array called foo int loc0 bool found false while found ampamp loc lt n if x fooloc found true else loc if found cout ltlt quotIt is therenquot 0 Can you analyze it What did you do about the if statement What did you assume about where the value stored in x occurs in the array if at all 26 BestCase AverageCase and WorstCase Analysis 0 For a given xed size vector7 we might want to know 7 The fewest number of operations best case that might occur 7 The average number of operations average case that will occur 7 The maximum number of operations worst case that can occur 0 The last is the most common The rst is rarely used 0 On the previous algorithm7 the best case is 017 but the average case and worst case are both 27 Approaching An Analysis Problem 0 Decide the important variable or variables that determine the size of the problem 7 For arrays and other container classes77 this will generally be the number of values stored 0 Decide what to count The order notation helps us here 7 If each loop iteration does a xed or bounded amount of work7 then we only need to count the number of loop iterations 7 We might also count speci c operations7 such as comparisons 0 Do the count7 using order notation to describe the result 28 Examples Loops In each case give an order notation estimate as a function of n which here notes the 0 Version A int count0 for int i0 iltn i for int j0 jltn j count 0 Version B int count0 for int i0 iltn i count for int j0 jltn j count 0 Version C int count0 for int i0 iltn i for int ji jltn j count o How many operations in each 29 More 0 Examples Solutions to these will be posted on line 1 Write a C function to remove the rst item in an array of 71 oat values Give an 0 analysis of this function 2 Can you analyze binary search Assume that the search interval is of size n 2k for some positive integer k 3 Recursion The Basics 31 Recursive De nitions of Factorials and Integer Exponentiation o The factorial is de ned for non negative integers as V nlnil ngt0 71 1 n 0 Computing integer powers is de ned as 71177 71411771 pgt0 1 p0 0 These are both examples of recursive de nitions 32 Recursive C Functions 07 like other modern programming languages7 allows functions to call themselves This gives a direct method of implementing recursive functions 0 Here s the implementation of factorial int fact int n if n 0 return 1 else int result fact nl return n result 0 Here s the implementation of exponentiation int intpow int 11 int p ifp0 return 1 else return n intpow n pl 33 The Mechanism of Recursive Function Calls 0 When it makes a recursive call or any function call7 a program creates an activation record to keep track of 7 Each newly called function s own completely separate instances of parame ters and local variables 7 The location in the calling function code to return to when the newly called function is complete 7 Which activation record to return to when the function is done 0 This is illustrated in the following diagram of the call fact4 Each box is an activation record7 the solid lines indicate the function calls7 and the dashed lines indicate the returns fact4 n4 result fact3 retum 46 fact3 m n3 result fact2 fact2 n72 result fact1 fact1 n1 result fact0 34 Iteration vs Recursion 0 Each of the above functions could also have been written using a for loop ie item tiuely o For example here is an iterative version of factorial int ifact int n int result 1 for int i1 iltn i result result i return result o Iterative functions are generally faster than their corresponding recursive functions Compiler optimizations sometimes but not always can take care of this by auto matically eliminating the recursion 0 Sometimes writing recursive functions is more natural than writing iterative functions however Most of our examples will be of this sort 35 Exercise Write an iterative version of intpow 36 Rules for Writing Recursive Functions Here is an outline of ve steps I nd useful in writing and debugging recursive functions 1 Handle the base cases rst at the start of the function 2 De ne the problem solution in terms of smaller instances of the problem This de nes the necessary recursive calls It is also the hardest part 3 Figure out what work needs to be done before making the recursive calls 4 Figure out what work needs to be done after the recursive call s completes to nish the computation 5 Assume the recursive calls work correctly but make sure they are progressing toward the base casesl 37 Example Printing the Contents of a Vector The following example is important for thinking about the mechanisms of recursion 0 Here is a function for printing the contents of a vector Actually it is two functions driver function and a true recursive function void printvec vectorltintgtamp v printvec v 0 void printvec vectorltintgtamp v unsigned int i if i lt vsize cout ltlt i ltlt quot quot ltlt vi ltlt endl printvec v i1 0 Exercise What will this print when called in the following code int main vectorltintgt a apushback 3 apushback 5 apushback 11 apushback 17 printvec a Note the idea of a driver function77 that just initializes a recursive function call is quite common 0 Exercise How can you change the second printivec function as little as possible to write a recursive function to print the contents of the vector in reverse order 3 OD Binary Search 0 Suppose you have a vectorltTgt v7 sorted so that vO lt vl lt v2 lt 0 Now suppose that you want to nd if a particular value x is in the vector somewhere o How can you do this without looking at every value in the vector The solution is a recursive algorithm called binary search7 based on the idea of checking the middle item of the search interval within the vector and then looking either in the lower half or the upper half of the vector7 depending on the result of the comparison Here is the recursive function The quotinvariantquot is that if x is in the vector then it must be located within the subscript range low to high Therefore when low and high are equal their common value is the only possible place for x Otherwise the middle value is checked and the search continues recursively in either the lower or upper half of the vector bool binsearch const vectorltdoublegtamp v int low int high double x if high low return x vlow int mid lowhigh 2 if x lt vmidl return binsearch v low mid x else return binsearch v mid1 high x The driver function It establishes the search range for the value of x based on the minimum and maximum subscripts in the vector bool binsearch const vectorltdoublegtamp v double x i return binsearch v 0 vsize1 x 39 Exercises 1 Write a non recursive version of binary search 2 If we replaced the if else structure inside the recursive binsearch function above with if x lt vmidl return binsearch v low mid1 x else return binsearch v mid high x would the function still work correctly 4 Summary 0 Algorithm analysis and order notation o Recursion is a way of de ning a function and or a structure in terms of simpler instances of itself While we have seen simple examples of recursion here ones that are easily replaced by iterative non recursive functions later in the semester when we return to recursion we will see much more sophisticated examples where recursion is not easily removed On Thursday we will proceed to C classes Data Structures 7 CSci 1200 Lecture 4 7 Classes Part 1 Review from Lectures 2 amp 3 0 C strings from the standard library 7 hold sequences of characters7 7 have a sophisticated set of operations de ned on them7 including resizing7 chang ing characters7 and appending new characters 0 Vectors7 also from the standard library 7 effectively they are smart7 dynamically sized arrays 7 should almost always be used instead of arrays 0 Strings and vectors 7 grow and shrink from their end highest subscripts rather than their beginning subscript 07 7 should almost always be passed by reference when it is desirable to ensure that no changes are made7 they should be passed by constant reference 0 Recursion is a way of de ning a function and or a structure in terms of simpler instances of itself We will see examples of recursive de nitions and recursive functions throughout the semester Today s Lecture C classes 0 Types and de ning new types 0 A Date class Class declaration member variables and member functions Using the class member functions Class scope c Member function implementation 0 Classes vs structs 0 Designing classes While this material will be a review for many of you7 it is important to make sure you understand the fundamentals 1 Background Reading Classes are covered in FordampTopp on pages 8 27 and 53 81 Introductory C texts all have background material on classes Types and De ning New Types 0 Q What is a type A A structuring of memory plus a set of operations functions that can be applied to that structured memory 0 Examples integers doubles strings and vectors 0 In many cases when we are using a class we do not know how that memory is struc tured Instead What we really think about is the set of operations functions that can be applied 0 To clarify let s focus on strings and vectors These are classes We ll outline what we know about 7 The structure of memory within each class object 7 The set of operations de ned 0 We are now ready to start de ning our own new types using classes Example A Date Class 0 Many programs require information about dates 0 Information stored about the date includes the month the day and the year 0 Operations on the date include recording it printing it asking if two dates are equal ipping over to the next day incrementing etc C Classes 0 A C class consists of 7 a collection of member variables usually private and 7 a collection of member functions usually public which operate on these vari ables 0 public member functions can be accessed directly from outside the class 0 private member functions and member variables can only be accessed indirectly through public member functions 0 We will look at the example of the Date class declaration provided in le Date h Using C classes We have been using C classes from the standard library already this semester so by studying how the Date example we are just repeating what we have already done but this time with a class we have de ned We will illustrate with the le datemain cpp 0 De ning class objects 7 Important note each object we create of type Date has its own distinct mem ber variables 0 Calling class member functions for class objects using the dot notation For exam ple tomorrow increment O 0 Note after looking at the example we still will not have examined how the class member functions are implemented This is an important feature of class design Exercise Hand write code that could be added to datemain Cpp to read in another date check if it is a leap year and check if it is equal to tomorrow In each of the latter two cases output an appropriate message based on the results of the check Class Implementation We will illustrate the concepts of class implementation through the Date example looking at the implementation le Date Cpp Class scope notation 0 Date indicates that what follows is within the scope of the class 0 You will have to get accustomed to the notation of class member functions 0 Within class scope the member functions and member variables are accessible without the name of the object Constructors These are special functions that initialize the values of the member variables You have already used constructors for string and vector objects 0 The syntax ofthe call to the constructor can be confusing It mixes variable de nitions and function calls See dateJnain opp 0 Default constructors have no arguments Multiple constructors are allowed just like multiple functions with the same name are allowed The compiler determines which one to call based on the argument list This must match in type the parameter list just like any other function call When a new object is created EXACTLY one constructor for the object is called You can t prevent it from happening You can only control which one is called Member Functions These are like ordinary functions except 0 They can access and modify the object s member variables 0 They can call the member functions without using an object name 0 Their syntax is slightly different because they are de ned within class scope Important member functions to study 0 set and get functions access and change a day month or year c increment uses another member function isLastDayInMonth o isEqual accepts a second Date object and then accesses its values directly using the dot notation 7 Since we are inside class Date scope this is allowed 7 The name of the second object date2 is required to indicate that we are inter ested in its member variables 0 lastDayInMonth uses the const array de ned at the start of the cpp le Accessing and changing member variables 0 When the member variables are private the only means of accessing them and chang ing them from outside the class is through member functions o If member variables are made public they can be accessed directly This is usually considered bad style and will not be allowed in this course Nonmember functions 0 Functions that are not members must interact with Date objects through the class public members the public interface77 declared for the class 0 These may perform operations that are closely associated with the class and therefore feel like member functions 0 One example is the function sameDay which accepts two Date objects and compares them by accessing their day and month values through their public member functions Header les and Implementation les cpp The code for the Date example is in three les 0 Date h contains the class declaration 0 Date Cpp contains the member function de nitions Date h is included 0 maindatecpp contains the code outside the class Date h again is included o The les Datecpp and maindatecpp are compiled separately and linked to form the executable program 0 Different organizations of the code are possible but not preferrable 7 For example we could have combined Dateh and Datecpp into a single le and included them in the main program 7 In this case we would not have to compile two separate les 0 In many large projects programmers establish the convention that requires exactly two les per class one header le and one implementation le Constant member functions Member functions that do not change the member variables should be declared const 0 For example bool Date isEqualconst Date ampdate2 const 0 This must appear consistently in both the member function declaration in the class declaration and the member function de nition 0 const objects usually passed as parameters can ONLY use const member functions 7 Remember you should only pass objects by value under special circumstances In general pass them by const reference if you do not want them to change 0 While you are learning you will tend to make errors in determining which member functions should or should not be const Watch for them when you compile les containing your class headers and member function de nitions Exercise Add a member function to the Date class to add a given number of days to the Date object The number should be the only argument and it should be an unsigned int Should this function be const Classes vs structs o Technically a struct is a class where the default protection is public not private 7 As mentioned above when a member variable is public it can be accessed and changed directly using the dot notation 7 For example tomorrowday 52 We can see immediately that this is dangerous because a day of 52 is invalid o The usual practice of using struct is all public members and no member functions This practice is contrary to the usual conventions of C programming Rule for the duration of CSCI 1200 We will not allow the use of struct and no member variable can be made public This will be enforced with various levels of grading penalties C vs Java Classes 0 ln C l 7 classes have sections labeled public and private7 but there can be multiple public and private sections In Java7 each individual item is tagged public or private 0 Class declarations and class de nitions are separated in C ll 7 whereas they are to gether in Java 0 In C here is a semi colon at the end of the class declaration after the Designing and implementing classes This takes a lot of practice7 but here are some ideas to start from 0 Begin by outlining what the class objects should be able to do This gives a start on the member functions 0 Outline what member variables might be needed to accomplish this 0 Write a draft class declaration in a h le 0 Write code that uses the member functions Revise the class h le as necessary 0 Write the class cpp le that implements the member functions In general7 do not be afraid of major rewrites if you nd a class is not working correctly or is not as easy to use as you intended This happens frequently in practice Data Structures i CSci 1200 Homework 2 Crossword Assistant Overview Are you good at crossword puzzles I m not It would be very nice if there were a system that generated possible matches for me and then I could judge which words t the clues This is a far cry from What you will see when you watch Watson play Jeopardy this month but you are just getting started This homework is worth 60 points toward your homework grade Because of the delays with the snowstorm on February 2 this is now due Thursday February 10 2011 at 115959 pm Please note the following 0 See the course web site for information about making up Lab 2 0 You may have only one late day on this homework which means that all submissions must be in by Friday February 10 2011 at 115959 pm 0 You are also forewarned that there may not be any ALAC help available on the homework due date 0 The delay in the due date of this homework will not delay Test 1 which is scheduled for Monday February 14th in class This is the second of two warm up homeworks that explore the use of basic constructs of C Starting with Homework 3 you will use classes and containers and solve larger projects See the course syllabus for discussion of the late policy See the course website for discussion of homework submission and homework grading See the academic integrity statement for discussion of what collaboration is and is not acceptable You may use any technique discussed in Lectures 1 4 or Labs 1 and 2 If you Wish you may also use structs or classes but that is not at all necesssary for this assignment Speci cs 7 Part 1 You are given a dictionary of potential words speci ed as a le of strings Each string will be all lower case letters You will read in this dictionary at the start of your program Next you will read a series of partial words to match against Each partial word will consist of letters and characters Your main problem is to nd all words in the dictionary that could match a partial word Matching occurs when all of the letters in the partial word match up in the same location as a word in the dictionary The blanks match with anything essentially they are just place holders to show the length of the word and the positions of the letters As an example given the partial word pl ve characters with 7p7 in location 2 and 7l7 in location 3 matches apple and maple but does not match apples or sample Your program should run with the command line match dictionary words results where results is the output le For each partial word in the words folder the program should output the following items 0 the partial word 0 the number of dictionary words that it will check against for Part 1 this can be the length of the entire dictionary 0 the number of words in the dictionary that matches 0 the matched words if any in alphabetical order Follow the example on the course website After all of the partial words have been input your program should output the average number of words matched per partial word and then it should output the number of times each word in the dictionary was matched skipping the words that were not matched at all Just to be clear all output must be to the results le You may choose to output debugging information to std cout but this will be ignored during grading Speci cs Part 2 If you implement the foregoing successfully you can earn at most 54 of the 60 points The problem you need to address to be able earn all 60 points is how to make this much faster by only searching words of the appropriate length The dictionary you are given will be sorted by length You must come up with a method that selects the subset of words to test based on the length of a partial word For example in the dictionary1txt le distributed with this homework words of length 6 start with sensor at location 13 the 14th word and end with musket at location 20 If a partial word is length 6 only these 8 words must be checked To demonstrate that you have implemented this successfully your program must output the number of words that you check against for a particular partial word See the course website for examples and follow these as best you can readmetxt le Your submisison must also include a readmetxt le see the le provided with the homework download that explains your progress with Parts 1 and 2 and that explains your method of solving Part 2 To satisfy this requirement you must only answer the questions posed in the downloaded Ieadme txt le Getting Started Start by outlining the important functions you must write for the rst part and then implement and test them Next write the code to open the input and output les and to read the input les At each stage check your results and save a copy of your program Only when you are sure you have the rst part working should you continue to Part 2 If you do not complete Part 2 successfully submit your working code for Part 1 Data Structures 7 CSci 1200 Homework 1 Popping Pigs Overview Many of you 7 perhaps most of you 7 have played Angry Birds by now or know someone who has In the simplest version of the game birds are red from a slingshot in the direction of pigs and when the birds strike the pigs the pigs explode This game like many video games requires a simulation of the geometry and physics of movement intersection and collision Homework 1 investigates a very simple version of this This homework is worth 60 points toward your homework grade and is due Tuesday Febru ary 1 2011 at 115959 pm See the course syllabus for discussion of the late policy See the course website for discussion of homework submission and homework grading See the academic integrity statement for discussion of what collaboration is and is not acceptable You may use any technique discussed in Lectures 1 or 2 or Lab 1 ofthe course as well as methods discussed on the course website If you wish you may also use structs or classes but that is not at all necesssary for this assignment Speci cs You are given a series of pigs represented as non interesting circles Circles are speci ed as three oating point values giving the x location and y location of the pig center and the pig radius Birds which have no radius y in a straight line not a parabolic arc starting from the 00 location which means a bird need only be speci ed by an angle 9 with the positive x axis being 0 and the angle formed by a counter clockwise rotation Whenever a bird7s path touches or intersects the circle representing a pig the pig is popped and the bird ies on without being diverted potentially popping other pigs Stating this mathematically which is what s needed to simulate the game any pig whose circle intersects a bird s ray of points t cos 0tsin 0 for t Z 0 is popped We will not worry about the order in which the pigs are popped by a particular bird The input will come from a single text le The rst line of the le will give an integer value 71 being the number of pigs You may assume without checking that n g 100 although if you use vectors instead of arrays you need not make this assumption This will be followed by 71 lines with each line containing three oat values 7 the x y and r values of the pig circles After these 71 lines you will have some number of oat values each representing the direction of a bird Thus for example if the input le is 3 15 65 14 96 46 26 75 89 18 45 6O 75 23 There are three pigs and then four birds shot in directions 45 60 75 and 23 Three different types of output will come from the program written to an output le 0 Check to see if any of the circles intersect Check all pairs of circles7 and if any pairs do inter sect7 there should be an error message output and the game program should not continue The format of this error message will be shown in the examples You may assume without checking that no pig circle encloses the 00 point This means that the birds aren t shot from inside a pig 0 When a bird pops a pig7 an output message should be generated Birds will be identi ed by their directions 457 607 75 or 23 in the above example7 and pigs by their indices 07 1 or 2 in the above example Follow the example output format posted on the course web site Note that once a bird pops a pig7 a subsequent bird can not pop the same pig 0 At the end of the program7 a message should be output indicating either that all pigs were popped7 or how many pigs remained Once again7 see the examples on the course web site In summary7 your program should run with a single command line of the form poppigs datafile outfile where data file is the name of the le containing the pig and bird information Except for command line argument errors7 all output should go to out file It is important to try to match our output as precisely as possible Popping Pigs and Intersecting Pigs We don t necessarily expect that you could come up with the equations and functions for the bird pig linecircle intersection or the pig pig circlecircle intersection on your own The function7 popspig7 that tells if a bird pops a pig7 is posted on the course web site You may use it exactly as is You may also write your own version7 of course Determining if two circles intersect is easy You just need to calculate the distance between the center points and compare it to the sum of the two circle radii If the distance is less than the sum7 the circles intersect StepBy Step Program Development Guide For this assignment7 we provide you with the following outline of steps for developing7 writing and testing this program You should follow similar steps in future assignments If you go to of ce hours or advising for help on Homework 17 you must show your progress in attemping to follow these steps 1 Implement and test two functions the one given above to determine if a bird pops a pig7 and a second to test if two pigs circles intersect Write a very simple main program that provides hand speci ed values to test the functions Save a copy of the result7 then delete the test main function you wrote and continue on An example of this is already given for you on line in checking the popspig function to Implement and test the code in the main function to check the command line arguments7 open the input le7 and read the pigs and birds Look carefully at the links for Misc Programming Info77 on the course website and at the nal example from Lecture 2 for aid in reading command line arguments Add code after reading the data to output it Save a copy of the resulting code here as well 3 F Implement and test the code to check to see if any pigs intersect each other You will need two nested for loops to do this along with a bool variable that is set whenever you discover that two pigs circles intersect Implement and test the code to read the birds and determine which birds pop which pigs You will need a vector of bools to determine whether or not a pig has been popped7 and thereby help to prevent a pig from being popped more than once You will also need a way to determine how many pigs were popped Data Structures i Lecture 2 Strings and Vectors 1 Overview of Lecture 2 The following topics will be covered 0 Complete discussion of scope from Monday lecture 0 Strings o Vectors as smart arrays77 2 Background Reading All reading references are to FordampTopp7 0 Strings pp 28 35 0 Vectors Chapter 4 Much of what is covered here is basic background for C programming and is covered in Virtually any introductory text 3 C Strings 31 Example 1 Here is example output of a program that reads in a string and outputs a framed greeting Please enter your first name Chuck Hello Chuck The program is on the next page ask for a person s name and generate a framed greeting include ltiostreamgt include ltstringgt int main stdcout ltlt quotPlease enter your first name quot stdstring name stdzzcin gtgt name build the message that we intend to write const stdstring greeting quotHello quot name quotquot build the second and fourth lines of the output const stdstring spaces greetingsize const stdstring second quot quot spaces quot quot build the first and fifth lines of the output const stdstring firstsecondsize write it all stdcout ltlt stdendl stdcout ltlt first ltlt stdendl stdcout ltlt second ltlt stdendl stdcout ltlt quot quot ltlt greeting ltlt quot quot ltlt stdendl stdcout ltlt second ltlt stdendl stdcout ltlt first ltlt stdendl return 0 32 string objects 0 A string is an object type de ned in the standard library to contain a sequence of characters 0 The string type like all types including int double char float de nes an in terface which includes construction initialization operations functions methods and even other typesl c When an object is created a special function is run called a constructor Whose job it is to initialize the object The greeting example code exhibits three ways of constructing string objects 7 By default to create an empty string 7 With a speci ed number of instances of a single char 7 From another string 0 The notation greeting size 0 is a call to a function size that is de ned as a member function of the string class There is an equivalent member function called length 0 Input to string objects through streams includes the following steps 1 The computer inputs and discards white space characters one at a time until a non white space character is found to A sequence of non white space characters is input and stored in the string This overwrites anything that was already in the string OJ Reading stops either at the end of the input or upon reaching the next white space character without reading it in The overloaded operator 7 is de ned on strings lt concatenates two strings to create a third string without changing either of the original two strings o The assignment operation 77 on strings overwrites the current contents of the string 33 Exercise H Consider the following code fragment stdzzstring a b c stdzzcin gtgt a gtgt b gtgt 6 and the input allcows eat123 grass every good boy deserves fudge What will be the values of strings a b and c at the end of the code fragment to Write a C program that reads in two strings outputs the shorter string on one line of output and then outputs the two strings concatenated together with a space between them on the second line of output 34 C vs Java Standard C library std string objects behave like a combination of Java String and StringBuffer objects If you aren t sure of how a std string member function or operator will behave check its semantics or try it on small examples or both which is preferable 0 Java objects must be created using new as in String name new StringquotChrisquot This is not necessary in C The C approximate equivalent to this example is std string namequotChrisquot On the other hand there is a new operator in C and its behavior is somewhat similar to the new operation in Java We will study it later in the semester 35 More on strings 0 Strings behave like arrays when using the subscript operator 7 This gives access to the individual characters in the string 7 Subscript 0 corresponds to the rst character 7 For example given std string a quotSusanquot Then a0 8 and a1 u and a4 n 0 Strings de ne a special type which is the type returned by the string functions size and length string sizetype 7 The notation means that sizetype is de ned within the scope of the string type 7 string sizetype is generally equivalent to unsigned int 7 You may have compiler warnings and potential compatibility problems if you compare an int variable to asize 36 Example Problem Writing a name along a diagonal Here is a more interesting problem What is your first name Peter 969696969696 D 969696969696 37 Solution Approach 1 0 Initial stuff read the name7 and output a blank line7 as in an earlier example 0 Let s think about the main output think of the output region as a grid of rows and columns 7 How big is this region 7 What gets output where o This leads to an implementation with two nested loops7 and conditionals used to guide Where characters should be printed 38 Solution 1 Program diagonalname Author Chuck Stewart Purpose A program that outputs an input name along a diagonal include ltiostreamgt include ltstringgt using namespace std int main cout ltlt quotWhat is your first name quot string first cin gtgt first const string star1ine first size4 const string blanks firstsize2 const string emptyline 7 blanks 77 cout ltlt n ltlt starline ltlt n ltlt emptyline ltlt n Output the interior of the framed greeting one line at a time for string sizetype i 0 iltfirst size i Job of loop body is to write a row of output containing s in the first Oth and last columns the ith letter in column i2 and a blank everywhere else for string sizetype j 0 j lt first size4 j if j II j first size3 cout ltlt else if j i2 cout ltlt firsti cout ltlt n cout ltlt emptyline ltlt n ltlt starline ltlt n return 0 39 Aside Ending a Line of Output 0 There are two common ways to end a line of output in a C program std cout ltlt n and std cout ltlt std endl What is the difference C streams store their output in an output bu er This buffer is not immediately written to a le or displayed on your screen The reason is that the writing process is much slower than the other computations It is much faster overall when output is buffered and then done all at once77 7 in large chunks 7 when the buffer is full 0 Thus7 just outputting the n 7 the end of line character 7 just adds one more character to the buffer Outputting std endl has two effects 7 Outputting the n character7 and 7 Causing the buffer to be ushed 7 actually output to the le or screen Why should you care 7 When your program crashes7 the contents of the output buffer are lost and not actually output As a result7 when looking at your output it often appears that your program crashed much earlier than it actually did Therefore7 using std endl helps greatly with debugging 7 But7 using std endl can substantially slow down a program that has a lot of output Therefore7 when a program is fully debugged and needs to run at a reasonable speed7 std endl should be replaced by n 310 Loop Invariants 0 De nition a loop invariant is a logical assertion that is true at the start of each iteration of a loop 7 In for loops7 the start is de ned as coming after the initializationincrement and termination test7 but before execution of the next loop iteration 0 An invariant is stated in a comment it is not part of the actual code 0 It helps determine 7 The conditions that may be assumed to be true at the start of each iteration 7 What must be done in each iteration 7 What must be done at the end of each iteration to restore the invariant 0 Analyzing the code relative to the stated invariant also helps explain the code and think about its correctness 311 L Values and R Values 0 Consider the simple code string a quotKimquot string b quotTomquot a0 b0 String a is now quotTimquot No big deal right Wrong Let s look closely at the line a0 b0 and think about what happens In particular what is the difference between the use of a0 on the left hand side of the assignment statement and b 0 on the right hand side 0 Syntactically they look the same But 7 The expression b 0 gets the char value T from string location 0 in b This is an r ualue 7 The expression a0 gets a reference to the memory location associated with string location 0 in a This is an l ualue 7 The assignment operator stores the value in the referenced memory location The difference between an r ualue and an l ualue will be especially signi cant when we get to writing our own operators 312 A Second Solution To Our Diagonal Name Problem Here are ideas for a second solution 0 Think about what changes from one line to the next 0 Suppose we had a blank linequot string containing only the beginning and ending asterisks and the intervening blanks c We could overwrite the appropriate blank character output the string and then restore the blank character The second solution will be posted on line 313 Thinking about problem solving Often it is easier to start by working on simpli ed versions of the problem to get a feel for the core issues In the example we considered a good start would be to think about writing the name along the diagonal without any framing We considered two solution approaches 7 Thinking of the output as a two dimensional grid and using logical operations to gure out what to output at each location 7 Thinking of the output as a series of strings one string per line and then thinking about the differences between lines There are often many ways to solve a programming problem Sometimes you can think of several while sometimes you struggle to come up with one When you have nished a problem or when you are thinking about someone else s solution it is useful to think about the core ideas used If you can abstract and understand these ideas you can later apply them to other problems 4 Standard Library STL Vectors 41 Problem Grade Statistics 0 Read an unknown number of grades 0 Compute 7 Mean average 7 Standard deviation 7 Median middle value c Accomplishing this requires the use of vectors 4 2 Standard Deviation 0 De nition if a0a1a2 an1 is a sequence of n values and a is the average of these values then the standard deviation is A ELOIQM NZ 2 n 7 1 0 Computing this equation requires two passes through the values 7 Once to compute the average 7 A second time to compute the standard deviation 0 Thus we need a way to store the values 0 The only tool we have so far is arrays But arrays are xed in size and we don7t know in advance how many values there will be c This illustrates one reason why we generally will use standard library vectors instead of arrays 43 Vectors 0 Standard library container class77 to hold sequences 0 A vector acts like a dynamically sized onedimensional array 0 Capabilities 7 Holds objects of any type 7 Starts empty unless otherwise speci ed 7 Any number of objects may be added to the end 7 there is no limit on size 7 It can be treated like an ordinary array using the subscripting operator 7 There is NO automatic checking of subscript bounds 44 Computing the Standard Deviation A program to compute the standard deviation is provided with these notes averageiandideviation Cpp We will use this to discuss the use of vectors 0 Header les include ltvectorgt de nes the vector class inc lude ltcmathgt includes the C standard math library prototypes and declarations so that we can use the sqrt function 0 The following creates an empty vector of integers vectorltintgt scores Vectors are an example of a templated container class 7 The angle brackets lt gt are used to specify the type of object the template type that will be stored in the vector 0 pushiback is a vector function to append a value to the end of the vector7 increasing its size by one This is an 01 operation on average 7 There is NO corresponding pushifront operation for vectors 0 size is a function de ned by the vector type the vector class that returns the number of items stored in the vector 0 After vectors are initialized and lled in7 they may be treated just like arrays 7 In the line sum scores i scores i is an r value 7 accessing the value stored at location i of the vector 7 We could also write statements like scores 4 100 to change a score Here scores 4 is an l value 7 providing the means of storing 100 at location 4 of the vector 7 It is the job of the programmer to ensure that any subscript value i that is used is legal 7 at least 0 and strictly less than scoressize 45 Median o lntuitively a median value of a sequence is a value that is less than half of the values in the sequence and greater than half of the values in the sequence More technically if a0 11012 an1 is a sequence of n values AND if the sequence is sorted such that a0 a1 a2 annl then the median is twin2 if 77 is Odd M if n is even 2 Sorting is therefore the key to nding the median 46 Standard Library Sort Function 0 The standard library has a series of algorithms built to apply to container classes The prototypes for these algorithms actually the functions implementing these algo rithms are in header le algorithm One of the most important of the algorithms is sort o It is accessed by providing the beginning and end of the containers interval to sort 0 As an example the following code reads sorts and outputs a vector of doubles double x stdzzvectorltdoublegt a while stdzzcin gtgt x apushbackx stdsort abegin aend for unsigned int i0 iltasize i stdcout ltlt ai ltlt n abegin is an iterator referencing the rst location in the vector while aend is an iterator referencing one past the last location in the vector 7 We will learn much more about iterators in the next few weeks 7 Every container has iterators strings have begin and end iterators de ned on them The ordering of values by std sort is least to greatest technically non decreasing We will see ways to change this 47 Computing the Median A program medi angrade Cpp that uses a vector to compute the median of a set of grades is provided with these notes and will be posted on line 48 Passing Vectors and Strings As Parameters The following outlines rules for passing vectors as parameters The same rules apply to passing strings 4 D o If you are passing a vector as a parameter to a function and you want to make a permanent change to the vector then you should pass it by reference 7 This is illustrated by the function read cores in the program mediangrade 7 This is very different from the behavior of arrays as parameters What if you don t want to make changes to the vector or don t want these changes to be permanent 7 The answer we ve learned so far is to pass by value 7 The problem is that the entire vector is copied when this happens The solution is to pass by constant reference pass it by reference but make it a constant so that it can not be changed 7 This is illustrated by the functions computejvgijstdAev and computeJnedian in the program medi angrade As a general rule you should not pass a container object such as a vector or a string by value because of the cost of copying There are rare circumstances in which this rule may be violated but not in Data Structures Initializing a Vector 7 The Use of Constructors Here is an example of several different ways to initialize a vector vectorltintgt a 1 int n 100 vectorltdoublegt b 100 314 2 vectorltintgt c nn 3 vectorltdoublegt d b 4 vectorltintgt e b 5 Version 1 constructs an empty vector of integers Values must be placed in the vector using pushback Version 2 constructs a vector of 100 doubles each entry storing the value 314 New entries can be created using pushback but these will create entries 100 101 102 etc Version 3 constructs a vector of 10000 ints but provides no initial values for these integers Again new entries can be created for the vector using pushback These will create entries 10000 10001 etc Version 4 constructs a vector that is an exact copy of vector b Version 5 is a compiler error because no constructor exists to create an int vector from a double vector These are different types 13 410 Exercises 1 After the above code constructing the three vectors what will be output by the following statement cout ltlt asize ltlt endl ltlt bsize ltlt endl ltlt csize ltlt endl D Write code to construct a vector containing 100 doubles each having the value 555 03 Write code to construct a vector containing 1000 doubles containing the values 0 1 xg x5 etc Write it two ways one that uses pushback and one that does not use pushback 411 Additional Example 7 Alphabetize Strings Posted on line as part of the zip le containing code from this lecture is an additional example of using vectors strings and the sort function to alphabetize last names The source code will also be posted on the web This is an important example for future homeworks 5 Summary 0 C strings from the standard library hold sequences of characters and have a so phisticated set of operations de ned on them 0 Vectors also from the standard library can be thought of as smart dynamically sized arrays Vectors should almost always be used instead of arrays but as we will see vectors are de ned internally in terms of arrays


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

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

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

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

Steve Martinelli UC Los Angeles

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


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund 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


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:

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

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.