UCR CS 12: Introduction to Computer Science II

Winter Quarter 2003: January 3, 2003 - March 14, 2003

Overview

: In CS 12, you'll learn to solve larger programming problems and will also touch on some of the deeper concepts underlying Computer Science. Hopefully you'll also have fun too!; Catalog description: CS 12. Introduction to Computer Science for Science, Mathematics, and Engineering II. (4) Lecture, three hours; laboratory, three hours. Prerequisite(s): CS 10 with a grade of "C-" or better; familiarity with C or C++ language. Structured and object-oriented programming in C++, emphasizing good programming principles and development of substantial programs. Topics include recursion, pointers, linked lists, abstract data types, and libraries. Also covers software engineering principles.; Note: students receiving less than a C- in the CS 10 prerequisite will be dropped automatically a few weeks into the quarter.

Basic information

Instructors and office hours:

Wagner Truppel (wagner@cs.ucr.edu)

: Tue & Thu, 2:00 pm - 3:00 pm, by appointment only, requested by email, and not guaranteed unless you receive a confirmation reply.

Office: Surge Bldg. 340.

Teaching Assistants and office hours:

Anwar Adi (aadi@cs.ucr.edu)

: The hour after each of his lab sections.

Anup Mayank (mayank@cs.ucr.edu)

: Tue, 5:00 pm - 6:00 pm.
Wed, 6:00 pm - 7:00 pm.

Ashish Sharma (asharma@cs.ucr.edu)

: Tue, 2:00 pm - 4:00 pm.

Kun Yan (kyan@cs.ucr.edu)

: Tue & Fri, 4:00 pm - 5:00 pm.

Held in Surge Bldg. 282.

Lectures:

Section 1:	Tue & Thu	11:10 am	-	12:30 pm	in	R. G. Sproul Hall 1102.
Section 2:	Tue & Thu	8:10 am	-	9:30 am	in	J. W. Olmsted Hall 1208.

Labs:

Lab attendance is mandatory. You are expected to stay in the lab for the entire lab session, working on material related to this course.

Section 21:	Tue	2:10 pm	-	5:00 pm	in	Surge Bldg. 171.
Section 22:	Tue	2:10 pm	-	5:00 pm	in	Surge Bldg. 172.
Section 23:	Wed	11:10 am	-	2:00 pm	in	Surge Bldg. 171.
Section 24:	Wed	11:10 am	-	2:00 pm	in	Surge Bldg. 172.
Section 25:	Thu	6:10 pm	-	9:00 pm	in	Surge Bldg. 171.
Section 26:	Fri	6:10 pm	-	9:00 pm	in	Surge Bldg. 172.
Section 27:	Mon	8:10 am	-	11:00 am	in	Surge Bldg. 283.

Books:

: Required: Absolute C++, W. Savitch, 1st ed., 2003 Addison-Wesley.; Required: The Practice of Programming, B. Kernighan & R. Pike, 1999 Addison-Wesley.; Please consult the errata pages for those books because there are always errors and typos in every book, which can make you waste a great deal of time. The errata pages are typically accessible from the books' web sites. In addition, you might want to download Savitch's PowerPoint slides for the book. I may occasionally use those slides in the lectures and having your own copy is very helpful. The slides are available for download from the book's web page.; For optional books, visit the Additional Resources section below.

Course grading:

Letter grades are roughly assigned according to the usual 90/80/70/60 rule: 90% and above correspond to an A, 80% and above to a B, 70% and above to a C, 60% and above to a D, and less than 60% to an F. +/- grades will likely be given. A+ will be given only to students who turn in all required material and additional material of sufficient quality, typically an extended programming project. In addition, the course is divided into two grading components combined as a weighted sum:

65% Lecture component:

15%	Quizzes, typically given during lab sessions.
20%	Midterm.
30%	Final.

35% Lab component:

12%	Weekly in-lab programming exercises, attendance, participation, and adherence to coding standards.
15%	In-lab independent programming projects, typically given two or three times during the quarter.
8%	Home programming assignments, typically given every two weeks and due a week after assigned.

To ensure minimum competency in successive courses requiring a C- or better in this course, the following grading scheme will be used: a C- minimum in both components is necessary to achieve a C- minimum for the final course grade, regardless of the components' weighted sum; otherwise, the final course grade will be no greater than a D+. For example, a B in the lab component and a D in the lecture component might yield a weighted sum of a C, but would instead result in a final course grade of D+.

Approximate Time Requirements:

This is a four-unit course. As such, you should expect to spend the following approximate amount of time:

: 3 hours/week attending the lectures.; 3 hours/week attending the lab sessions.; 6 to 10 hours/week doing individual study (readings, homeworks, programming, lab preparation, etc).

Please do not underestimate the time you will need to spend on this course. These are real time amounts spent by average successful past students.

Course evaluation:

: We may provide midterm as well as end-of-term course evaluations. Midterm evaluations are an opportunity for students to let us know what is working and what we can improve, while there's still time to change.

Please help us to help you by filling out the course evaluation forms.

Lecture topics

Review of some basic ideas behind computer programming: binary numbers, computer organization, programming languages, compilers, linkers, executables.
Review of Procedural Programming: top-down and bottom-up approaches to solving programming problems.
Review of elementary C++: basic data types, variables, operators, expressions, flow of control, functions, call by value, call by reference, function overloading.
Introduction to Data Structures.
Elementary Data Structures: Arrays.
C++ and statically defined arrays.
Elementary Data Structures: Stacks.
Functions and Activation Frames.
The Divide-and-Conquer approach to solving programming problems.
Recursion.
C++ Structures.
C++ Pointers and Dynamic Arrays.
C++ Static and Dynamic Memory Allocation.
Introduction to Object-Oriented Programming.
C++ Classes.
Brief introduction to UML.
C++ Constructors.
C++ Namespaces.
C++ Operator Overloading, Friends, and References.
Classes and Dynamic Memory Allocation, Destructors.
The C++ String and Stream classes.
Inheritance.
Polymorphism.
Abstract Data Types.
C++ Templates.
Elementary Data Structures: Linked Lists.
The topics below were originally planned but not actually covered, due to time constraints.
- Containers and Iterators.
- Error handling: Exceptions.
- Introduction to Complexity Theory: Big-O Notation.
- C++ Standard Template Library.

Lab topics

: In addition to exercising the topics discussed in the lectures, lab sessions will also concurrently cover the following topics:

How to send and read email using Pine.
How to turn in your work electronically.
Basic UNIX commands, Emacs, gcc, make files.
Writing code: style and attitude. Coding standards.
Debugging: compiler, linker, and runtime errors.
Testing.
Software design: introduction to UML.

Detailed lecture schedule

Subject to change as the quarter progresses.

Please note that even though almost all the chapters in Savitch's book will be covered in the lectures, only a few of those will be covered with the level of detail presented in the book. Therefore, it's crucial that you read the book as we go along.

Do not put off reading the assignments or you will risk falling behind.

Date	Topics	Readings
Tue Jan 07	Course overview. Review of some basic ideas behind computer programming: binary numbers, computer organization, programming languages, compilers, linkers, executables.	Review chapters 1 and 2, then read the handout on computer organization. [handout 1]
Thu Jan 09	Review of Procedural Programming: top-down and bottom-up approaches to solving programming problems. Review of elementary C++: basic data types, variables, operators, expressions, flow of control, functions, call by value, call by reference, function overloading.	Read chapters 3 and 4 to review the material you learned in CS 10.
Tue Jan 14	Introduction to Data Structures. Elementary Data Structures: Arrays. C++ and statically defined arrays.	Read chapter 5.
Thu Jan 16	Elementary Data Structures: Stacks. Functions and Activation Frames.	Read the handout on stacks and activation frames. [handout 2]
Tue Jan 21	The Divide-and-Conquer approach to solving programming problems. Recursion [Tower of Hanoi demo].	Read chapter 13. Recursion is non-intuitive at first, so make sure to read this chapter carefully.
Thu Jan 23	C++ Structures. C++ Pointers and Dynamic Arrays. C++ Static and Dynamic Memory Allocation.	Read sections 6.1, 10.1, and 10.2. Pointers confuse many beginners, so read those sections very carefully.
Tue Jan 28	Introduction to Object-Oriented Programming. C++ Classes. Brief introduction to UML.	Read sections 6.2, 7.1, and 20.2.
Thu Jan 30	C++ Constructors. C++ Namespaces.	Read section 7.2 and chapter 11.
Tue Feb 04	C++ Operator Overloading, Friends, and References. Classes and Dynamic Memory Allocation, Destructors.	Read chapter 8 and section 10.3.
Thu Feb 06	Midterm Exam
Tue Feb 11	The C++ String and Stream classes.	Read chapters 9 and 12.
Thu Feb 13	Inheritance I.	Read section 14.1.
Tue Feb 18	Inheritance II. Polymorphism I.	Read sections 14.2 and 15.1.
Thu Feb 20	Polymorphism II.	Read section 15.2.
Tue Feb 25	Abstract Data Types. C++ Templates.	Read chapter 16.
Thu Feb 27	Elementary Data Structures: Linked Lists I.	Read section 17.1.
Tue Mar 04	Elementary Data Structures: Linked Lists II.	Read section 17.2.
Thu Mar 06	[not actually covered this quarter] Containers and Iterators. Error handling: Exceptions.	Read section 17.3 and chapter 18.
Tue Mar 11	[not actually covered this quarter] C++ Standard Template Library: Containers and Iterators.	Read sections 19.1 and 19.2.
Thu Mar 13	[not actually covered this quarter] Introduction to Complexity Theory: Big-O Notation. C++ Standard Template Library: Generic Algorithms.	Read section 19.3.
Tue Mar 18	Optional Review Session
Thu Mar 20	Section 1 Final Exam: 8:00 am - 11:00 am
Sat Mar 22	Section 2 Final Exam: 8:00 am - 11:00 am

Detailed lab schedule

Subject to change as the quarter progresses.

'K & P' on the table below refers to Kernighan & Pike's The Practice of Programming book.
Readings should be completed before the lab session they correspond to.
Home programming assignments are due at 8:00 pm on the due date.

Week	Topics/Activities	Assignments
1 Jan 06 - 10	Login assignments. How to send and read email using Pine. How to turn in your work electronically. Basic UNIX commands, Emacs, gcc.	In-lab programming exercise 1: functions.
2 Jan 13 - 17	Writing code: style and attitude. Coding standards. Presentation of chapter 1 of K & P. Quiz 1, on material and readings from week 1 lectures, and on chapter 1 of K & P.	Read chapter 1 of K & P. Home programming project 1: arrays and stacks. out on Jan 12, due 9 pm Jan 20
3 Jan 20 - 24	Presentation on recursion, structures, and pointers. Quiz 2, on material and readings from week 2 lectures.	In-lab programming exercise 2: recursion, structures, and pointers.
4 Jan 27 - 30	Brief presentation on UML. Quiz 3, on material and readings from week 3 lectures.	In-lab programming exercise 3: debugging.
5 Feb 03 - 07	Debugging. Presentation of chapter 5 of K & P.	Read chapter 5 of K & P.
6 Feb 10 - 14	Discussion of midterm solution. Testing. Presentation of chapter 6 of K & P.	Read chapter 6 of K & P. In-lab independent programming project 1: Structures and pointers.
7 Feb 17 - 21	Quiz 4, on chapters 5 and 6 of K & P, and on lecture material from week 6.	Home programming project 2: operator overloading. out on Feb 15, due 9 pm Mar 3
8 Feb 24 - 28	Presentation on C++ Templates. Quiz 5, on lecture material from week 7.	In-lab programming exercise 4: class inheritance and polymorphism.
9 Mar 03 - 07	[not actually covered this quarter] Presentation on Containers, Iterators, and Exceptions. Quiz 6, on lecture material from week 8.	In-lab programming exercise 5: separate compilation.
10 Mar 10 - 14	[not actually covered this quarter] Presentation on Complexity Theory and Big-O notation.	[cancelled] In-lab independent programming project 2: linked-lists and templates.

Material available for download:

Handouts:

1:	Intro to computer organization	pdf
2:	Intro to stacks and activation frames	pdf

Lecture slides:

	My own	Savitch's
1:	pdf / pps	-
2:	pdf / pps	-
3:	pdf / pps	Ch. 5: pdf / pps
4:	pdf / pps	-
5:	pdf / pps	Ch. 13: pdf / pps
6:	pdf / pps	-
7:	pdf / pps	-
8:	pdf / pps	-
9:	pdf / pps	Ch. 8: pdf / pps
10:	pdf / pps	Ch. 14: pdf / pps
11:	see lec 10.	Ch. 15: pdf / pps
12:	pdf / pps	-
13:	pdf / pps	Ch. 17: pdf / pps

Demos:

The Towers of Hanoi puzzle, implemented as both an applet and a stand-alone java application. This demo requires Java 1.2 or higher.

html / jar

In-lab programming exercises:

	Topic	Assignment	Free Code	Solution
1:	Functions	pdf	-	pdf / cpp
2:	Recursion, structures, and pointers	pdf	cpp	pdf / cpp
3:	Debugging	pdf	cpp	pdf / cpp
4:	Class inheritance and polymorphism	pdf	cpp	pdf / tar
5:	Separate compilation	pdf	-	pdf / tar

In-lab independent programming projects:

	Topic	Assignment	Free Code	Solution
1:	Structures and pointers	pdf / tgz	cpp / txt	cpp
2:	Linked-lists and templates	-	-	-

Home programming projects:

	Topic	Assignment	Free Code	Solution
1:	Arrays and stacks	pdf	cpp	- / cpp
2:	Classes and operator overloading	pdf	cpp	- / cpp

Quizzes:

	Questions / Solutions
1:	not administered
2:	pdf
3:	pdf
4:	not administered
5:	pdf
6:	pdf

Exams:

Exam	Questions / Solutions
Midterm	pdf
Section 1 Final Exam	-
Section 2 Final Exam	-

General course features and policies (please read these carefully)

Material covered: Lecture doesn't cover all required material, which also appears in the course books and may be covered only in the lab sessions.
Academic dishonesty: cheating will be strongly punished (typically with an F in the course). You can report cheating anonymously at: https://www.cs.ucr.edu/cheating/. Assignment submissions must represent your original work. Copying from any sources (web, other books, past or current students, etc.) is strictly prohibited -- learning to program requires you to learn to figure things out by yourself; using existing code and other resources becomes important later on in your studies. While discussing assignments together is encouraged, team coding (even of pseudo-code) or letting others see your code are specifically not allowed. Be aware that programs are automatically compared to the current and prior quarter's programs for plagiarism, using a sophisticated code-comparison tool that ignores insignificant differences (like whitespace and variable names). If you're smart enough to fool the instructors, TAs, and code-comparison tools, you're more than smart enough to do the programs on your own!
Final Exams are scheduled by the University, not by the instructor, and are correlated to the course sections. What that means is that you must take the final exam scheduled for the section you are enrolled in. The same policy will apply to the midterm and quizzes.
Regrade policy: corrections must be submitted in writing and within one week of the distribution of the graded material. The entire exam/assignment may be regraded, not just the problem in question, so the grade may go up or down. Thus, think your regrade requests through carefully. Grade-database errors should also be pointed out within one week of posting.
Final grades: Per university policy, changes to your final grade will be made only in the event of a clerical error. You should not ask the instructor how far you were from a cutoff and what extra work you can do to improve the grade.
Switching/adding/dropping lab and lecture sections: all add, drop, and section changes of all lower division Computer Science courses, after the period when students can do so electronically is over, are done through the College of Engineering's Student Affairs office. Neither the instructors nor the CS department itself can sign any add/drop forms, nor can they arrange for section changes. Please go to Student Affairs, Bourns Hall A159, for any and all such changes.
Communicating with the instructors and TAs: when sending electronic mail to the instructors or TAs, include in the body of your message your full name, student ID number, and UCR email address. Keep in mind that there may be several students with names almost identical to your own, so proper identification is essential for a prompt reply. Also, please try to be polite and use reasonable grammar and formatting.
Cell phones: During lectures and lab sessions, we expect you to turn off your cell phone. If you can't make sure that your cell phone is off during those periods, please leave it at home.
Homework and lab reports: All turned-in assignments must be turned in electronically. Every part of your assignment (every file) must begin with our report template header. Source code must comply with professionally accepted coding standards. In particular, all your code must be compiled with the -Wall -W -Werror command line options, or else it will not be graded. Also, you must include a section explaining the design, structure, etc of your program and how it works. Comments in source code are important, must be there, and help, but they are not a replacement for an explanatory section. In addition, please remember that successfully writing a computer program that compiles and runs correctly is not something anyone can do in just a few minutes, even when it looks easy. Debugging typically takes three times longer than figuring out how to write your program. Do not leave your programming assignments to the last minute.
Reading: Read the current book sections before coming to lecture, and attend all lectures in their entirety. To encourage these important college study habits, we may give a few simple pop quizzes during the quarter, at any time during lecture.
A+'s may be given to students submitting all required material and possibly turning in extra (quality) material (typically lab-related) going beyond the course requirements.
Success in computer science courses requires time. A typical student needs to spend 12-16 hours per week on this course (including lecture and lab). For your own benefit, please allocate that time.

Lab guidelines (please read these carefully)

Students are required to stay the full three hours of lab session every week. You'll have in-lab exercises, quizzes, discussions, and practical exams. Work ahead or on extra course-related material if you finish early.
During lab discussion time, students should move away from their computers to the whiteboard.
Prepare for lab before arriving.
All persons in lab during scheduled lab time must be formally registered in that section. No swapping sections and no unregistered people in the lab are allowed.

Electronic assignment turn-in

Grades

: Final scores. Please check carefully.

Course email list

: CS 12 mailing List (send mail now or access the archive): Be sure to sign up to receive important announcements, which will be made only through the course email list. You must use your CS or EE account, or else some other UCR account, so be sure to learn how to read those accounts or at least automatically forward messages to your personal email address (just create in your home directory a file named ".forward" containing your personal email address).

Additional Resources

UCR CS department's Online Documentation page.
UCR CS department's Cool Links and Resources For Students page.
GNU Emacs Reference Card (pdf).
Anwar Adi's Intro to programming tools in Linux page.
Books
- Peter Fröhlich's excellent book page.
- C++ in a Nutshell pre-release web page.
- Software Craftsmanship - The New Imperative.
- Practical C++ Programming.