UCR CS 14: Introduction To Data Structures & Algorithms

Summer 2003 (Session I): June 23 - July 25

Programming Points
Assignments
Exercises
Lecture Schedule
Labs
Style Guide
Current Grades

Overview

CS 14 builds on the basic tools provided in the CS 10-12 sequence by introducing mature programming concepts: abstraction, reusability, efficiency, ADTs, Big-O notation, just to name a few. CS 14 builds heavily on basic C++ skills to allow for more advanced software development.

Catalog description: CS 14. Introduction to Data Structures and Algorithms. (4) Lecture, three hours; laboratory, three hours. Prerequisite(s): CS 12 with a grade of "C-" or better; MATH 009A or MATH 09HA; proficiency in C++. Topics include basic data structures such as arrays, lists, stacks, and queues; dictionaries including binary search trees and hashing; priority queues (heaps); introductory analysis of algorithms; sorting algorithms; and object-oriented programming including abstract data types, inheritance, and polymorphism. Also covers solving complex problems through structured software development.

Note: Students receiving less than a C- in the CS 12 prerequisite will be dropped automatically during the quarter.

Basic Information

Instructor:
Titus Winters (titus@cs.ucr.edu)
Monday - Wednesday, 1pm-2pm, Surge 281 (Location may change)

Teaching Assistant:
Shaohui "Steve" Chen (schen@cs.ucr.edu)

Lecture:
MTWTh, 5:30-7pm, 2355 Sproul Hall

Lab:
Lab attendance is required. Attendance will be taken at the beginning and end of every lab section, and points awarded accordingly. During lab sections, you are expected to be working on material related to this course.

Time & Place: T Th, 2-5pm, 172 Surge Building

Books:
Required: Data Abstraction And Problem Solving With C++: Walls and Mirrors, Frank M. Carrano and Janet J. Prichard, 3rd ed., 2002 Addison-Wesley.

Please consult the errata pages for the book 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 book's web site.

Final Exam:
Friday, July 25, 3:30-5:30pm

Course Grading:
Letter grades will be assigned roughly according to the standard 90/80/70/60 scale out of 100 percentage points overall, with a 90 corresponding to an A, 80 to a B, and so on. +/- grades will be given out as appropriate. The course is divided into two individual components:

65% - Lecture (Theory) Component: Represents your ability to reproduce simple information on demand, think abstractly, and answer questions about relevant course learning.
- 15% quizzes/lecture homeworks - There will be 4 short (15-20 minute) quizzes during the session. Quizzes will primarily cover material learned in lecture and lab during the previous week. Regular quizzes will be held on Monday at the beginning of lecture. There may also be a number of "reading quizzes" held at the instructors discretion covering the assigned reading material. Students must therefore bring paper and a writing implement to every lecture.
- 20% midterm - There will be a midterm held on Thursday, July 10th. It will cover all the material presented in the course up to that date, as well as important material from previous CS courses (basic C++ concepts).
- 30% final - The final exam will be held on Friday, July 25th. It will be a cumulative exam, covering all of the material presented in the course both in lab and lecture.
35% - Lab (Programming) Component: Represents your ability to implement the concepts presented in class or on the assignment webpages in C++. This represents your ability to use the tools that you have been taught.
- 8% lab practical exams - There will be 2 lab practical exams held during the quarter. Notice of the exam dates will be given in lecture and on the mailing list at least 3 days in advance. Anyone unable to attend the exam is required to schedule an alternate time with the instructor. Lab practicals will be a short, closed book, no assistance programming (30 minute) assignment to ensure that you are absorbing the programming material.
- 20% programming points - Over the course of the quarter you need to acquire 200 programming points to earn full credit in this portion of your grade. More information on the CS 14 programming point system can be found here.
- 7% style - 7% of your course grade will be given to the average of your style score on at-home assignments. That is, if you do only 2 home assignments, and receive 0 style points on the first and 10/10 on the second, you will be given 3.5% (7% * (0 + 10 points earned)/ 20 points possible). If you then turn in a 3rd home assignment and again recieve full style points, your style score will then go up to 4.7% (7% * (0 + 10 + 10 points earned)/30 points possible).

Assignments

For Tuesday, June 24th: Read the first half of Section 9 regarding Big-O notation/algorithm efficiency
Theory Homework #1 Ranking rates-of-growth of functions. Due Thursday, June 26th.
For Wednesday, June 25th: Caranno (the course text), pages 112 - 131. For those of you without the text, this is covering Abstract Data Types, defining them, how to specify them (the operations that each ADT has), and the ADT List (which we will come back to over and over again, like sorting.)
For Thursday, June 26th: Caranno, pages 418-424 (Iterators), Chapter 6 (ADT Stack)
For Monday, June 30th: Review Chapters 6-7 (Stacks and Queues), Read the second half of Chapter 9 regarding Sorting Algorithms.
For Wednesday, July 2nd: Read Chapter 10 (Trees). This covers the general notion of a Tree and also Binary Search Trees.
For Thursday, July 3rd: Read Wagner's slides on Trees from last quarter. It is Lecture 6, available here.
For Monday, July 7th: Read the first half of Chapter 12 (balancing binary trees).
For Tuesday, July 8th: Complete problems 10.4 10.5 10.7 10.23 10.24 from the text. Make sure not to do the Self-Test set, the proper set begins on page 559.
For Wednesday, July 9th: Read pages 594 - 609 about Heaps.
For Tuesday, July 15th: Read pages 656 - 677 about Hash Tables.
For Monday, July 21st: Read pages 690 - 702 about representing graphs and graphs in general.

Lecture Examples

Binary Tree from lecture on July 2nd/3rd
hashing.cc hashing.h from lecture on July 15th/16th.
STL Map
STL List
STL Set from lecture on July 23rd.

Lecture Schedule

Subject to change as the quarter progresses I will announce at the end of each lecture the reading assignment for the following day. Doing the reading greatly benefit your ability to follow along in lecture, which will directly correlate with a higher grade in the course.

Week 1, first half: Introduction, course information, abstraction. Abstract Data Types (ADTs), Review of Recursion, Introduction to Complexity Theory & Big-O Notation.
Week 1, second half: ADT List, array, STL, and pointer implementation. Iterators. ADT Stack, ADT Queue.
Week 2, first half: Quiz #1, Sorting (SelectionSort, BubbleSort, InsertionSort, MergeSort, RadixSort)
Week 2, second half: Trees: Definitions, properties, traversal.
Week 3, first half: Quiz #2, Balanced Binary Trees, (Splay Trees?)
Week 3, second half: Midterm, Binary Heaps: definitions, properties, tree, array and list implementation.
Week 4, first half: Quiz #3, Non-positional ADTs: Hash Tables
Week 4, second half: More hash tables, hash functions.
Week 5, first half: Quiz #4, Graphs/Graph representations. Using common STL types.
Week 5, second half: Special topics. Final review
Week 5, FRIDAY Final.

Labs

Quizzes & Tests

Policies (Please read these carefully)

Grades: Current grades will be posted here as frequently as possible. It is your responsibility to ensure that your grades are correct.
Operating system: All homework assignments and exercises are to be developed under Linux. Questions on how to move assignment files from Windows to Linux will not be answered. Further, if we have reason to suspect that assignments were developed under Windows, your assignment will be docked 25%.
Compiler flags: In an attempt to wean people out of bad/nonstandard programming habits, the following compilations flags will be used with g++ for all submissions:
```
 -W -Wall -Werror -pedantic
```
Any submission that does not compile with these flags will be sent back for resubmission, or docked 10%.
Material covered: Lecture doesn't cover all required material, you are responsible for retaining knowledge from the required reading and from the lab sessions.
Assignment Proficiency: For all assignments made up to the last week of the course, a grade of less than 50% functionally will cause the assignment to be sent back for corrections.
Academic dishonesty: Cheating will be strongly punished, most likely with an F in the course and an official letter in your student file. All incidences of cheating will be brought up with the Dean of Academic Affairs.

You may report cheating anonymously at: https://www.cs.ucr.edu/cheating/. Honest students remember: if you get the cheaters expelled, they won't be setting the curve.
Assignment Submissions: ALL code in an assignment submission must represent your own original work. Copying from any sources (including but not limited to the Internet, books, past or current students) is strictly prohibited. Programming is a skill that takes a lot of effort to master, and can only be done through practice. Doing it yourself requires that you learn to figure things out on your own, which is one of the most important aspects of programming.

General discussion of assignments with other students is allowed. The test for when you have gone too far in your collaboration is when any student in the discussion starts speaking in code, or anyone writes down something that looks like code.

Remember that you are not allowed to show your code to any student in this course, nor should you be asking to see their work.

We have sophisticated code-comparison tools that are quite good at catching cheating. Don't try to beat them. Just do your own work.
Regrade Policy: Regrade requests must be submitted physically in writing within one week of the graded material being given to you. The entire exam/assignment may be regraded, so your grade may go up or down as a result of regrade requests.
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.
Cell phones: During lectures and lab sessions, please turn off your cell phone. We reserve the right to penalize the grade of repeat offenders. If there is anything so pressing as to require your phone to be on during class, you probably don't need to be in class.
Lab attendance: To recieve full credit for lab, you must attend for the full 3 hour period. If you finish the required material early, work on a programming assignment or read the text. Surfing the Internet or chatting with friends are not valid uses of lab time.
Style: Course style guidelines are posted here
Time Requirement: I expect each and every student that passes this course to spend 25 - 30 hours / week on the course, including time spent in lecture and lab. Lecture and lab constitute 12 hours / week, leaving 13-18 hours to be spent at home working on programming assignments and doing the required reading.

Course email list

CS 14 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).