{"id":2232,"date":"2018-01-04T13:30:45","date_gmt":"2018-01-04T20:30:45","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/?page_id=2232"},"modified":"2018-01-16T16:36:02","modified_gmt":"2018-01-16T23:36:02","slug":"sample-problems-for-tutorial-1","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/sample-problems-for-tutorial-1\/","title":{"rendered":"Sample problems for tutorial week #1"},"content":{"rendered":"
    \n
  1. Rank the following functions by order of growth. That is, order them so that f1<\/sub> \u2208 O(f2<\/sub>), f2<\/sub> \u2208 O(f3<\/sub>), etc. Make sure to indicate whether or not fi<\/sub> \u2208 \u0398(fi+1<\/sub>). For instance you could use the notation n < n^2 = 2n^2 < n^4…
    \n\n\n\n\n\n
    n3<\/sup> – n \u221a\u00a0n\u00a0<\/span>
    \n<\/span><\/td>\n    		n!<\/td>\nlog2<\/sub>n<\/td>\n2n<\/sup><\/td>\n<\/tr>\n
    32n<\/sup><\/td>\nlog3<\/sub>n<\/td>\nn1.2<\/sup><\/td>\n32n-1<\/sup><\/td>\n<\/tr>\n
    1.51.5n<\/sup><\/sup><\/td>\n\u221a\u00a0n\u00a0<\/span>
    \n<\/span><\/td>\n    		3n<\/sup><\/td>\nn3<\/sup> + log n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/li>\n
  2. An undirected graph is connected<\/i> if for every two nodes N1<\/i> and N2<\/i>, there is a path from N1<\/i> to N2<\/i> in the graph. Describe a simple algorithm to determine if a given graph is connected. What is the running time of your algorithm?<\/li>\n
  3. Suppose you begin with a pile of n<\/tt> stones, and split this pile into n<\/tt> piles of one stone each by successively splitting a pile of stones into two smaller piles. Each time you split a pile you multiply the number of stones in each of the two smaller piles you form, so that if these piles have r<\/tt> and s<\/tt> stones in them, respectively, you compute rs<\/tt>. Show that no matter how you split the pile, the sum of the products computed at each step equals n(n-1)\/2<\/tt>. Here is an example that shows how the computation proceeds:
    \n

    <\/p><\/blockquote>\n

    The sum is 21+2+12+1+3+2+2+1+1 = 45, which is indeed 10 * 9 \/ 2.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Rank the following functions by order of growth. That is, order them so that f1 \u2208 O(f2), f2 \u2208 O(f3), etc. Make sure to indicate whether or not fi \u2208 \u0398(fi+1). For instance you could use the notation n < n^2 = 2n^2 < n^4… n3 – n \u221a\u00a0n\u00a0 n! log2n 2n 32n log3n n1.2 … <\/p>\n

    Continue reading “Sample problems for tutorial week #1”<\/span><\/a><\/p>\n","protected":false},"author":55633,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2232","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2232","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/users\/55633"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/comments?post=2232"}],"version-history":[{"count":5,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2232\/revisions"}],"predecessor-version":[{"id":2305,"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/pages\/2232\/revisions\/2305"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/wp-json\/wp\/v2\/media?parent=2232"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}