Notes for CMPT 225 Fall 2018

The following are notes for CMPT 225 Fall 2018. They are undergoing revisions and so may change during the course.

The course marking scheme, quizzes, due dates, etc. are on Canvas.

Assignments

Late assignments will be handled using “late time” as described in Canvas.

Final Exam

Please see Canvas for the date and time of the final exam.

The final exam is 3 hours and covers the entire course, but nothing about graphs (the topic of the last week of the course). See Lecture Notes for details. The final exam is similar in style to the midterm, but about twice as long.

It is a closed book exam: no notes, books, computers, calculators, phones, etc. are permitted.

Do not bring valuables to the exam! You will be asked to but jackets, backpacks, computers, etc. at the front of the room out of your reach.

You may bring your cell phone to the exam, but you cannot use it or leave the room with it. If you do need to leave the room (e.g. to use the washroom), you may be asked to hand over your phone to a TA/instructor.

See the grading FAQ for information about how final grades are calculated.

Some more specific study advice:

  • Any type of question could appear on the exam. For example, you could be asked to write code (both C++ and pseudocode), give definitions, write proofs (e.g. for O-notation), etc.
  • Don’t worry about the STL-style implementations give in the textbook. You only need to know about the basic class-based implementations as done in lectures and assignments.
  • Make a list of all the data structures discussed in the course. Explain how they work, and what operations are typically done on them. Use O-notation to describe their performance.
  • Be able to “run” the algorithms discussed in the course “by hand” with specific examples.
  • Make a list of all the important definitions. For example, AVL trees are an important data structure in this course because they are the main height-balanced binary search tree. So know all about those.
  • The textbook has lots of sample problems, and a good way to study would be to try to solve as many of those problems as you can. The topics of this course are quite standard and popular, so it’s not hard to find lots of examples and problems online.

Midterm Exam

The midterm is 50 minutes long, and will be written in the same lecture room at the usual time. See Canvas for the exact time/date.

It is a closed book exam: no notes, books, computers, calculators, phones, etc. are permitted.

Do not bring valuables to the exam! You will be asked to but jackets, backpacks, computers, etc. at the front of the room out of your reach.

There’s no time for bathroom breaks! This is only a 50 minute exam, and so we expect you to sit in the room for the entire time you are writing the exam. Once you leave the room, your exam is over.

See Lecture Notes for the exact topics the midterm will cover.

Any type of question could appear on the exam. For example, you could be asked to write code (C++-like pseudocode is fine), give definitions, write proofs (e.g. for O-notation), etc.

Here are some midterm questions (solutions).

Note that the textbook has many questions at the end of each chapter that you can use to help prepare.

Some other details:

  • you only need to know about O-notation as discussed in the lectures; you don’t need to know anything about big-theta and big-omega notation

Software

Lecture Notes

The course textbook is Data Structures & Algorithms, 2nd edition, by Goodrich, Tamassia, and Mount.

Week 1

  • For a review of C++, see chapter 1 of the textbook (we will not use much from chapter 2). In particular, focus on classes and pointers and make sure you know how to use the course makefile and cmpt_error.h with g++ on Ubuntu.
  • intvec.cpp contains the code for the dynamic vector-like class shown in Friday’s lecture.

Week 2

  • Chapter 3 (Arrays, Linked Lists, Recursion) of the textbook:
    • arrays: inserting and removing items; basic sorting (e.g. insertion sort)
    • singly-linked lists: list.cpp (non-OOP, singly-linked), list_class.cpp (OOP, singly-linked)
    • recursion
      • how it is typically implemented in programming languages (i.e. call stack)
      • tracing recursive functions: cmpt_trace.h
      • linear recursion (only one recursive call), e.g. summing/reversing elements of an array/list
      • binary recursion (two recursive calls), e.g. recursively generating Fibonacci numbers
      • recursion examples: recursion.cpp (uses cmpt_trace.h)
    • you should essentially know everything in chapter 3 (hopefully much is review), however we are not focusing on the use of the STL or generics (i.e. C++ templates)

Week 3

  • variations of singly-linked lists; doubly-linked lists (doubly_linked.cpp)
  • a very fast recursive version of the Fibonacci function that uses a cache to avoid re-computing values: fib_cached.cpp
  • code for the integer power calculations intpow.cpp
  • code for the max of a vector<int> max.cpp
  • Chapter 4 (Analysis Tools) of the textbook:
    • the 7 basic functions used in the book
    • basic ideas of algorithm analysis, e.g. counting primitive operations
    • definition of big-O for big-O notation; use this definition to prove basic facts about big-O notation (e.g. examples 4.10 - 4.14 on p. 169)

Week 4

  • Chapter 4 (Analysis Tools) of the textbook:
    • definition of big-O for big-O notation; use this definition to prove basic facts about big-O notation (e.g. examples 4.10 - 4.14 on p. 169)
  • Chapter 5 (Stacks, Queues, and Deques) of the textbook:
    • Abstract data type: see definition on p. 68 of the textbook
    • stacks, queues, and deques
      • code for int stacks stack_adt.cpp
      • code for generic stacks that store any type T stack_adt_generic.cpp
      • code for generic queues that store any type T queue_adt_generic.cpp (includes a version of the Circular_list class from the textbook)
      • The code examples here (and in the lectures) are slightly different, and slightly simpler, than most of the code in the textbook. Please follow this coding style for assignments and exams.
      • You won’t be asked any questions about templates on exams. Possibly, exams might show you code that uses templates, but there will be nothing more complicated then what’s in stack_adt_generic.cpp and the purpose of the question won’t be to understand the details of templates.

Week 5

  • Chapter 7 (Trees) of the textbook:
    • Basic tree definitions and properties (7.1.1 - 7.1.2)
    • Tree traversal algorithms (7.2)
    • The sections of chapter 7 not mentioned above are not ones we directly covered in the lectures and are topics you don’t need to know about in detail.

Week 6

  • Chapter 7 (Trees) of the textbook:
    • Basic tree definitions and properties (7.1.1 - 7.1.2)
    • Tree traversal algorithms (7.2)
    • Binary trees (7.3.1, 7.3.3, 7.3.4, 7.3.6)
    • The sections of chapter 7 not mentioned above are not ones we directly covered in the lectures and are topics you don’t need to know about in detail.
  • Chapter 10: definition of a Binary search trees (BST)

The Midterm Exam covers everything before this point.

Week 7

  • Binary search trees (BSTs): 10.1 of the textbook
  • midterm!

Week 8

  • AVL trees: 10.2 of the textbook
    • know the height-balance property, and understand the proof of why an AVL tree has height O(log n)
    • you should know AVL tree search and insertion in detail, i.e. be able to it by hand
    • there are help AVL tree animations on-line, you might want to look at, e.g. this one is good
  • The rest of chapter 10 covers splay trees, (2,4)-trees, and red-black trees
    • You should have a basic idea of what these other trees are about, and why they are interesting or useful.
    • You do not need to know them in the same amount of depth as AVL trees.

Week 9

  • Priority queues and heaps: chp. 8 of the textbook
    • know the priority queue ADT
    • know how to implement a priority queue using an ordered or unordered array/vector
    • know how to sort with a priority queue (selection sort and insertion sort)
    • define a heap
    • know the height of a heap and how to prove it
    • be able to implement insert(key), min(), and removeMin() and justify their running-times in O-notation
    • explain how heapsort works, and why it does O(n log n) comparisons in the worst case
    • you don’t need to know about bottom-up heap construction, or adaptable priority queues (section 8.4)
  • Notes on treaps: treaps1, treaps2, treaps3, treaps4

Week 10

Week 11

Week 12

  • Hashing (chapter 9)
    • Map ADT (9.1.1, 9.1.4)
    • hash tables (9.2)
  • sample C++ implementation of a linear probing hash table: hashing.cpp

Week 12

  • Graphs (chapter 13): basis definitions and facts, basic representations (adjacency list/matrix), Dijkstra’s algorithm
  • the final exam will not ask any questions about graphs