CSE 310 Homework 0 Chris Bourke Fall 2004 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 different 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 dlog ne 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 no 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 n n 1 2 n Therefore by Theorem n n2 2 n n 1 n 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 AP 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 finished 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 file named hw example dvi At this point you have several options You can convert the dvi file into a pdf file or a postscript file by using either dvipdf or dvips respectively Another alternative is to use pdflatex instead of latex which automatically outputs a pdf file rather than a dvi file 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 offsets 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