COMP 2012H - Fall 2014

Fall 2014, COMP 2012H Honors Object-Oriented Programming and Data Structures [5 credits]
Lecture L1 (1728), TuTh 16:30-18:20, Rm 6602 (L31-32)
Prof. Dekai WU, Rm 3539, 2358-6989,

Lab LA1 (1730) TA: Karteek ADDANKI, Fr 14:30-16:20, Rm 4214 (L19),

You are welcome to knock on the door of the instructor any time. The TAs' office hours are posted at


Welcome to COMP2012H!

Always check the Discussion Forum for up-to-the-minute announcements.

Discussion forum is at Always read before asking/posting/emailing your question.
Course home page is at
Lab info is at


Welcome to Honors Object-Oriented Programming and Data Structures. COMP 2012H is designed to give you the solid software engineering experience necessary to build, extend, and maintain a realistically sized non-toy program, using both traditional and up-to-date techniques that you will need on the job. Most students find that C++ and other modern languages offer a huge, confusing variety of different and often-contradictory complexities. In this sequence you will untangle the confusion by gaining an enhanced holistic theoretical perspective, comparing and contrasting the most important paradigms of programming languages.

Understand by doing. The only way to learn languages is through serious practice. The only way to appreciate software engineering is to engineer some serious software. And by far the best way to understand programming languages is to implement one.

So, through an integrated series of programming assignments, you will use C++ to gradually implement your own complete interpreter for a real programming language that is a small but fully operational version of Scheme (or Lisp).

You will learn the most important procedural, static and dynamic object-oriented, and generic programming paradigms of C++ programming, through hands-on practice with building the basic pieces of your Scheme interpreter. The Scheme programming project will help deepen the C++ concepts you have learned, by giving you a better understanding of the functional and generic programming roots and foundations that underlie the design and effective use of STL in the C++ Standard Library. If we progress sufficiently rapidly, then we will also learn about the syntactic description and analysis of programming languages, and their runtime environments. Throughout the entire series, you will focus on developing adequate software engineering habits, so that you can continue to build, extend, and maintain the code you have built so far.

Academic Calendar Description

[Previous Course Code(s): COMP 152H] This course is an accelerated and intensive course on concepts and techniques behind object-oriented programming (OOP) and data structures using an OOP language. It covers the major materials of COMP2011 and COMP2012, and its curriculum is designed for students with excellent programming background or substantial programming experience. Topics include: functions; pointers; abstract data types and their class implementation; static and dynamic construction and destruction of objects; data member and member functions; public interface and encapsulation; class hierarchies; polymorphism; inheritance and dynamic binding; standard template library; generic programming using templates; object-oriented view of data structures: linked lists, queues, stacks, trees, and their algorithms such as searching, sorting and hashing. Exclusion(s): COMP 1003, COMP 1004, COMP 2011, COMP 2012 Prerequisite(s): Grade A or above in COMP 1002 / COMP 1021 / COMP 1022P / COMP 1022Q

Course Outcomes

  1. Write object-oriented programs in C++ with object creation, destruction, member variables and functions, inheritance, polymorphisms, and templates.
  2. Analyze a program and provide simple solutions with OOP.
  3. Write basic algorithms associated with data structures such as stacks, queues, lists, trees, and hashes.
  4. Define binary tree and search tree and describe how they are used to solve problems.
  5. Develop a large program using separate compilation, good OOP design, and code reuse.


Reference Books


To receive a passing grade, you are required to sign an honor statement acknowledging that you understand and will uphold all policies on plagiarism and collaboration.


All materials submitted for grading must be your own work. You are advised against being involved in any form of copying (either copying other people's work or allowing others to copy yours). If you are found to be involved in an incident of plagiarism, you will receive a failing grade for the course and the incident will be reported for appropriate disciplinary actions.

University policy requires that students who cheat more than once be expelled. Please review the cheating topic from your UST Student Orientation.

Warning: sophisticated plagiarism detection systems are in operation!


You are encouraged to collaborate in study groups. However, you must write up solutions on your own. You must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism.


The course will be graded on a curve, but no matter what the curve is, I guarantee you the following.

If you achieve 85% you will receive at least a A grade.
75% B
65% C
55% D

Your grade will be determined by a combination of factors:

Midterm exam ~20%
Final exam ~25%
Participation ~5%
Homework ~40%
Labs ~10%


No reading material is allowed during the examinations. No make-ups will be given unless prior approval is granted by the instructor, or you are in unfavorable medical condition with physician's documentation on the day of the examination. In addition, being absent at the final examination results in automatic failure of the course according to university regulations, unless prior approval is obtained from the department head.

There will be one midterm worth approximately 20%, and one final exam worth approximately 25%.


Software engineering is about communication between people. Good participation in class and/or the online forum will count for approximately 5%.


All programming assignments must be submitted by 23:00 on the due date. C++ programming assignments must be compiled using g++ on Unix and will be collected electronically using the automated CASS assignment collection system. Late assignments cannot be accepted. Sorry, in the interest of fairness, exceptions cannot be made.

Programming assignments will account for a total of approximately 40%.


All information for laboratory/tutorial assignments is at

Laboratory/tutorial assignments will be due Monday of the week after they are announced at 23:00. Laboratory/tutorial assignments must be in C++ on Unix and will be collected electronically using the automated CASS assignment collection system. Late assignments cannot be accepted. Sorry, in the interest of fairness, exceptions cannot be made.

You will also have the option to turn in your laboratory/tutorial assignments in lab by demonstrating to the TA. This will also give you an opportunity to get an early indication of whether your assignment is correct. If not, you may still decide to fix it, and then wait until the Monday 23:00 CASS collection to turn in your assignment.

There will be up to 10 laboratory/tutorial assignments, which in total will count for approximately 10%.


Date Wk Event Paradigm Topic Notes Reading Assignments
2014.09.02 1 Lecture Administrivia (honor statement, HKUST classroom conduct) Business Week, New York Times, Bjarne Stroustrup on Educating Software Developers, The Perils of JavaSchools, V1.Ch3,
2014.09.04 1 Lecture Procedural Singly vs doubly inked lists; homogenous vs heterogenous containers; structs, unions, tagged unions
2014.09.05 1 Lecture Procedural abstract data types; APIs; encapsulation; make; Assignment 0 [14:30-16:20, Rm 4214]
2014.09.09 2 Holiday Mid-Autumn Festival
2014.09.11 2 Resched [rescheduled to 2014.09.05]
2014.09.16 3 Lecture Functional StaticOO Encapsulation, s-expressions, cons lists, eval; Assignment 1 A0 due
2014.09.18 3 Lecture SwEngr Introduction: Data abstraction (YourPets2a.cpp, YourPets2b.cpp) V1.Ch2, V1.Ch4
2014.09.19 3 Lecture SwEngr Emacs; doxygen (doxygen notes: horrible example, Marine's, Adam's [14:30-16:20, Rm 4214] Self-review (References, Const)
2014.09.23 4 Lecture SwEngr StaticOO Introduction: C++ and software engineering; Assignment 1 V1.Ch1
2014.09.25 4 Lecture SwEngr StaticOO Declaration and definition (reverse_print.cpp, use_reverse_print.cpp, reverse_print.hpp); Overloading and constructors V1.Ch5; Overloading and constructors
2014.09.26 4 Lecture Functional DynamicOO Polymorphism, using car/cdr/cons/nullp; Assignment 2; Destructors [14:30-16:20, Rm 4214] V1.Ch6
2014.09.27 4 A1 due
2014.09.30 5 Lecture StaticOO DynamicOO Order of construction/destruction, Post Office example, argc & argv; Inheritance: Introduction V1.Ch14
2014.10.02 5 Holiday Chung Yeung Festival
2014.10.03 5 Lecture StaticOO DynamicOO Inheritance: Substitution principle; Inheritance: Access control: public, protected, private; Inheritance: Public, private, protected inheritance [14:30:00-16:20, Rm 4214] V1.Ch14
2014.10.07 6 Lecture DynamicOO Inheritance: Virtual functions; Inheritance: Abstract base classes, ex1, ex2, ex3, ex4 V1.Ch15
2014.10.09 6 Lecture DynamicOO StaticOO SwEngr Inheritance: Overriding vs overloading; The "this" pointer; Exceptions V1.Ch15; V1.Ch4; V2.Ch1
2014.10.10 6 Lecture Generic Functional Introduction to generic programming; Function and class templates; Exceptions, boolean operators, exposing eval & print; Assignment 3 [14:30-16:20, Rm 4214] V1.Ch16; V2.Ch1
2014.10.14 7 Resched [rescheduled to 2014.09.19] A2 due
2014.10.16 7 Lecture Generic Overloading operators; Container classes V1.Ch12; V2.Ch7
2014.10.21 8 Lecture Generic STL: Sequences & Iterators V2.Ch6
2014.10.23 8 Lecture Generic STL: Introduction to algorithms; STL: Function pointers V2.Ch6, ref V1.Ch3
2014.10.27 9 A3 due
2014.10.28 9 Exam Midterm (sample exam for your practice)
2014.10.30 9 Lecture Functional Lambda, apply, bootstrapping, Turing equivalence; Assignment 4
2014.11.04 10 Lecture Generic STL: Function objects or functors; STL: More algorithms V2.Ch6
2014.11.06 10 Lecture Dictionaries Trees: binary trees
2014.11.11 11 Lecture Dictionaries Trees: binary search trees
2014.11.13 11 A4 due
2014.11.14 11 Lab Functional Project (Lab Assignment): binary search trees, STL map interface
2014.11.18 12 Lecture Dictionaries Hashing, open addressing, separate chaining, hash functions; Assignment 6
2014.11.25 13 Lecture Algorithms Sorting: insertion sort, mergesort, quicksort, heapsort; More on sorting
2014.11.26 13 A6 due
2014.11.27 13 Lecture Functional Project (In-class Assignment): more bootstrapping: list-tail, list-ref, reverse, equal?, assoc; quicksort: list-partition, list-sort
2014.12.11 14 Exam Final (Rm 3008, L3-4, 12:30-15:30) sample final exam plus a sample midterm and another sample midterm for your practice)
Last updated: 2014.11.26