CSE 235 Homework Template Nobel Khandaker Spring 2010 Problem Levitin 2 1 1 For each of the following algorithms indicate i a natural size matrix for its inputs ii its basic operation iii whether the basic operation count can be di erent for inputs of the same size a Computing the sum of n numbers Answer i n ii addition of two numbers iii no b Computing n Answer i log n ii Multiplication of two integers iii no c Finding the largest element in a list of n numbers Answer i n ii Comparison of two numbers iii Nothing else This document was created by Chris Bourke 1 1 Problem Prove that n n2 2 n Answer We have the following theorem from Levitin page 57 Theorem 1 Let f n and g n be two monotonically increasing functions then 0 f n O g n f n c f n g n lim n g n f n g n We set up our limit appropriately lim Therefore by Theorem 1 n n 1 2 n n n n2 2 n n 1 3x Here is a mathematical expression a b 2k ni 7y Note that it is written in line in the text The following mathematical expression is displayed on a new line centered but it is not assigned a number 3x a b 2k ni 7y The equation 1 has a number and a label which can be referenced in the text a b ni 3x 7y 1 The set of equations below are listed as an array Only two are numbered a b 2 a b 2 a2 b2 2ab a2 b2 2ab a b 3 a3 3a2 b 3ab2 b3 2 3 4 Problem Draw the graph K5 Answer K4 is shown in Figure 1 Problem De ne the semantics of the logical connective in Propositional logic 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Figure 1 A complete graph with 5 nodes Table 1 Definition of the logical connective a 0 0 1 1 b 0 1 0 1 a b 0 0 0 1 Answer Given two logical propositions a and b the semantics of is de ned in Table 1 Problem Give an algorithm to compute the sum of n integers stored in an array A Answer The following algorithm computes the sum Summation A 0 n 1 Input an integer array A n 1 Output the summation i 0 A i sum 0 for i 0 n 1 sum sum A i return sum Compiling Your Document Now that our document is nished we need to compile it If you are on CSE or any other system that has LATEX installed then you compile this document from the command line as follows latex hw example tex LATEX will do its thing and report any errors that you may have otherwise it will successfully compile in to a dvi le named hw example dvi At this point you have several options You can convert the dvi le into a pdf le or a postscript le by using either dvipdf or dvips respectively Another alternative is to use pdflatex instead of latex which automatically outputs a pdf le rather than a dvi le If you have labels like our label label theorem asymptotics you will need to run latex or pdflatex 2 or three times to compile the proper references Additional Tools You can use a program called ispell from the command prompt to spell check your document Conveniently ispell ignores LATEX markup If you are just getting used to the linux environment one of the best text editors for LATEXbesides emacs and xemacs is nedit This text editor recognizes LATEX markup uses font and color o sets to help you out Additional Resources The main source for LATEX resources is the TEX Users Group http www tug org in particular check out their page for beginners Getting Started With LATEX at http www tug org begin One of the best tutorials is the Not So Short Introduction to LATEX 2e which can be found at http www ctan org tex archive info lshort english lshort pdf Good Luck on your LATEXing References 1 Chris Bourke Using latex to typeset your homework example 2004
View Full Document
Unlocking...