{"id":12,"date":"2014-12-30T17:39:10","date_gmt":"2014-12-31T00:39:10","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?page_id=12"},"modified":"2014-12-30T17:39:10","modified_gmt":"2014-12-31T00:39:10","slug":"syllabus","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202016w1\/syllabus\/","title":{"rendered":"Syllabus"},"content":{"rendered":"

<\/a><\/p>\n

Introduction<\/h2>\n

This course is about several broad categories of problems and problem-solving techniques (such as greedy algorithms, divide-and-conquer algorithms, dynamic programming, and the class of NP-complete problems) and gaining the tools and experience necessary to judge how a new problem might fit one of these categories, how to approach solving the problem, and how to analyze and adjust your solution.<\/p>\n

At the end of the course, you will be able to:<\/p>\n

    \n
  1. Recognize which algorithm design technique(s), such as divide and conquer, prune and search, greedy strategies, or dynamic programming was used in a given algorithm.<\/li>\n
  2. Select and judge several promising paradigms and\/or data structures (possibly slightly modified) for a given problem by analyzing the problem’s properties.<\/li>\n
  3. Implement a solution to a problem using a specified algorithm design paradigm, given sufficient information about the form of that problem’s solution.<\/li>\n
  4. Select, judge and apply promising mathematical techniques (such as asymptotic notations, recurrence relations, amortized analysis and decision trees) to establish reasonably tight upper and lower bounds on the running time of algorithms.<\/li>\n
  5. Recognize similarities between a new problem and some of the problems they have encountered, and judge whether or not these similarities can be leveraged towards designing an algorithm for the new problem.<\/li>\n<\/ol>\n

    You can also see a more detailed list of topic-level learning goals<\/a>, although we will\u00a0alter the specific topics used to address the course-level learning goals.<\/p>\n

    <\/a><\/p>\n

    Prerequisites and Calendar Description<\/h2>\n

    Available in the CPSC 320 UBC Calendar Entry<\/a>.<\/p>\n

    Beyond these, brush up on probability and combinatorics (e.g., at least the intro to the Wikipedia article on combinations<\/a>). You should also be comfortable reasoning using mathematical notation. You will need familiarity with summations, sets, relations, functions, asymptotic notation (O, \u03a9, \u0398), recursion, loop invariants, basic data structures (stacks, queues, linked lists, heaps, graphs, hash tables), sorting algorithms, and graph traversal (depth-first and breadth-first search).<\/p>\n

    <\/a><\/p>\n

    Tutorials<\/h2>\n

    Tutorials begin on Monday 12 September.<\/strong><\/p>\n

    Tutorials roughly alternate between review periods (review of\u00a0the previous week and practice for the next) and quizzes. The quizzes are “low-stakes” in that your quiz grade will be a small fraction of your grade on a follow-up assignment. (So, you could<\/strong> skip tutorial at the expense of\u00a0a small amount of credit. Unless you anticipate the course is\u00a0easy<\/strong>, you should attend! If you do think it’s easy, be sure you understand\u00a0the Dunning\u2013Kruger effect<\/a>.)<\/p>\n

    <\/a><\/p>\n

    Evaluation<\/h2>\n

    Your course mark will be based roughly on the following breakdown. The instructor reserves the right to change this scheme (but does not anticipate using that right).<\/p>\n\n\n\n\n\n\n\n
    Assignments\/Quizzes (5-8)<\/td>\n25%<\/td>\n<\/tr>\n
    Midterm Exam<\/td>\n25%<\/td>\n<\/tr>\n
    Final Exam<\/td>\n45%<\/td>\n<\/tr>\n
    Pre-Class Preparation\u00a0Work<\/td>\n1%<\/td>\n<\/tr>\n
    Best of the 4 previous parts<\/td>\n4%<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    To pass the course, you must obtain a 50% overall mark and, in addition, achieve a passing grade on your overall exam mark (the weighted average of midterm and final exams). Students who fail the overall exam mark will receive as their course grade the minimum of their normally computed grade and 45%.<\/p>\n

    We use\u00a0the “10% rule” for\u00a0midterms: If your final exam mark is more than 10% points above\u00a0your midterm exam mark, we replace the midterm mark with the\u00a0final mark minus 10% points. So,\u00a0if your final exam mark is f<\/code> (a natural but mildly ominous-sounding letter), then the\u00a0midterm mark m<\/code> is: max(m, f-10)<\/code>.<\/p>\n

    All assignments\/quizzes contribute equal weight toward the assignment\/quiz average; however, your lowest assignment\/quiz mark will be dropped.<\/p>\n

    Pre-class preparation work will be collected either online at noon on the day of lectures with assigned work (with submission\u00a0links e-mailed to your @ugrad.cs.ubc.ca address) and be worth 2 points each. If p<\/code>\u00a0is the total number of assigned\u00a0prep missions (because “mission” sounds awesome, and p<\/code>\u00a0is a less ominous letter)\u00a0over the term and you earn y<\/code>\u00a0points total, then your pre-class prep\u00a0grade will be min(100, 100*y\/(0.75*2*p))<\/code>. In other words, you only need the equivalent of full marks on\u00a075% of these\u00a0to earn 100% on this component.\u00a0However,<\/strong> the hands-on nature of class time means I expect you to prepare for each class so you can learn and contribute!<\/p>\n

    Finally, whichever of your assignment\/quiz, midterm, final, and pre-class prep\u00a0averages is best will be worth an additional 4% of your course mark.<\/p>\n

    (Since the prep missions\u00a0should be relatively easy if you do the readings, you can earn a high mark on 5% of the course just by putting in organized effort. If, on the other hand, you want to skip all the lectures and manage on your own, you can do that instead and theoretically only lose 1%.. just please don’t land in the middle and regularly show up to lecture unprepared. Also, bear in mind that “In Theory, Theory and Practice are the same. In Practice, they differ.” Put another way: Skipping lectures is wonderful preparation for\u00a0failing the course.)<\/p>\n

    To have marking of any\u00a0assessment reviewed<\/strong> (except the final exam):<\/strong> staple a note detailing all of your objections to the assessment and submit this to your instructor no later than two weeks after the week the marked assessment\u00a0was returned (regardless of whether you collected your assessment\u00a0at that time). (For online returns like scanned exams, just submit a separate note, but include your ugrad login ID and student number.) The instructor will review the marking. The instructor’s review decision is final and may either increase or decrease the assigned mark based on your objections or other aspects of the submission. For the final exam, there will be a period to review the exam with the instructor to learn from it. For marking disputes, see UBC’s Review of Assigned Standing<\/a> policy.<\/p>\n

    <\/a><\/p>\n

    Important Dates<\/h2>\n\n\n\n\n\n\n\n\n
    Add\/Drop Deadline<\/i><\/td>\n20 September (Tuesday)<\/td>\n<\/tr>\n
    Thanksgiving<\/i><\/td>\n10 October (Monday)<\/td>\n<\/tr>\n
    Drop with W Deadline<\/i><\/td>\n14 October (Friday)<\/td>\n<\/tr>\n
    Midterm\u00a0Exam<\/i><\/td>\n20 October (Thursday)<\/td>\n<\/tr>\n
    Remembrance Day<\/i><\/td>\n11 November (Friday)<\/td>\n<\/tr>\n
    Final Exam<\/i><\/td>\nWe’ll know when you do! See UBC’s exam page<\/a>.<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/a><\/p>\n

    Rough Topic Schedule<\/h2>\n

    Here is a VERY rough schedule of topics and readings very much ubject to change<\/i>. We’ll post reading assignments on this blog as they come out.<\/p>\n