Data Structures (Summer 2016: 22c:021)
Course Supervisor: Professor In Jeong Chung.
Discussions: MW 12:30P -1:20P (Section A01) & TTh 12:30P -1:20P (Section A02) in 301 MLH.
Office Hours: T 1:30P - 3:20P & W 1:30P - 2:20P (in 301 MLH), and by appointment.
Links: C++ Language Tutorial
Topics, tutorial links, examples and files (by week)
Week 1: C++ basics, structure of a C++ program, variables, data types, type deduction, literals, increment and decrement operators (difference between x++ and ++x), conditional ternary operator, basic input output (cin and cout), stringstreams, control structures.
Example program: week1.cpp
Week 2: Continuation of control structures, functions, call by value vs. call by reference, inline functions, recursivity, overloaded functions, function templates, scopes and namespaces, C++ classes, constructors, constructor overloading.
PowerPoint: Container Classes
Example program: A static bag container class
Week 3: Pointers to classes, difference between classes and structures, operator overloading, keyword this, static members, constant member functions, class templates, linked list implementation, discussion on programming assignment 1.
Example program: LinkedList.cpp
Week 4:
Continuation of discussion on programming assignment 1.
Example program: poly_linkedlist.cpp
Introduction to Standard Template Library (STL) and vectors (section A02 only).
Tutorial links:
Week 5:
Introduction to Standard Template Library (STL) and vectors (section A01), stack implementation in C++, infix to postfix conversion algorithm, discussion on programming assignment 2, application of operator overloading in polynomial addition.
Infix to postfix conversion algorithm
Pseudo-code for infix to postfix conversion
Example programs:
Stack.cpp
PA2.cpp
Polynomial.cpp (operator overloading)
Week 6:
Binary search trees (BST), construction and traversals of BSTs in C++ (example program: figure 10.10 at page 513 of textbook), how to pass a function as a parameter of a function (page 507), passing a function as a parameter to solve the traversal problem mentioned in the text book (page 506), discussion on programming assignment 3.
Example program: PA3.cpp (updated, all errors fixed)
Week 7:
Discussion on programming assignment 3 & 4, definition and motivation for topological sort/ordering, an algorithm for finding a topological ordering from a DAG using sink/source vertex, an algorithm for finding topological ordering from a DAG using depth first search.
Lecture note and example program
Video lecture of Tim Roughgarden
Week 8:
Difference among passing a pointer, a reference of a pointer, and a pointer to a pointer. Discussion on programming assignment 4.