{"id":12,"date":"2014-12-30T17:39:10","date_gmt":"2014-12-31T01:39:10","guid":{"rendered":"https:\/\/blogs.ubc.ca\/cpsc320\/?page_id=12"},"modified":"2018-04-20T16:13:34","modified_gmt":"2018-04-20T23:13:34","slug":"syllabus","status":"publish","type":"page","link":"https:\/\/blogs.ubc.ca\/cpsc3202017winter2\/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 Wednesday 3 January.<\/strong><\/p>\n

    Tutorials roughly alternate between TA-facilitated sessions (often preparation for assignments\/exams, supplementary material, or review of previous courses) and tutorial quizzes. Tutorial quizzes are low-stakes (see the grading scheme below) opportunities for timed, exam-like questions. They also set the stage for the assignment that follows them. (If you think the course is easy<\/strong>,\u00a0you could<\/strong> skip tutorial at the expense of\u00a0a small amount of credit. However, if you do think the course is easy, be aware that you may be misjudging your abilities as a new learner. See the fascinating Dunning\u2013Kruger effect<\/a>.)<\/p>\n

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

    Evaluation<\/h2>\n

    Your course mark will be based on the following breakdown. The course staff\u00a0reserves the right to change this scheme (but does not anticipate using that right).<\/p>\n\n\n\n\n\n\n\n\n
    Assignments (~5)<\/td>\n23%<\/td>\n<\/tr>\n
    Midterm Exams (2)<\/td>\n30%<\/td>\n<\/tr>\n
    Final Exam<\/td>\n40%<\/td>\n<\/tr>\n
    Tutorial Quizzes<\/td>\n2%<\/td>\n<\/tr>\n
    Pre-Class Quizzes<\/td>\n2%<\/td>\n<\/tr>\n
    Best of the 5 previous parts<\/td>\n3%<\/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 individual exam mark (the average of the individual components of your midterm and final exams, weighted according to the table above). 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

    Each assignment, each tutorial quiz, and each pre-class quiz contributes equal weight toward their respective averages. However, your lowest assignment and lowest tutorial quiz mark will be dropped.<\/p>\n

    Pre-class quizzes\u00a0will be due online roughly weekly and be scaled to 2 points each, where your grade will be rounded up to the next integer. (So, a 30% on a quiz would earn 1\/2, and a 68% on a quiz would earn 2\/2) If p<\/code>\u00a0is the total number of pre-class quizzes\u00a0and you earn y<\/code>\u00a0points total, then your pre-class quiz grade will be min(100, 100*y\/(0.8*2*p))<\/code>. In other words, you only need the equivalent of full marks on 80% of these\u00a0to earn 100% on this component.\u00a0However,<\/strong> the hands-on nature of class time means we\u00a0expect you to prepare for each class so you can learn and contribute!<\/p>\n

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

    (Since the pre-class quizzes are\u00a0relatively easy if you do the readings, you can likely earn a perfect mark on 5% of the course just by putting in organized effort. If\u00a0instead you want to skip the lectures and manage on your own, you can do that and theoretically<\/strong> only lose 2%.. 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 pre-class quizzes and the final exam):<\/strong>\u00a0use GradeScope’s regrade request interface no later than two weeks after the week the marked assessment\u00a0was returned (regardless of whether you collected your assessment\u00a0at that time). The course staff will review the marking. Our review decision is final and may either increase or decrease the assigned mark based on your objections or other aspects of the submission.<\/p>\n

    For pre-class quizzes, send a note by e-mail or private Piazza post to your course instructor. Be sure to include the name of the assessment (e.g., “Pre-Class Quiz #3”), your full name, your ugrad login ID, your student number, and all<\/strong> grading concerns, including your justification for why you should have received a different grade.<\/p>\n

    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\n\n\n\n
    First Day of Classes for CPSC 320<\/i><\/td>\n3 January (Wednesday)<\/td>\n<\/tr>\n
    Add\/Drop Deadline<\/i><\/td>\n17 January (Wednesday)<\/td>\n<\/tr>\n
    Midterm\u00a0Exam #1<\/i><\/td>\n6 February (Tuesday)<\/td>\n<\/tr>\n
    Drop with W Deadline<\/i><\/td>\n9 February (Friday)<\/td>\n<\/tr>\n
    Family Day<\/i><\/td>\n12 February (Monday)<\/td>\n<\/tr>\n
    Mid-Term Break<\/i><\/td>\n19\u201323 February<\/td>\n<\/tr>\n
    Midterm\u00a0Exam #2<\/i><\/td>\n13 March (Tuesday)<\/td>\n<\/tr>\n
    Good Friday\/Easter Monday<\/i><\/td>\n30 March\/2 April<\/td>\n<\/tr>\n
    Last Day of Classes<\/i><\/td>\n6 April (Friday)<\/td>\n<\/tr>\n
    Final Exam<\/i><\/td>\nWe’ll know when you do, but between 10 and 25 April<\/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 subject to change<\/i>. We’ll post reading assignments on this blog as they come out.<\/p>\n