CSCI 102L will teach students the fundamentals of object-oriented
programming and design with a focus on the representation and
manipulation of data using well-known data structures.
This course will use the C++ programming language.
Familiarity with C/C++ (at the level of CSCI 101L or EE 106L)
- Basic UNIX usage (ssh, vi/emacs/pico, g++)
- Basic stream usage (cout & cin)
- Control structures (if/else if/else, switch, for/while/do-while, etc.)
- Defining & using functions (modularization of code)
- Basic use of strings
- Basic use of arrays & vectors
- Basic use of structs & classes
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms (3rd Edition),
MIT Press, 2009.
(Chapters 6 & 11 are used as reference material)
- [BC: added 3/21/2011]
G. T. Heineman, G. Pollice, and S. Selkow,
Algorithms in a Nutshell [Paperback],
(Chapters 4 & 5 are used as reference material)
- [BC: added 3/18/2011]
Data Structures and Algorithms in C++ [Paperback],
Thomson Press (India) Ltd, 2006.
(Chapters 9 & 10 are used as reference material)
A link to the
USC Spring 2011 academic calendar
is provided here for your convenience.
Syllabus / Topics Covered
This course is split into two major portions. In the first
portion of the class, we'll be discussing topics that give
students with a solid programming foundation in C++.
This portion of the class is very programming intensive and
the major topics will include:
Once students have used the first portion of the course to
solidify their programming abilities, the second portion on
the course will focus almost entirely on data structures and
The topics for the second portion of the course include:
- Basic Data Structures
- Memory management
- Reference Variables
- Automatic vs. Static variables
- Stack allocation vs. Heap allocation
- Input/Output Streams
- Console (cin, cout, cerr)
- Exception Handling
- Object-Oriented Design
- Advanced Programming Topics
- Graphical User Interfaces (GUIs)
- C++ Standard Template Library (STL)
- Algorithmic Complexity (Big O notation)
- Algorithm Design
- Data Structures
- Linked Lists
- Stacks, Queues, Deques
- Binary Search Trees
- Heaps, Priority Queues
- Sets, Maps, Hashtables
Certainly a large portion of the course is focused on teaching
students various programming techniques, algorithms and data
structures, but over the course of the semester, students are
also encouraged to keep the following themes in mind:
- Making the transition from programmer to software engineer
- Writing software other developers can (re)use
- The power of data representation and abstraction
- The beauty and potential of object-oriented design
- Writing clear, efficient and maintainable code
- Becoming a better all-around software developer
The elements of the course can be viewed in a pyramid structure:
Reading Assignments: Readings from the book and other sources form the base of the pyramid. These readings contain theoretical concepts, examples and usable code that will be very helpful for all the work in this course.
Lab Assignments: The lab assignments are designed to provide you with fundamental programming techniques that important to all of your software engineering endeavors. Labs will be assigned on a weekly basis and will focus on implementing various topics discussed in lecture. It will be difficult to succeed in this class without doing the weekly labs on time.
Homework Assignments: The homework assignments will utilize the techniques, and in some cases the code, from the labs. The labs are like miniature homework assignments and students will use what they learn in labs to complete the larger homework assignments. If students neglect to do the labs, they will find the homework assignments much more difficult.
Exams: The exams are the top of the pyramid. Students will be expected to know the material from the assigned readings in the book, the labs and the homeworks. The exams are a student's chance to demonstrate that they fully understand the course material.
Course ABET Outcomes
- Ability to choose appropriate and efficient data structures and algorithms to solve a problem
- Ability to compare data structures and algorithms for efficiency using algorithm analysis
- Ability to program wiith a container-class library
- Ability to design, document, and implement classes
- Ability to program with pointers and dynamic data
- Ability to write recursive functions and understand when recursion is appropriate to a problem
- Ability to use or implement linear data structures, including stacks, queues, lists
- Knowledge of search structures and algorithms including binary search, search trees, and hash tables
- Knowledge of sorting algorithms
- Ability to apply tools and techniques for program correctness,
such as unit testing, use of a symbolic debugger, and assert statements
- Ability to convert a small to moderate-sized problem into a program in an object-oriented language
- Ability to write readable and maintainable code
- Ability to use or implement other data structures such as (non-search) trees, heaps, and graphs
Academic Integrity Policy
Please make sure you read the Academic
Integrity Policy of this course.
Most class related announcements will be done through e-mail via
a Google Group setup by the instructor.
It is your responsibility to make sure that your mailbox
is not full. If you miss some important announcements
because your e-mail service provider is dropping your
messages on the floor, it cannot be used as an excuse.
Lab Assignment Grading
Unless otherwise specified, each weekly lab will require a design
writeup to be written and turned in at the start of the lab
for that week. These are worth 3 points.
You cannot get the 3 points unless you turn in your writeup
at the beginning of lab.
You can find a template for your design documents
If you don't finish your lab during your lab session, you can
go to a later lab session and demonstrate it to the TAs there.
You may also demonstrate the lab assignment to one of the TAs
or the instructor at their office hours.
If you don't get your lab graded during the week it is assigned,
you will receive a 50% deduction penalty.
Labs MUST be demonstrated to the instructor or TAs by the end
of day Friday.
You should strive to have your labs finished by the end of your lab session.
Labs will only be graded up to one week late.
After that, you will get no points.
Homework Assignment Grading
All of the homework assignments will require students to
prepare a design document.
You can find a template for your design documents
All assignments will be graded on the aludra/nunki UNIX systems.
Before you submit your code, MAKE SURE that your code compiles
and runs properly on aludra/nunki because that's where it will
be tested and graded.
An excuse such as "It runs just fine on my computer!" will not
Please also note that you must submit your code using the
USC Blackboard System
since the Blackboard System timestamps you submission.
All homeworks must be turned in on time.
Late submissions will receive severe penalties. Due to clock skews,
electronic submissions of homework assignments will
be accepted within 15 minutes after the specified deadlines without
If you submit within the next 24 hours, you will receive 80% of your grade.
Although right after midnight, you will lose 1% every 5 minutes.
When the penalty reaches the day limit, it flattens out.
For example, if your submission has a timestamp that is 32 minutes after
the grace period, 7% will be deducted from your assignment after grading;
if your submission has a timestamp that is 1 day, 6 hours, and 41 minutes
after the grace period, you will receive a score of zero
(and your assignment will not be graded).
The figure below summarize the deductions.
If you are unable to complete a homework assignment due
to illness or family emergency, please see the instructor as soon as
possible to get an extension. A doctor's note
is required as proof of illness or emergency.
In general, when you get sick,
it's best to see a doctor and get a note just in case you may need it later.
[BC: next few paragraphs copied from the homeworks
Modifications after Deadline
You are allowed to submit modifications via
e-mail to the instructor, within 24 hours
of the submission deadline.
One line (128 characters max) of change is defined as
one of the following:
where x is a line number and y is a specified file.
The first 3 lines of modifications are free
of charge. Additional modifications cost 3 points per
- Add 1 line before (or after) line x of file y
- Delete line x of file y
- Replace line x of file y by 1 line
Afterwards, additional modifications cost 12 points
per line until 7 days past the submission deadline.
After 7 days past the submission deadline, an additional
modification costs 30 points per line.
Please note that this applies to source code, Makefile, and README files.
Please note that the number of points deducted mentioned above
is based on a 100-point scale.
Two midterm examinations and a final examination will be given.
They will cover the lectures, readings, labs and homeworks.
The coverages of the two exams will not overlap.
The dates for these exams are posted near the top
of the class home page.
Any scheduling conflicts regarding the midterm exam date must
be resolved with the instructor at least two weeks
before the exam date.
The date of the final examination is firm and cannot be changed.
The exams are usually closed book, closed notes, and closed everything (and no "cheat sheet").
Also, no calculators, cell phones, or any electronic gadgets are allowed.
There will be assigned seating.
The grading breakdown is as follows:
Final grades for the course will follow this scale:
||% of Final Grade
We use a fixed grading scale in this course so that we can encourage cooperation and friendly association amongst students.
|95% or higher
Pleaes also note the following:
- Your assignments are your own work! No group assignments are allowed
or will be tolerated. You are free to talk to other students about
assignments but no actual material (files, code fragments, etc.) should
be shared or copied. We will act harshly at any sign of copying.
- We will not assign incompletes unless it is
for a documented medical reason (in accordance with USC policy).
Note From A Doctor
Recently, there has been a change in the policy at the
Student Health Center regarding giving a "note from the doctor"
to you to bring to a faculty
member so that you can be execused from deadlines. Basically,
they will not give you such a note any more.
What they would give you is an Authorization for Disclosure
of Medical Information form. With this form, you give them
permissions to discuss your illness with me.
So, if you visit a doctor at the Student Health Center,
please make sure you fill out one of these forms, check the
"limited discussion with faculty" checkbox, get it stamped,
signed, and dated by someone there (a clerk/receptionist
would sign at the "witness" line), and bring it back to me.
This would satisfy the "note from a doctor" requirement so
that you can get an extension.
If you visit a doctor somewhere else, please either bring a
"note from the doctor" or a similar authrozation letter so
I may contact them.
All requests to change grading of homework or
exams must be submitted in writing within two weeks
of the time the initial grade was given. Requests must be specific
and explain why you feel your answer deserves additional credit.
A request to re-grade an assignment can result in the entire assignment
being re-evaluated and as a result the score of any part of
the assignment be increased or lowered as appropriate.
in order to be eligible for regrades,
you must write your
entire exam in
The instructor's office hours are held several times a week for one hour each.
If you are not available during the designated time for office hours,
you are always welcome to make an appointment (and reserve a timeslot)
to see the instructor.
You are strongly encouraged to come see the instructor if you
are stuck with the a programming assignment. Don't wait till
the deadline gets close.
No extra credit assignments will be given for this class. So, there
is not need to ask. Try your best from the beginning!
Implicit Student Agreement
All work including homeworks, programming
assignments and exams must be that of the individual student. It is often
productive to study with other students. However, if any portions of homeworks
or programming assignments are found to be shared between two (or more)
students, zero credit will be given to all students concerned and all students
will be disciplined. This policy is in the interest of those students who
do their own work, which hopefully applies to all of you in this class.
In this class, we will use sophisticated automated program checkers
to detect cheating. Be aware that the program checkers have
demonstrated very good results and are widely used within the
Any student caught cheating will be given zero credit and will be disciplined.
It is the students responsibility to submit their assignments in time.
Students are expected to be familiar with programming in
C/C++ on the UNIX platform. No special assistance or
consideration will be offered if your background is inadequate.
The instructor must treat all students equally and cannot
give special treatment to any particular student.
Therefore, please do not ask special favors from the
instructor because of your circumstances.
This may seem unfair to you because you believe that your
circumstances are special (understandably, everone
does). But the rule the instructor must follow is that whatever
he offers you, he must offer to the entire class.
Auditing is not permitted for this class.
(The resources below are provided for your information.
Please note that the instructor has not read most of them.
Please use these resources at your own risk!)
- C Programming
(by Steve Holmes at the University of Strathclyde in Glasgow, England)
- includes notes on make, separate compilation,
file I/O, etc.
tutorial (at Indiana University)
- Steve's Software Trek
(by Steve Karg) - includes some useful C/C++ source code for string
manipulation, INI file manipulation, etc.
- C Examples -
lots and lots of sample C code for basic stuff.
- C/C++ at USC
from USC ITSWeb