CPSC 221: Basic Algorithms and Data Structures
2016 Winter Term 1
Lab/Lecture Notes


Home Learning Goals Schedule Administration Readings Lab/Lecture Notes Assignments Computing

  • Handouts for the course as a whole
  • Lab handouts/materials
  • Sections 101 (Manuch) and 102 (Evans) handouts/materials
  • Old CPSC 221 lecture recordings -- optional and just for your reference, only accessible from ubcsecure wireless or a UBC VPN

    • (Assignments are available from the assignments page.)

    Handouts for Everyone!

    Here are some possibly-helpful notes:

    Lab Handouts

    Date Lab Resources
    Sep 12 - Sep 16 Lab 1: An Introduction to Programming and Compiling in C++
    Sept 19 - Sept 23 Lab 2: Debugging an Insertion Sort program, C++ pointers, and memory leaks
    • lab2.zip contains all the files you need for this lab
    • In the first part of the lab, you need to find the bugs and fix them. Only insertion.cc needs to be changed.
    • After doing the second part ("fill in the blanks") you can verify your answers using a program you can compile with "make pointers".
    • The third part uses "valgrind" to find memory leaks. For bonus marks you can fix the leaks.
    Sept 26 - Sept 30 Lab 3: C++ Class and Linked Lists
    • lab3.zip contains all the files you need for this lab. Updated Thursday Sept 22nd @10:30pm
    • First, you'll complete some function members of a simple C++ Class. (Read the "helpful links" to save yourself some time.)
    • Next you'll code three functions that manipulate Linked Lists.
    • The third part is optional, but recommended.
    Oct 3 - Oct 7 Lab 4: Heaps
    • binaryHeap.cpp is the only file you will need for this lab
    • NOTE: Monday and Tuesday AM labs will not have previous exposure to binary heaps. Your TA will do a quick overview of binary heaps during labs.
    • First, you will implement three functions operating on binary heaps.
    • Next, you'll analyze the asymptotic runtime of your solutions to two of these functions.
    • Check out your notes on binary heaps if you're stuck.
    Oct 10 - Oct 17 Lab 5: Binary Search Trees
    • lab5.zip contains all the files you need for this lab
    • Since Mon Oct. 10 is a holiday, Monday sections will do this next week (on Oct 17).
    • This week you'll be working with the Binary Search Tree data structure. You may find it useful to familiarize yourself with them before lab, so we've provided some links (in the lab handout) that should help you out.
    Oct. 24 - Oct. 28 Lab 6: Quicksort
    • qsortCount.cc is the C++ source that you'll use for this lab.
    • Click the Quick Sort button on this Visualizer for a demo.
    • Note that there are two optional questions at the end of the lab, worth no extra points.
    Oct. 31 - Nov. 4 Lab 7: Hashing
    • lab7.zip contains all the files you need for this lab
    • Linear, Quadratic and Double Hashing are demonstrated on this Hashing Visualizer.
    Nov. 7 - Nov. 11 Labs Cancelled for Remembrance Day Holiday
    • All labs are cancelled for this week. :'(
    • Your TAs may hold extra office hours during lab times. Check Piazza to see if and when extra office hour times are being held.
    Nov. 14 - Nov. 18 Lab 8: AVL Trees
    • lab8.zip contains all the files you need for this lab.
    • Try out this AVL tree Visualizer. Click the Options button to do the rotations manually, or go step by step.
    Nov. 21 - Nov. 25 Lab 9: Parallelism
    • lab9.zip contains all the files you need for this lab
    • Run your code on the ugrad servers so you don't have to copy the large sample text files.
    • This is the last lab assignment of the term, so labs in Nov. 28 - Dec. 2 are for marking lab 9 and then answering any questions you might have (about project 3, course material, life..)

    Section 102 (Evans, TTh 8-9.30) and 101 (Manuch, TTh 14-15.30) Handouts

    Date

    Topic

    Lecture Slides

    Extra material

    Readings (see the syllabus for a complete list)
    Original Will's annotated Jan's annotated
    Sep 8 Introduction, Arrays, Queues, Stacks 4up 1up annotated annotated fib.cpp Epp:
    Koffman: P) A C++ Primer, 1) Introduction to Software Design, 4.5-4.7) Linked Lists, 5) Stacks, 6) Queues
    Sep 17 Asymptotic Algorithm Analysis 4up 1up annotated annotated none Epp: 11.1-3) Asymptotic Notation
    Koffman: 2.6) Efficiency of Algorithms
    Oct 4 Priority Queues 4up 1up annotated annotated skiplist Epp: 10.6) Rooted Trees
    Koffman: 8.1) Trees, 8.5) Heaps and Priority Queues
    Oct 6 Recursion, Induction, and Loop Invariants 4up 1up annotated annotated none Epp: 5.2-5) Mathematical Induction and Loop Invariants
    Koffman: 2.5) Loop Invariants, 7) Recursion
    Oct 18 Sorting 4up 1up annotated annotated Best Case Heapsort Epp: 11.3-5) Application: Analysis of Algorithm Efficiency I & II
    Koffman: 10) Sorting
    Oct 25 Hashing and Pigeonhole Principle 4up 1up annotated annotated none Epp: pg.401) Hash Functions, 9.4) Pigeonhole Principle
    Koffman: 9) Sets and Maps
    Nov 5 AVL Trees 4up 1up annotated annotated Avg Cost to Create BST Epp: 10.6) Rooted Trees
    Koffman: 8.1-4) Binary Search Trees, 11.1) Tree Balance and Rotation, 11.2) AVL Trees
    Nov 8 B+-Trees 4up 1up annotated annotated BST Remove annotatedWill annotatedJan Epp:
    Koffman: 11.4-5) 2-3, 2-3-4, and B-Trees
    Nov 15 Parallelism 4up 1up annotated annotated Parallelism and Concurrency Notes Epp:
    Koffman:
    Nov 24 Graphs 4up 1up annotated annotated Kruskal "proofs" Epp: 10) Graphs and Trees
    Koffman: 12) Graphs
    Dec 12 Review 1up

     

    cs221@ugrad.cs.ubc.ca
    Last Modified: Tue 4 Oct, 2016