Week

Date

Topics

Slides (codes)

1

2 Sep

Introduction
C++ language basics
Basic control: conditional, and iteration

intro.ppt
basics.ppt
if.ppt
loop.ppt
control2.ppt

4 Sep (1^st assignment)

2

9 Sep

Functions

Function overloading

Reference
Array

function.ppt

function2.ppt

reference.ppt
array.ppt (1/2)

11 Sep

3

16 sep

Algorithms

Search and sort

Recursion

Algorithm analysis

pointer.ppt ½

array 2/2

recursion.ppt

analysis

18 sep

4

23 sep (mixed-mode, lecture room and zoom)

Sorting algorithms

Data structures

Pointers and  dynamic Data

Concept of lists and linked lists
Some algorithms with linked lists

insertionMergeSort

quicksort

pointer.ppt 2/2 (as dynamic objects)

struct.ppt
list.ppt

25 sep (2^nd assignment)

5

30 sep

2 oct

6

7 oct (holiday, no class)

Local/global scope

listAlgo.ppt (.cpp)

scope.ppt

9 oct

7

14 oct

Object-Oriented Programming

Basic Object-Oriented Programming (OOP): classes

Abstract data type (ADT)

Dynamic classes

Fundamental Data Structure:
- list and its ADT

class

abstractDataType

dynamicClass

listADT

16 oct

8

21 oct (in-class midterm, two hours from 10:30am to 12:20pm)

Mid-term exam week

23 oct (in-class midterm check-up, no lecture)

(3^rd assignment)

9

28 Oct

Operator overloading, Part 1

overload (string in codes)

Part 2 of overloading

30 Oct

10

4 Nov

More on classes:

- static members

- member initializer

Generic Programming:
- function and class templates

File organization: Separate compilation
(File I/O)

class2 (codes)

generic (codes)

separateCompilation
fileIO.ppt

6 Nov

11

11 Nov

More on data structures and applications:

- stacks

- queues

Applications: bucket and radix sort

Standard Template Library (STL) (vector, list, deque, stack, queue (string))

Inheritance
- single inheritance
- order of construction/ destruction
- multiple inheritance

stackQueue (codes)

STL
vector reference
list reference
deque reference
stack and queue reference
string
string reference

inheritance

13 Nov

 (3^rd assignment due, 4^th assignment)

12

18 nov

Polymorphism
- virtual functions
- dynamic binding
- pure virtual functions
- abstract classes

Non-linear data structures
- trees, binary tree and binary search tree (BST)

Balanced BST binary search tree: AVL trees

polymorphism
(codes)

bst
(codes)

avl1
(avl2)

20 nov

13

25 nov (4^th assignment due)

27 Nov ( The Last Lesson)

Heaps, Heap sort, priority queue

B Trees (1)

Graphs, Breadth-first-search and depth-first-search of graphs

(not Part II of dfs, not topological sort)

Hashing

heapsort

btree

bfs
dfs

hashing

Final exam:

Friday, 12 Dec 8:30am-11:30, 4620