Lectures, Labs, and Course Outline

For every week this term, you can find below readings to help you prepare for that week's lectures, a summary of lecture material (posted at the end of the week), and lab exercises that you should be able to solve easily given that week's readings and lecture material. Think of the lab exercise as an "early warning system": if you have any difficulty solving it, then this is a strong indication that you need to review the lecture material and ask questions. You can find more information about the lab format further below on this page.

Week Readings Lectures Labs
1. (Jan 7–Jan 11) Topics: introduction and administration, Abstract Data Types, Python classes and objects
Readings:
NO labs this week
Slides from ramp-up session (from last fall, same content as this term)
2. (Jan 14–Jan 18) Topics: stacks and queues, Python exceptions
Readings:
  • Stacks in How to Think Like a Computer Scientist
  • Exceptions in How to Think Like a Computer Scientist
Lab 1 handout
files: specs.txt sample1.txt sample2.txt
3. (Jan 21–Jan 25) Topics: inheritance, testing and test-driven development, unittest
Readings:
  • Inheritance in How to Think Like a Computer Scientist
Lab 2 handout
files: testqueue.py timestack.py timequeue.py
4. (Jan 28–Feb 1) Topics: recursion, linked lists
Readings:
  • Recursion in How to Think Like a Computer Scientist
  • Linked Lists in How to Think Like a Computer Scientist
Lab 3 handout
5. (Feb 4–Feb 8) Topics: linked lists
Readings:
  • Re-read Linked Lists in How to Think Like a Computer Scientist
Lab 4 handout
6. (Feb 11–Feb 15) Topics: memory model, trees, binary trees, tree traversals
Readings:
  • Trees in How to Think Like a Computer Scientist
Lab 5 handout
(Feb 18–Feb 22) Reading Week No Lectures No Labs
7. (Feb 25–Mar 1) Topics: Binary Search Trees
Readings:
  • Trees in How to Think Like a Computer Scientist
  • Binary Search Trees on Wikipedia (You can safely ignore the sections "Sort" and "Types", and I will cover simplified versions of the code for each operations.)
Lab 6 handout
files: client.py
8. (Mar 4–Mar 8) Topics: BST search and insert, BST remove
Readings:
  • Binary Search Trees on Wikipedia (You can safely ignore the sections "Sort" and "Types", and I will cover simplified versions of the code for each operations.)
Lab 7 handout
files: BST.py, BST_rec1.py, BST_rec2.py, BST_rec3.py, BST_iter.py
9. (Mar 11–Mar 15) Topics: BST remove (continued)
Readings:
  • Binary Search Trees on Wikipedia (You can safely ignore the sections "Sort" and "Types", and I will cover simplified versions of the code for each operations.)
Lab 8 handout
10. (Mar 18–Mar 22) Topics: performance of BSTs, priority queues and heaps
Readings:
Lab 9 handout
Files: chart.xls, search.py, test_search.py, sort.py, test_sort.py
11. (Mar 25–Mar 28) Topics: heaps (continued), sorting: heapify, heap-sort
Readings:
Lab 10 handout
12. (Apr 1–Apr 5) Topics: selection-sort, insertion-sort, quick-sort, merge-sort, Python profiling, review
Readings:
Lab 11 handout
Review See the Tests/Exam page for advice about studying for and writing the final exam.

Lab format

You can earn 1 mark for each lab you attend. To earn your lab mark, you must actively participate in the lab.
We mark you in order to ensure a serious attempt at learning, NOT to make careful critical judgments on the results of your work.

You may be tempted to do the lab work before your actual lab. (Labs will usually be posted on Mondays.) We really, really don't want you to do this, for a number of good pedagogical reasons: