CS117-02: Introduction to Programming III: C++ Spring 1998

Course Syllabus

Material Covered

So this class is about giving you some analysis tools for confronting problems that come up in everyday programming. In this class, we want to explicitly lay out for you some of the classic data structures used in thinking about the way data should be organized in a program. In many cases, particular ways of solving a problem, or algorithms, suggest particular kinds of data structure, and vice versa. I want to give you a sense of how the two are interlinked, and the issues involved in selecting algorithms and data structures.

We will be coding in C++, and we'll be using the Macintosh as the platform. The C++ standard has been expanded to include a number of classic data structures, and a set of generic algorithms to manipulate them. This whole collection has been put together into something called the Standard Template Library, or STL.

Below is a sequence of material I hope to cover this quarter. It's a rough outline, and there will be supplementary materials provided as needed. Also, the content will probably change in the next week or two as I focus in on project so that there is a nice, fun synergy of coding and theory.

An Outline of Things to Come

Lecture 1, 3/30. An introduction to the study of algorithms and data structures. A review of C++. A light introduction to the STL. Administrative details.

Lecture 2, 4/3 A little more on STL. Introduction to algorithm analysis. Recursive functions.

Lecture 3, 4/6 Order notation.

Lecture 4, 4/8 Benchmarking. Correctness.

Lecture 5, 4/10 Introduction to container classes. A detailed treatment of standard string library.

Lecture 6, 4/13 Vectors. Simple sorting. Introduction to lists.

Lecture 7, 4/15 Lists. Introduction to search.

Lecture 8, 4/17 Stacks and queues. Simulation.

Lecture 9, 4/20 Queues. Sets and multisets. More on search.

Lecture 10, 4/22 Trees. Binary trees.

Lecture 11, 4/24 Parsing. Search.

Midterm, 4/27

Lecture 12, 4/29 Review of the midterm. About the final project.

Lecture 13, 5/1 Priority queues. Heaps.

Lecture 14, 5/4 Maps.

Lecture 15, 5/6 Hashes.

Lecture 16, 5/8 Data mining and ADTrees.

Lecture 17, 5/11 Matrix representations.

Lecture 18, 5/13 Graphs. Adjacency matrix representations. Edge list representations.

Lecture 19, 5/15 Graphs. Weighted graphs. Sparse matrix representations.

Lecture 20, 5/18 Graphs. Profiling.

Lecture 21, 5/20 Files.

Lecture 22, 5/22 Binary files. File merging.

Lecture 23 , 5/25 An Overview of CORBA.

Lecture 24 -- 29, 5/27 -- 6/4 Other material on final project.

Final ? [6/4 , 6/12]

Software and Instructional Lab

The department has an instructional lab, called the MacLab, which is located in Ryerson 177 and 178 and has a large number of Macs. We'll be using the Metroworks C++ compiler. This is bundled in an extensive Integrated Development Environment (IDE).

You will need to bring a 3.5 inch disk each time you work in the MacLab, so that you can save the work you've done. Please have several for this course. Also be sure to keep a separate backup disk and make a backup of your work regularly. The MacLab also has a library of reference manuals for your use while in the Lab. Be sure to ask for help from the MacLab staff if you need it. Since some of the later assignments will make use of platform dependent resources, you will have to use Codewarrior for the Mac. If this presents a serious problem, see me.

There will be a folder on the MacLab server for this section of the class. Some information you may need for future homework will be in this folder, as well as a drop-box for you to hand in the program portion of your homework. You can find the folder by going to MacLab Administration, Courses, Spring 1998, 117-02.

Grading Policy and Homework

This course will be graded on the basis of assignments which will be due on Friday of every week, a midterm, a final exam, and a final project. The assignments are due at the time of class. You will have a homework assignment that can be a throw away. Late assignments will be corrected and returned, provided that they are received before the assignments are handed back, but will not count toward your grade. This policy is intended to encourage you to keep up with the work, which is critically important in this course.

For all programming exercises, hand in a printout of the program and several sample runs on representative data for programming exercises, making sure to put your name on top of every sheet. Nonprogramming exercises should be written up neatly, one problem per sheet of paper, also with your name at the top of every sheet. When testing your programs run them on inputs that make it hard for your program, in order to show clearly that your program works. You should also provide an electronic version of your programming assignments. This means you must either place a version in the drop box or turn in a version on a 3.5" diskette.

Programming assignments will be graded on both correctness and style. The correctness criteria should be clear. Style is something a little more subjective, but programming style is a lot of what you should learn in this course. Be sure to comment your code! Procedures should start out with few lines telling what the procedure is supposed to do and what the arguments are, and any non-obvious lines in the procedure body should have a comment after them. This will make more sense once you begin doing the assignments.

The grade in this course will be based on the following percentages:

homework -- 35%

midterm project -- 15%

final project -- 15%

final exam -- 35%

Academic Misconduct

Collaboration is permissible on the homework, if you indicate clearly who you cooperated with. Copying someone's homework verbatim isn't going to help you on the final. Please acknowledge on each assignment any discussions that may have taken place or any sources you have consulted. Don't cheat on the final or midterm. The final project should also be your own thing, for example, you should be able to intelligently discuss how you implemented it.

As this is a course in computer science, you should also be aware of the University's Policy on Information Technology Resources, described in the Student Information Manual.

Last modified: Fri Apr 24 14:51:46 CDT 1998