{"id":31,"date":"2019-04-26T14:30:15","date_gmt":"2019-04-26T21:30:15","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/?page_id=31"},"modified":"2019-08-10T06:55:32","modified_gmt":"2019-08-10T13:55:32","slug":"worksheets","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/content\/worksheets\/","title":{"rendered":"Worksheets"},"content":{"rendered":"<h5>Lecture worksheets:<\/h5>\n<ul>\n<li>Stable marriage problem: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/06\/smp-intro.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/smp-intro-soln.pdf\">sample solution<\/a>\n<ul>\n<li>Handouts: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/06\/unit1-how-to-solve-320-problems.pdf\">How to Solve a 320 Problem<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/06\/gale-shapley.pdf\">The Gale-Shapley Algorithm<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Resident hospital problem: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/smp-reductions.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/smp-reductions-soln.pdf\">sample solution<\/a><\/li>\n<li>Asymptotic analysis review: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/unit3-asymptotic-analysis-review.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/unit3-asymptotic-analysis-review-soln.pdf\">sample solution<\/a>\n<ul>\n<li>Handout: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/little-o-overview.pdf\">Little-o Overview<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Graphs: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/unit4-graph-play-notes.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/unit4-graph-play-notes-soln.pdf\">sample solution<\/a><\/li>\n<li>Clustering: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/clustering.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/clustering-sol.pdf\">sample solution<\/a><\/li>\n<li>Clustering proof of correctness: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/clustering-completed.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/clustering-completed-sol.pdf\">sample solution<\/a><\/li>\n<li>Divide and conquer (QuickSelect): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/div-and-conq-qselect.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/div-and-conq-qselect-sample-soln.pdf\">sample solution<\/a>\n<ul>\n<li>Handout: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/master-theorem.pdf\">The Master Theorem<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Dynamic programming in 1D (change-making), part 1: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp1.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp1-sample-soln.pdf\">sample solution<\/a><\/li>\n<li>Dynamic programming in 1D (change-making), part 2: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp2.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp2-sample-soln.pdf\">sample solution<\/a><\/li>\n<li>Dynamic programming in 2D: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp-lcs.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/dp-lcs-soln.pdf\">sample solution<\/a><\/li>\n<li>Reductions: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/reductions.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/reductions-sol.pdf\">sample solution<\/a>\n<ul>\n<li>Handout: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/np-completeness-summary.pdf\">Quick Notes on NP-completeness<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Steiner Problem intro: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner1.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner1-sol.pdf\">sample solution<\/a><\/li>\n<li>Steiner Problem reduction: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner2.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner2-sol.pdf\">sample solution<\/a><\/li>\n<li>Steiner Problem, proof of reduction correctness: <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner3.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/steiner3-sol.pdf\">sample solution<\/a><\/li>\n<\/ul>\n<h5>Tutorial worksheets:<\/h5>\n<ul>\n<li>Proof techniques review (week 1): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/proof_techniques_review.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/proof_techniques_review_soln.pdf\">sample solution<\/a><\/li>\n<li>Combinatorics review (week 1): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/combinatorics_review.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/combinatorics_review_soln.pdf\">sample solution<\/a><\/li>\n<li>Pseudocode guide (week 2): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/pseudocode_guide.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/pseudocode_guide_sol.pdf\">sample solution<\/a><\/li>\n<li>Proof questions from exams (week 3): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/320-exam-proofs.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/320-exam-proofs-soln.pdf\">sample solution<\/a><\/li>\n<li>NP-completeness (week 5): <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/2019_S2_NP_Completeness.pdf\">worksheet<\/a> and <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/files\/2019\/07\/2019_S2_NP_Completeness_Sample_Solution.pdf\">sample solution<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Lecture worksheets: Stable marriage problem: worksheet and sample solution Handouts: How to Solve a 320 Problem and The Gale-Shapley Algorithm Resident hospital problem: worksheet and sample solution Asymptotic analysis review: worksheet and sample solution Handout: Little-o Overview Graphs: worksheet and &hellip; <a href=\"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/content\/worksheets\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":43098,"featured_media":0,"parent":27,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-31","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/pages\/31","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/users\/43098"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/comments?post=31"}],"version-history":[{"count":24,"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/pages\/31\/revisions"}],"predecessor-version":[{"id":484,"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/pages\/31\/revisions\/484"}],"up":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/pages\/27"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/cpsc3202019s2\/wp-json\/wp\/v2\/media?parent=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}