CSE 235 Homework Template∗Nobel KhandakerSpring 2010Problem: (Levitin 2.1.1) For each of the following algorithms, indicate (i) anatural size matrix for its inputs; (ii) its basic operation; (iii) whether the basicoperation count can be different for inputs of the same size.a. Computing the sum of n numbersAnswer:i. nii. addition of two numbersiii. nob. Computing n!Answer:i. ⌈log n⌉ii. Multiplication of two integersiii. noc. Finding the largest element in a list of n numbersAnswer:i. nii. Comparison of two numbersiii. Nothing else.∗This document was created by Chris Bourke [1].1Problem: Prove thatn(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, thenlimn→∞f(n)g(n)=0 ⇒ f (n) ∈ O(g(n))c ⇒ f (n) ∈ Θ(g(n))∞ ⇒ f (n) ∈ Ω(g(n))We set up our limit appropriately:limn→∞n(n−1)2n= n − 1 = ∞Therefore, by Theorem 1,n(n2)2∈ Ω(n)Here is a mathematical expression: (a + b)2kni3x7y. Note that it is written in line,in the text.The following mathematical expression is displayed on a new line, centered, butit is not assigned a number:(a + b)2kni3x7yThe equation (1) has a number and a lab el, which can be referenced in the text.(a + b)ni3x7y(1)The set of equations below are listed as an array. Only two are numbered.(a + b)2= a2+ b2+ 2ab (2)(a + b)2= a2+ b2+ 2ab (3)(a + b)3= a3+ 3a2b + 3ab2+ b3(4)Problem: Draw the graph K5.Answer: K4is shown in Figure 1Problem: Define the semantics of the logical connective ∧ in Propositionallogic.00110001110001110001110011Figure 1: A complete graph with 5 nodes.Table 1: Definition of the logical connective ∧.a b a ∧ b0 0 00 1 01 0 01 1 1Answer: Given two logical propositions a and b, the semantics of ∧ is definedin Table 1:Problem: Give an algorithm to compute the sum of n integers stored in anarray A.Answer: The following algorithm computes the sum:Summation(A[0 . . . n − 1])Input: an integer array AOutput: the summation∑n−1i=0A[i]sum = 0for i = 0 . . . (n − 1)sum = sum + A[i]return sumCompiling Your DocumentNow that our document is finished, we need to compile it. If you are on CSEor any other system that has LATEX installed, then you compile this documentfrom the command line as follows: latex hw example.texLATEX will do its thing and report any errors that you may have, otherwise it willsuccessfully compile in to a dvi file named hw example.dvi. At this point youhave several options. You can convert the dvi file into a pdf file or a postscriptfile by using either dvipdf or dvips respectively. Another alternative is to usepdflatex instead of latex, which automatically outputs a pdf file rather thana dvi file.If you have labels like our label, \label{theorem:asymptotics}, you will needto run latex or pdflatex 2 or three times to compile the prop er references.Additional ToolsYou can use a program called ispell from the command prompt to spell checkyour document. Conveniently, ispell ignores LATEX markup!If you are just getting used to the linux environment, one of the best text editorsfor LATEXbesides emacs and xemacs is nedit. This text editor recognizes LATEXmarkup uses font and color offsets to help you out.Additional ResourcesThe main source for LATEX resources is the TEX Users Group: http://www.tug.orgin particular, check out their page for beginners, Getting Started With LATEX athttp://www.tug.org/begin.One of the best tutorials is the Not So Short Introduction to LATEX 2e whichcan be found athttp://www.ctan.org/tex-archive/info/lshort/english/lshort.pdfGood Luck on your LATEXingReferences[1] Chris Bourke. Using latex to typeset your homework example.
View Full Document