Honors Computer Science I
Honors Computer Science I COP 3502H
University of Central Florida
Popular in Course
Popular in Computer Programming
This 33 page Class Notes was uploaded by Luisa Beer on Thursday October 22, 2015. The Class Notes belongs to COP 3502H at University of Central Florida taught by Staff in Fall. Since its upload, it has received 29 views. For similar materials see /class/227472/cop-3502h-university-of-central-florida in Computer Programming at University of Central Florida.
Reviews for Honors Computer Science I
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/22/15
Modularity is an important part of the algorithmprogram design process Most algorithms solve complicated problems that are best understood and solved in pieces Modularity allows the designer to abstract the various pieces needed to solve the problem into manageable size tasks Subalgorithms are used to simplify the algorithm design and understanding This is notjust a available option but the core of good algorithm design Algorithms that do not feature modularity are low abstraction hard to understand and hard to debug Modularity must be incorporated into any well designed algorithm Each subalgorithm handles a single logical chunk of the solution The main algorithm coordinates the overriding logic Subtask 22V Graphical representation ofabstraction featuring modularity Modularity Functions 1 o It is abstraction because we are considering the essence each task apart from the embodiment its component parts o It is a hierarchy of abstraction because we re doing this at multiple levels main tasks subtasks subtasks of subtasks etc The details are hidden in the tasks and subtasks o The details of the algorithm are hidden in the subalgorithms This enhances understanding the algorithms by hiding obscure details 0 Makes the algorithm easier to write by reducing the complexity 0 Saves time space and effort Modules can be called from many different places within an algorithm Rather than repeating the task you simply call the same task again Sort of like speeddial on your phone Permits the reuse of logic lf properly designed modules can be reused across different algorithms All that is required is that the different algorithms need the same subtask to be performed Enhances the ability to maintain and reuse the implemented algorithm 0 An interface is the common boundary between two bodies or spaces In algorithmic terms the interface specifies how the module can be connected to the outside world ie to other algorithms Consider the problem ofobtaining a list of names sorting those names into alphabetical order and finally printing out the sorted list of names This problem can logically be broken into three separate tasks modules 1 An input module to read the list of names 2 A module to sort the names 3 An output module to print the sorted list of names Modularity Functions 2 When considering the second module to sort the names we can choose any sorting technique that we want and change it whenever we feel like it without affecting the rest of the algorithm One thing will remain constant throughout our changing of the sorting technique in the second module and this will be how the module interfaces with the outside world In other words it will always expect the same type of input and produce the same type of output regardless of the sorting technique that is currently employed in the module An interface between algorithmic modules is defined in terms of parameters Parameters are similar to other variables except that they specify the interface to a module Parameters are used only when it is necessary to pass information between modules 0 A parameter is a special kind of variable that allows a data value to be passed between a module and any algorithm that might use that module 0 A parameter specifies a communication channel between two algorithmic components There are two types of parameters 1 Call by Value parameters allow values to be passed into a module by the caller Call by value parameters are input parameters Calling M39Qdul39e variable El 2 Call by Reference parameters allow the module to return values to the caller Call by reference parameters are inputoutput parameters Calling Module variable Modularity Functions 3 In C we have a single construct that can be used to create modules which is the function Functions are categorized by their return types 0 Functions that return a value functions that perform some subtask that requires returning some value to the calling function 0 Void functions functions that perform some subtask that does not require a single value to be returned to the calling function To incorporated the modularity provided by functions in C programs you need to be able to do two things 1 Create functions 2 Call functions from the main function as well as other functions lFii n i39iiwi39i E A function s declaration prototype gives us all the information that we need to know about how to use the functions and no other details are provided For example double power double base double exponent This prototype tells us that the function is named power and it returns a type double and has two parameters both of which are of type double The general format of a function declaration in C is returntype functionname list of argument speci ers where returntype specifies the type returned by the function functionname any identifier you appropriately choose argument speci ers list of typeidentifier pairs showing the number of parameters with their types No information about how the function performs its task is provided however the user has enough information to invoke or use the function Modularity Functions 4 in aware l dlmsilw 71m Shown below are a few of the functions available in some of the various C libraries that you will find useful Libram otypeh int isalpha int 0 int isdigit int c int isupper int c int islower int c int tolower int c int toupper int c Libram mathh double cos double X double aoos double X double cosh double X double exp double X double oeil double X double floor double X double fabs double X double pow double X double y double sqrt double X Libra stlibh int randvoid void srand unsigned seed Modularity Functions 5 o A program is constructed of one or more functions one of which must be main 0 Each functions must have been defined before it is called The best way to organize modules in a program is to list the prototypes of all functions before the main function Their definition can be placed after the main function A function implementation describes in detail how the function performs its task Simply put a function implementation is a complete brief program that produces some effects if certain assumptions about the arguments to the function are satisfied The first line of the implementation is called the function heading The general form for a function implementation is Modularity Functions 6 ltfunction headinggt ltoptiona data declarationsgt ltexecutable statementsgt A function heading must match up with a corresponding function declaration prototype The return type and a function name must be the same in the heading as they are in the declaration and the arguments must match in a one toone correspondence between type and position In addition each type in the argument list of a function heading must be followed by an argument name usually called a formal parameter The formal parameter list must match the number of arguments usually called actual parameters used when the function is called The general form of a function heading is ltreturn typegt ltfunction namegt ltlist of formal parametersgt Data and Executable Statements in a Function Implementation 0 Declaration section is optional 0 The executable statement section has the same form as the executable statement section of the main function 0 Unless it is a void function a function implementation must include at least one statement of the form return ltexpressiongt Modularity Functions 7 In the function heading int min int num l int num2 int num3 H4 I The formal parameter list parameter variables and their types are declared here In the call to the module int smallest smallest min a b c I The actual parameter list cannot tell the parametertype from here The number of parameters in the actual and formal parameter lists must be consistent Parameter association in C is positional This means that the first actual parameter corresponds to the first formal parameter the second matches the second and so on Actual parameters and formal parameters must be of compatible data types Actual input parameters may be a variable constant or any expression matching the type of the corresponding formal parameter For example using the previous example we could have smallest min15 a 5b Modularity Functions 8 Function implementation Function min Finds the minimum of three integer values nput three integer values Output The integer which is the smallest in the list int min int num1 int num2 int num3 int minimum local declaration ifnum1 lt num2 minimum num1 else executable statements minimum num2 ifnum3 lt minimum minimum num3 return minimum returned value Calling the function min from the main program function include ltstdiohgt int main int q1 q2 q3 three quiz scores sid student id count counter for students double quizavg count 1 while count lt 30 printf n Enter student id and quiz grades scanf dddd ampsid ampq1 ampq2 ampq3 quizavg q1q2q3 minq1 q2 q32 printf 10d 72fn sid quizavg count count 1 end while loop return 0 Modularity Functions 9 A simple calculator include ltstdiohgt Function calculate This function computes the value of a simple arithmetic expression nput A character representing the operator it must be or and two integers representing the operands Output An integer value computed as the value ofthe given expression int calculate char operator int op1 int op2 int result if operator result op1 op2 else if operator 2 result op1 op2 else if operato result op1 op2 else result op1 op2 return result end function calculate caing algorithm int main char symbol int n1 n2 valid 0 do printf Enter the expression scanf cdd ampsymbol ampn1 ampn2 ifsymbol H symbol symbol symbol valid 1 else printf Unknown operator c Try againn while lvalid printf That computes to dn calculatesymbol n1 n2 return 0 end Modularity Functions 10 Function computegrade Returns a numerical value between 0 and 4 corresponding to a given letter grade lfthe grade is invalid a 1 will be returned lnput A single character The character must be one of the following A B KC D or F Output A numerical value A 4 B 3 C 2 D 1 and F 0 int computegrade char grade ifgrade A return 4 else if grade 8 return 3 else if grade 0 return 2 else if grad D return 2 else if grade F return 1 else return 1 end compute grade Modularity Functions 11 This program conducts a shopping spree and prints the total amount spent include ltstdiohgt double totawithtaxdouble value double taxrate int main char ans double totaspent 00 price tax rate printf Is there another item to buyn scanf c ampans while ans y read in value of item and taxrate printf Enter the item price and taxraten scanf lflf ampprice amptaxrate reset the total totaspent totaspent totawithtaxprice taxrate printf Is there another item to buyn scanf c ans printf You spent If on your shopping spreen totaspent return 0 end main Function totawithtax nput value is a positive number and taxrate is between 0 and 1 Output This function returns the total cost ofan item based upon its price and the taxrate double totawithtax double value double taxrate return value 1 taxrate endtotalwithtax Write a function that takes in a number n assumed to be an integer and computes the sum of the rst n integers and returns this value Write a program that uses the function from above to compute the first 20 triangle numbers The nth triangle number is simply the sum ofthe rst n numbers Modularity Functions 12 Solutions to exercises you were supposed to try Function trianglenum Computes the sum of the rst n integer numbers nput n is a positive integer Output The sum of1 2 3 n int trianglenum int n int index 1 sum 0 return 0 if input is invalid ifn lt 1 return 0 compute sum for index 1 index lt n index sum index return sum end function trianglenum include ltstdiohgt int trianglenum int n int main int index print rst 20 triangle numbers for index 1 index lt 20 index printf d triangle number is dn index trianglenumindex end main Function trianglenum Computes the sum of the rst n integer numbers nput n is a positive integer Output The sum of1 2 3 n int trianglenum int n int index 1 sum 0 return 0 if input is invalid ifn lt 1 return 0 compute sum for index 1 index lt n index sum index return sum end function trianglenum Modularity Functions 13 A void function does not return a value to the calling algorithm A return statement is not included in a void function After the last statement in a void function is executed the control of execution is returned to the calling point in the calling algorithm function void functionname formal parameters Modularity Functions 14 a A binary tree is a data structure that is made up of nodes and pointers much in the same way that a linked list is structures The difference between them lies in howthey are organized a A linked list represents a linear or predecessorsuccessor relationship between the nodes of the list A tree represents a hierarchical or ancestral relationship between the nodes 1 In general a node in a tree can have several successors called children In a binary tree this number is limited to a maximum of 2 a The top node in the tree is called the root 1 Every node in a binary tree has 0 1 or 2 children There are actually two different approaches to defining a tree structure one is a recursive definition and the other is a nonrecursive definition The nonrecursive definition basically considers a tree as a special case of a more general data structure the graph In this definition the tree is viewed to consist of a set of nodes which are connected in pairs by directed edges such that the resulting graph is connected every node is connected to a least one other node no node exists in isolation and cyclefree This general definition does not specify that the tree have a root and thus a rootedtree is a further special case of the general tree such every one of the node except the one designated as the root is connected to at least one other node In certain situations the nonrecursive definition of a tree has certain advantages however for our purposes we will focus on the recursive definition of a tree which is De nition A tree tis a nite nonempty set of nodes t r U T1 U T2 UU Tn with the following properties 1 A designated node ofthe set r is called the rootofthe tree and 2 The remaining nodes are partitioned into n 2 O subsets T1 T2 Tn each of which is a tree called the subtrees oft For convenience the notation t r T1 T2 Tn is commonly used to denote the tree t Binary Trees 1 A complete set of terminology has evolved for dealing with trees and we ll look at some of this terminology so that we too can discuss tree structures with some degree of sophistication As you will see the terminology of trees is derived from mathematical genealogical and botanical disciplines Rooted Tree from the nonrecursive definition A tree in which one node is specified to be the root call it node 0 Every node other than 0 call it b is connected by exactly one edge to exactly one other node call it p Given this situation p is b s parent Further b is one of p s children Degree of a node The number of subtrees associated with a particular node is the degree of that node For example using our definition of a tree the node designated as the root node r has a degree of n Leaf Node A node of degree 0 has no subtrees and is called leaf node All other nodes in the tree have degree of at least one and are called internal nodes Child Node Each root r of subtree t of tree 1 is called a child of r The term grandchild is defined in a similar fashion as is the term great grandchild Parent The root node r of tree 1 is the parent of all the roots r of the subtrees t 1ltiltn The term grandparent is defined in a similar manner Siblings Two roots r and r of distinct subtrees t and 1 of tree 1 are called siblings These are nodes which have the same parent The definitional restrictions placed on a binary tree when compared to a general tree give rise to certain properties that a binary tree will exhibit that are not exhibited by a general tree Some of these properties and corresponding terminology are defined below Number of nodes in a binary tree A binary tree 1 of height h h 2 0 contains at least h and at most 2 71 nodes Height of a binary tree The height of a binary tree that contains n n 2 0 nodes is at most n and at least l logg n1l Binary Trees 2 Full binam tree A binary tree of height h that contains exactly 2 71 nodes is called a full binary tree Each level i in the tree contains the maximum number of nodes ie every node in level i1 has two children 0 0 O 0 O O a full binary tree height 3 23 1 7 39 39 number of nodes 7 not a full binary tree height 4 24 1 15 number of nodes 7 Complete binary tree A binary tree of height h in which every level except level 0 has the maximum number of nodes and level 0 nodes are placed from left to right on the level with no missing nodes Note that a full binary tree is a special case of a complete binary tree in which level 0 contains the maximum number of nodes Some complete binary trees are shown below 0O 0O 0 A Want to insert the leftchild to the left of its parent and the rightchild to the right of its parent Common technique is to insert in order of arrival and always place element as close to the root as possible given a choice In other words do not arbitrarily make the tree taller Binary Trees 3 I I I I I l l I I don t insert here Consider the expression a b c d P P G E Q a A binary tree has a natural linked representation A separate pointer is used to reference the root of the tree a Each node has a left and right subtree which is reachable with pointers Binary Trees 4 Binary Trees 5 Tree 1 Tree 2 Binary Trees 6 0 65 0 0 Practice Binary Tree Traversal Answers Tree 3 we 9 a Preorder Visit node visit left subtree visit right subtree Inorder Visit left subtree visit node visit right subtree Postorder Visit left subtree visit right subtree visit node Tree 1 Preorder 4030 10 32 35 7060 65 90 Inorder 10 3032 3540 60 6570 90 Postorder 1035 32 3065 6090 70 4O Binary Trees 7 Tree 2 Preorder 4030 105 1532 3570 60 6590 95 Inorder 5 10 1530 3235 40 6065 7090 95 Postordel39 5 15 10 35 3230 6560 95 9070 40 Tree 3 Preorder 4030 105 15 13 1232 35 7060 6566 67 6890 95 Inorder 5 10 12 13 1530 32 3540 6065 66 6768 70 9095 Postorder5 12 13 15 10 35 3230 68 67 66 6560 95 9070 40 The traversal algorithms shown above make exploit the fact that a binary tree can be recursively defined as A binary tree is a empty or u a node the root with two binary trees called the left subtree and the right subtree ofthe root Let s examine the inorder traversal algorithm again Consider the following binary tree and produce the inorder traversal using the algorithm above For practice do the preorder and postorder traversals as well Binary Trees 8 An inorder traversal of this binary tree produces B A F D G C E Notice that the search for a node to print moves as deeply as possible in the left subtree before ever considering the right subtree This is called a depth rst traversal The preorder and postorder traversals are also depthfirst traversals Now let s perform some other operations on binary trees Suppose that we want to find the largest value in a binary tree The following algorithm will accomplish this task struct treeNode int data struct treeNode left struct treeNode right int ndMax struct treeNode p int rootvalue left right max max 1 assume all values in the tree are positive integers ifp NULL rootvalue p gt data left findMax p gt left right ndMax p gt right find the largest ofthe tree values if left gt right max left else max right if rootvalue gt max max rootvalue return max es 9 Let s trace the execution of algorithm findMax on the tree shown below CDU ILOO intial call p root rootvaue 40 left findMaxptr to 54 left NULL return1 right NULL return1 return 54 right findMaxptr to 13 rootvaue 54 77 rootvaue 13 7 left findMaxptr to 23 rootvaue 23 8 left NULL return1 9 righ NULL return1 return 23 right findMaxptr to 77 rootvaue 77 left NULL return right NULL return return 77 77 1 1 On return left subtree search at 40 returns 54 right subtree pending left subtree of 13 returns 23 right subtree of 13 returns 77 tree rooted at 13 returns 77 as the right subtree at 40 tree at 40 has left subtree 54 and right subtree 77 77 is returned as maximum value in the tree Binary Trees 10 Now let s suppose that we want to add the values of every node in the tree together to produce a single sum Before looking at the algorithm below try this yourself to see if you can produce a correct recursive algorithm to solve this problem l motility 1935 L wweu from Let s trace the execution of algorithm sumTree on the tree shown below answer return 40 addp gtle139t addpgtright 40 54 addp gtle139t addpgtright addp gtright 40 54 O 0 addp gtright 40 54 0 0 13 addpgtleft addpgtright 4054OO132300addp gtright 4o54oo1323oo77ammommamxpwgm 40540O1323OO77OO 94 36 77 207 Binary Trees 11 A binary search tree is a binary tree that is either empty or in which each node contains a data value that satisfies the following 1 All data values in the left subtree are smaller than the data value in the root 2 The data value in the root is smaller than all values in its right subtree 3 The left and right subtrees are also binary search trees A binary search tree often abbreviated to BST allows for fast searching t amounts to embedding the binary search into the data structure Shown below is an example BST A binary search tree Obviously a BST is designed for quick searching and this is an extremely common operation on this data structure and it is the first algorithm that we present for it Binary Trees 12 Inserting a new node into a BST always occurs at a NULL pointer There is never a case when existing nodes need to be rearrange to accommodate the new node As an example consider inserting the new value 43 into the BST shown below Where is the new node supposed to go Technique search for 43 and you won t find it but the search algorithm has taken you to the NULL pointer where it should be so this is the insertion point 43 should be here so put it here Binary Trees 13 Deletion of nodes in a BST can be broken into three separate cases and each is handled somewhat differently The cases are 1 deletion of a leaf node 2 deletion of an internal node with a single child either a left or right subtree and 3 deletion of an internal node with two children has both a left and right subtree We ll examine each case separately Since a leaf node has empty left and right subtrees deleting a leaf node will render a tree with one less node but which remains a BST This is illustrated below A BST with a leaf node The BST with the leaf node marked for deletion deleted A BST remains When the node has one child the case is also not too complicated but is more so than deleting a leaf node The parent s reference to the node is reset to refer to the deleted node s child This has the effect of lifting up the deleted node s children by one level in the tree All greatgreatgrandchildren will lose one great from their kinship designations An example is shown below Binary Trees 14 A BST with an internal node having only one child marked to be deleted 6 The marked internal node has only a right subtree so the parent ofthe deleted node will now reference the deleted node s child 3 Note that it makes no difference if the node to be deleted has only a left or a right child The previous example illustrated the case when the only child was a right child The next example illustrates the case when the only child is a left child lnitial BST with the node to be deleted shown in green Its only child is a left child a 9 9 9 0 The BST after the deletion has ooourred C9 0 9 Binary Trees 15 Notice that essentially all that occurred to delete an internal node with a single child is the parent of the deleted node becomes the parent of what formerly were its grandchildren The last case of deletion from a BST is the most difficult to handle There is no onestep operation that can be performed since the parent s right or left reference cannot refer to both node s children at the same time There are basically two different approaches that can be used to handle this case deletion via merging and deletion via copying which essentially reduce to the following scenario A deleted node with two children must be replaced by a value which is one of a The largest value in the deleted node s left subtree a The smallest value in the deleted node s right subtree The above technique means that we need to be able to find either the immediate predecessor or the immediate successor node to the node which is being deleted and replace the deleted node with this value As an example consider the following EST and suppose that we are deleting the value 18 from this tree Since the node containing 18 has two children it fits into this category for deletion lt s immediate predecessor is the rightmost node in its left subtree Binary Trees 16 which is 13 so our first choice would be to move 13 into the node currently occupied by 18 this is shown below We could have just as easily found the immediate successor of 18 which is the leftmost node it is right subtree and put this value into the place currently occupied by 18 This case is shown below Notice that in both cases the node which is physically deleted from the BST is a leaf node and this is the trivial deletion case Also notice that while there is no fundamental difference is selecting the immediate predecessor or the immediate successor as the replacement for the deleted value in reality there may be a difference The example above illustrates to some degree this difference which Binary Trees 17 results from a potential difference in the heights of the two subtrees In the example above the immediate predecessor was the better choice since it was only one level away from the node to be deleted and therefore our search to find this node would be shorter than the search to find the immediate successor which was two levels away While a few levels difference in the location of the immediate predecessor and immediate successor may not make much difference it certainly will if there is a big difference between the two heights and obviously the shorter the height the quicker the search and this is the way to go Shown below are three problems for you to practice writing algorithms for operations on binary trees As usual try these before you look at the answers on the last page of this set of notes for a possible solution Since the tree has a naturally occurring recursive definition make your functions recursive 1 Write a function that will count the number of leaf nodes in a binary tree 2 Write a function that will find the height of a binary tree The height of an empty tree is defined a zero The height of a single node tree is defined as 1 3 Write a function that will interchange all the left and right subtrees in a binary tree Binary Trees 18 Solution to Practice Problem 1 int numberofleaves struct treeNode p if pl NULL ifpgtleft NULL ampamp pgtright NULL return 1 else return numberofleavespgtleft numberofleavespgtright else return 0 Solution to Practice Problem 2 int height struct treeNode p int leftheight rightheight if p NULL return 0 else leftheight heightpgtleft rightheight heightpgtright if leftheight gt rightheight returnleftheight 1 else returnrightheight 1 Solution to Practice Problem 3 void interchange struct treeNode p struct treeNode temp if p NULL interchange pgtleft interchange pgtright temp pgtleft pgtleft pgtright pgtright temp Binary Trees 19
Are you sure you want to buy this material for
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'