CPSC 221: Basic Algorithms and Data Structures
2016 Winter Term 2 (January-April 2017)
Lab/Lecture Notes


Home Learning Goals Schedule Administration Readings Lab/Lecture Notes Assignments (Theory/Programming) Computing

Short-cut links on this page (no effect with a short, Web page size):

  • Some Handouts for Reference
  • Lab Handouts/Materials See also the supplementary lecture slides for the Jan. 4-16 unit below. They're in the column entitled "Extra Material" and look for the "Pointers" PDF files.
  • Lecture Section Handouts - Sections 201 (Ed), 202 (Anthony), and 203 (Mehrdad)
    •  Assignments will be posted on the assignments page.

    Some Handouts for Reference

    Here are some possibly helpful notes:

    Lab Handouts/Materials


    Dates Lab Resources
    Jan. 9-13 Lab 1: An Introduction to Programming and Compiling in C++
    Jan. 16-20 Lab 2: Debugging an Insertion Sort Program, C++ Pointers, and Memory Leaks
    • lab2.zip contains all the files you need for this lab.
    • Note that there is a set of Pointer notes in the "Extra Material" column of the lecture slides; they may be helpful. We went over these in class.
    • 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.
    • We strongly recommend that you learn to use a debugger for this lab, even if you think you can find the errors without a debugger. Being able to use a debugger is a valuable skill.
    Jan. 23-27 Lab 3: C++ Classes and Linked Lists
    • lab3.zip contains all the files you need for this lab.
    • patch.zip contains an optional patch to improve the tests for part 2. (Note that this is extra material for those students who are interested in exploring more of C++. It is not needed for the labs/projects.)
    • In Lab 3, 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.
    • Finally, the last part is optional, but recommended.
    Jan. 30-Feb. 3 Lab 4: Heaps
    • binaryHeap.cpp is the only file you will need for this lab.
    • Heaps are linked structures with two pointers: one for the left child, and one for the right child.
    • 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.
    • Your textbook (Koffman/Wolfgang) has a lot of material on trees and heaps in Chapter 8. Please make use of it, especially if you haven't seen trees or heaps before. Your TAs will do a quick overview of binary heaps during labs, but it would help to do some pre-reading.
    • Here is a very brief introduction to binary trees and binary heaps which we covered in the lectures on Friday, Jan. 27 (Ed, Anthony) and Monday, Jan. 30 (Mehrdad): binary_trees_heaps_brief_intro_4up.pdf
      • or binary_trees_heaps_brief_intro_1up.pdf.
    Feb. 6-10 Lab 5: Binary Search Trees
    • lab5.zip contains all the files you need for this lab.
    • This week you'll be working with the Binary Search Tree data structure. You may find it useful to familiarize yourself with them before the lab, so we've provided some links (in the lab handout) that should help you out.
    Tues., Feb. 14 to Mon., Feb. 27 Lab 6: Quicksort
    • Since Mon., Feb. 13 is a holiday (BC Family Day), and since Mon., Feb. 20 to Fri., Feb. 24 is the Winter mid-term break ("Reading Week"), the Monday lab sections will do Lab 6 on Feb. 27. The Tuesday-Friday labs from Feb. 28 to Mar. 3 will NOT meet. Note that the midterm is on Wed., Mar. 1 at 17:00 for all lecture sections.
    • 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.
    Tues., Feb. 28 to Thurs., Mar. 9 No Labs
    • There are no labs on Tuesday, February 28 to Thursday, March 9, inclusive. Note that labs resume on Friday, March 10. (Classes end on the first Thursday in April.)
    Fri., Mar. 10 to Thurs., Mar. 16 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.
    Fri., Mar. 17 to Thurs., Mar. 23 Lab 8: AVL Trees
    • lab8.zip contains all the files you need for this lab.
    • You can preview the lecture slides for the AVL unit (being released by Thursday, March 16th) if you haven't been introduced to AVL trees in your lecture section yet. (See also the Koffman textbook (pp. 628-643) for more material.)
    • Also, try out this AVL tree Visualizer. Click the Options button to do the rotations manually, or go step by step.
    Fri., Mar. 24 to Thurs., Mar. 30 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 during Mar. 31 to Apr. 6 are for marking Lab 9 and then answering any questions you might have about course material.

    Lecture Section Handouts - Sections 201 (Ed), 202 (Anthony), and 203 (Mehrdad)

    We will post our annotated slides after a unit has ended, but not after each class. We will bring the first n pages of slides to Lecture #1; so, you won't have to download or print anything for Day 1. Thereafter, you should download or print the "Original" lecture slides. The instructors will work from the same set, with minor variations. Note, however, that explanations, examples, or supplementary material that is written on the whiteboard or the document camera -- or is in response to a student question during the lecture -- may not appear in the annotated notes.

    <--

    Date

    Topic

    Lecture Slides (original plus instructor annotated)

    Extra Material

    Readings (see the syllabus for a complete list)
    2017 Original Ed Anthony Mehrdad
    Jan 4-16 Introduction, Arrays, Queues, Stacks 4up 1up annotated lectures

    annotated pointers

    		annotated pointers TBA fib.cpp

    Pointers 1up

    Pointers 4up

    		Epp: n/a
    Koffman:
    Chapter P: C++ Primer
    Chapter 1: Intro. to Software Design
    Chapter 4.5-4.7: Linked Lists
    Chapter 5: Stacks
    Chapter 6: Queues
    Jan 18-Feb 1 Asymptotic Algorithm Analysis 4up 1up annotated lectures annotated lectures annotated lectures (UPDATED) fib.cpp

    Heaps 1up

    Heaps 4up

    Epp:
    Chapter 11.1-11.3: Asymptotic Notation
    (In the 3rd edition, it's Chapter 9.1-9.3.)
    Koffman:
    Chapter 2.6: Efficiency of Algorithms
    Feb 3-10 Priority Queues 4up 1up annotated lectures annotated lectures annotated lectures n/a Epp:
    Chapter 10.6: Rooted Trees
    Koffman:
    Chapter 8.1: Trees
    Chapter 8.5: Heaps and Priority Queues
    Feb 10-Mar 3 Recursion, Induction, and Loop Invariants 4up 1up annotated lectures annotated lectures annotated lectures (pre-midterm) n/a Epp:
    Chapter 5.2-5.5: Mathematical Induction and Loop Invariants
    Koffman:
    Chapter 2.5: Loop Invariants
    Chapter 7: Recursion
    Mar 3-20 Sorting 4up 1up annotated lectures annotated lectures TBA Best Case Heapsort Epp:
    Chapter 11.3-11.5:
    Application: Analysis of
    Algorithm Efficiency, Parts I & II;
    Exponential and Logarithmic
    Functions: Graphs and Orders

    Koffman:
    Chapter 10: Sorting
    Mar. 10-20 Hashing and Pigeonhole Principle 4up 1up annotated lectures annotated lectures TBA none Epp:
    Example 7.2.3 on Page 401
    and Chapter 9.4:
    The Pigeonhole Principle

    Koffman:
    Chapter 9: Sets and Maps
    Mar. 17-22 AVL Trees 4up 1up annotated lectures annotated lectures TBA Avg Cost to Create BST Epp:
    Chapter 10.6: Rooted Trees

    Koffman:
    Chapter 8.1-8.4: BSTs
    Chapter 11.1: Tree Balance and Rotation
    Chapter 11.2: AVL Trees

    Mar 22-27 Parallelism 4up 1up annotated lectures annotated lectures TBA Parallelism and Concurrency Notes Epp: n/a

    Koffman: n/a

    Mar 27-31 B+-Trees 4up 1up annotated lectures annotated lectures TBA Epp: n/a

    Koffman:
    Sections 11.4-11.5:
    2-3, 2-3-4, and B-Trees

    Mar. 31 - Apr. 6 Graphs 4up 1up annotated lectures annotated lectures TBA Kruskal "proofs" (FYI) Epp:
    Chapter 10: Graphs and Trees

    Koffman:
    Chapter 12: Graphs

     

    Last Modified: April 6, 2017