This course covers advanced computer programming, mainly concerning representation of data and use of the memory. See the syllabus.
MW 11:00-12:30, TTh 11:00--12:00 or by appointment.
If you have obtained a password then you can check your grades as I have them recorded.
You can obtain a password from me. To obtain one by email, send me email giving your name, the course, and the password that you want. Choose a string of 4 or 5 letters/digits.
Assignments will be posted here as they become available. Some pages are available to help you know how to write programs.
The class notes describe C/C++ language features and the basics of object-oriented programming. You can also find material in the appendix of the textbook.
Although you may feel free to develop your programs under any system, all programs will be tested using the g++ compiler under Unix. All students will receive accounts in the lab in Austin 320. If you already have an account, it has not been changed. If you do not have an account, then your account is your first initial followed by your middle initial followed by up to six letters of your last name.
A brief tutorial on unix is available.
[8/22/02] We began looking at memory management in C++. We talked about the memory, memory addresses and pointer variables. The * operator finds the thing that a pointer points to.
[8/27/02] We continued looking at memory management. We say the heap, and the new and delete operators. We started working on arrays.
[8/29/02] We looked at arrays, pointer arithmetic and memory management using arrays. We did examples using null-terminated strings.
[9/5/02] We discussed programming assignment 1 and hash tables.
[9/10/02] We discussed more on programming assignment 1, and also looked at structures in C++, and how to use pointers to structures.
[9/12/02] We began looking at linked lists, and how to define functions on linked lists. We used both loops and recursion.
[9/17/02] We discussed abstraction and information hiding. We defined an abstract, or conceptual, view of lists. Next time we will implement the conceptual view, and see how to use it in other modules.
[9/19/02] We discussed progrmming assignment 2. Then we looked at functions on lists, including concatenation of lists.
[9/24/02] We continued looking at linked lists. Functions can be implemented either in the physical view (inside the implementation of the abstract data type) or in the conceptual view (either inside or outside the implementation of the abstract data type).
[9/26/02] Exam 1.
[10/1/02] We began a study of object-oriented programming by looking at the basic concepts, and how they are written in C++.
[10/3/02] We did an example of an abstract data type in an object-oriented style. We defined stacks, and wrote a class to implement them. We introduced destructors, and added a destructor to the stack class.
[10/8/02] We looked at an alternative implementation of stacks, using linked lists.
[10/10/02] We discussed programming assignment 3, and how to compute minimal spanning trees.
[10/17/02] We discussed more on programming assignment 3, including how to implement the connection manager.
[10/22/02] We talked about queues and a class that implements queues.
[10/24/02] We went through details of an implementation of queues using an array.
[10/29/02] We discussed programming assignment 4.
[10/31/02] We discussed priority queues, and began to look at heaps.
[11/5/02] We went through details of heaps, including the reheapUp and reheapDown operations.
[11/7/02] We saw how to perform the update operation in heaps, and quantified the efficiency of heaps.
[11/12/02] We began to look at the problem of sorting an array. We used heaps to develop an algorithm that sorts an array of size n in time proportional to n log2(n).
[11/14/02] We continued to look at sorting. We developed the quicksort algorithm, with runs in time n log2(n) in the average case.
[11/19/02] We proved a lower bound for sorting.
[11/21/02] We looked at the searching problem, and explored methods of implementing tables.
[11/26/02] We looked at basic binary search trees, and saw algorithms for lookup and insertion.
[12/3/03] Exam 2.