Week
Topic
Lecture
Reading
TA notes
Assignments
1
08/22/11 - 08/26/11
Intro to C++
2.
Pointers
3.
Object Based and Object Oriented Programming
4
Time and Space Complexity
5
Linear Lists, Arrays, array Lists and Matrices
6
Stacks and Queues
7
Hashing
8.
Binary and other trees
9.
Binary Trees
and Priority Queues
10.
Exam1
11
Balanced BSTs and Graphs
08/22/11
Syllabus and Administrivia
08/24/2011
Header files and separate compilation.
08/26/2011
C++ and C strings and Intro to STL
08/29/2011
Java vs C++ and Intro to Pointers
08/31/2011
Pointers contd
Passing and returning from functions
09/02/11
Pointers contd
09/05/2011
Labour Day
NO Class
09/07/2011
C arrays, pointers, destructors, copy constructors and operator=
09/09/2011
Time complexity
09/12/2011
Space complexity,
Intro to cache miss and effects of cache on performance.
09/14/2011
linear lists
09/16/2011
Array Linear List
Chapter 5
09/19/2011
Array List and Linked Lists
09/21/2011
Linked Lists
09/23/2011
Arrays and Sparse matrices
09/26/2011
Sparse matrix concluded and Stacks started
Chapter 1(textbook: Sahni)
makefile and compilation tutorial
by Ricky J. Sethi (not related to me :) )
Unix Programming tools from Stanford CS library
STL vectors<vector>
STL strings<string>
<cstring> or <string.h>old style C strings
Chapter 1(textbook: Sahni) Please read this completely if you did not read it last week.
Read Pointers and Memory from Stanford CS Ed Library.
The above article and all the other articles mentioned below and otherwise by Nick Parlante and from Stanford CS library are really useful and worth reading.
Read Essential C by Nick Parlante from this page.
Passing arrays as Parameters: read at the bottom of this page
Here is a nice article on difference between C++ arrays and Java arrays. It is very important that you read it and understand properly.
Also read the Weiss C++ review below for passing and returning from functions
Read section 1.4 of the textbook (Sahni) and particularly section 1.4.5
Necessary housekeeping for the above Vect fragment
Read Essential C++ by Nick Parlante from here.
Read at least the first of these three links. this contains some examples that we discussed in class and also the description on Copy Constructors, Operator=, and destructors.
Read E4 from this document on overloaded operators
Deadline extended till Friday 23rd september 2011, before class 12:50pm
IMPORTANT CORRECTION:
Iterator::begin() returns an iterator referring to the FIRST element of the container, NOT a null position.
10/03/2011
Hashing started
10/05/2011
Data structure using pair, compression and hash functions
10/07/2011
String to integer keys
10/10/2011
double hashing, rehashing etc.
10/12/2011
hashing ends and trees started, properties of binary trees
10/14/2011
BInary trees contd.
10/17/2011
Chapter12 started
10/19/2011
heap sort, machine shop problem etc.
10/21/2011
10/24/2011
Union Find
10/26/2011
10/28/2011
Binary Search Trees
NO LECTURE
7.
8.
9.
10.
11.
12.
13.
14.
15.
16
17
18
19
20
21
22
23
Some additional reading material:
Read lecture 12 from here for another good article I found on pointers and memory in C++. This article also gives a good review on C++ memory model (Stack vs heap memory model). And another interesting thing is that this article ends with the 3 swap functions we discussed in class.
Secondly, here is a really good document on Dynamic memory allocation. Please read it thoroughly.
Another good article! The more you read the better you get :)
Another article on pass by value vs pass by reference. You will notice that this swap function explanation is so ubiquitous in explaining this concept.
Here is an article on difference between C++ and Java classes.
Read section 2.2 and 4.5 of the textbook.
For time complexity read Chapter 3 completely, specially section 3.3. (Note that this is not optional even though the book says so.)
Other than above selected topics that were covered in class, you should completely read Chapters 2, 3, 4 yourself.
Read the proof given on page 152 for array doubling.
Start reading Chapter 5
Read section E4 from this document on overloaded operators by Scott Meyers
Chapter 5
Chapter 6
Chapter 7
Chapter 8.
Read the Tower of Hanoi problem, Parenthesis matching problem and Rat in a maze problem.
Chapter 8 complete
Chapter 9
Chapter 10 started
I will write up a note and post it for conversion from string to integer keys.
Readings/notes will be posted over the weekend
Chapter 11 started
Last semester's exam 2 (syllabus from which is also included in this time's exam 1)
Stroustrup STL Written by Mr. C++
Notes on Input and output files for prob 2
Read these documents for creating random access iterators. You will need the random access iterator tag.
Also familiarize yourself with the typedef keyword in C++
12
Graphs
13
Greedy algorithms
10/31/2011
AVL Trees
11/02/2011
Graphs
11/04/2011
NO CLASS
(Homecoming)
11/07/2011
Graph Search Methods
11/09/2011
11/14/2011
Single source all destinations
11/16/2011
Proof of Dijkstra's algorithm and MInimum Spanning Trees
11/18/2011
Dynamic Programming
due wed Nov 16. Additional details and I/O files will be posted soon.
For post order iterator (Q1) you can use the following files and the driver code.
refresh your browsers and use files below:
14
Dynamic Programming
15
Divide and Conquer
11/21/2011
Longest Common Subsequence (LCS)
11/23/2011
Bellman Ford Algorithm
11/28/2011
We revisited Bellman Ford and started Divide and Conquer: merge sort, binary search. power of a number and their recurrences
11/30/2011
Quick sort, matrix multiplication,
Strassen's algorithm
12/02/2011
Selection problem and closest pair of points
For multistage graphs, the standard reference section 5.2 from this classic book:
by Horowitz, Sahni and Rajasekaran
The above link may be hard to understand because of all the formalism involved. INstead you can look over my notes or read the link below.
Read LCS from CLRS book.
Read Bellman Ford Algorithm from textbook(Sahni) and CLRS book for negative cycles.
Some dynamic programming practice problems:
http://people.csail.mit.edu/bdean/6.046/dp/
You may (not required) also want to read a few sections from Chapter 6 of this book:
http://www.cs.berkeley.edu/~vazirani/algorithms.html
(Note that Q4(c) is not in the syllabus)