UCR CS 14: Introduction to Data Structures And Algorithms

Spring Quarter 2003: March 26, 2003 - June 13, 2003

Lecture Schedule	Lab Schedule	Downloadable Material
Electronic Turn-in	Grades	Course Email List
Anonymously Report Suspected Cheating	Anonymously Provide Comments/Suggestions	Previous CS14's

Overview

: In CS 14, you'll you'll learn how to utilize and design reusable abstractions to lift software development to a higher level. You'll also learn about fundamental data structures and algorithms that are widely applicable. Hopefully you'll have fun too!; 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 a few weeks into the quarter.

Basic information

Instructors and office hours:

Wagner Truppel (wagner@cs.ucr.edu)

: Tue & Thu, 3:00 pm - 4: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:

Mirella Moro (mirella@cs.ucr.edu)

Mon	1:00 pm	-	2:00 pm
Tue	6:40 pm	-	7:30 pm
Thu	10:00 am	-	11:00 am

Held in Surge Bldg. 282.

Hongwei Ji (hji@cs.ucr.edu)

Steve Chen (schen@cs.ucr.edu)

Lectures:

Section 1:

Tue & Thu

11:10 am

12:30 pm

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:	Mon	6:10 pm	-	9:00 pm	in	Surge Bldg. 170.
Section 22:	Wed	2:10 pm	-	5:00 pm	in	Surge Bldg. 170.
Section 23:	Thu	11:10 am	-	2:00 pm	in	Surge Bldg. 170. CANCELLED
Section 24:	Thu	6:10 pm	-	9:00 pm	in	Surge Bldg. 170. CANCELLED
Section 25:	Fri	8:10 am	-	11:00 am	in	Surge Bldg. 170.
Section 26:	Fri	11:10 pm	-	2:00 pm	in	Surge Bldg. 170.

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.; For optional books, visit the Additional Resources section below.

Extra (Optional) Readings:

: In addtion to the required readings, I've made available photocopies of certain book chapters which I believe have clear presentations of some of the material to be covered in the course. This is not mandatory reading. This extra material is accessible from the UCR Printing and Reprographics Office on campus, next to the UCR Bookstore's entrance. Just ask for the CS 14 Readings.

Course grading:

Letter grades are roughly assigned according to the usual 90/80/70/60 scale out of 100 total course points, with 90 and above corresponding 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+'s will be given to students in the high 90's who also have turned in all required material and many of the challenge in-lab excercises. The course is divided into two grading components, combined as a weighted sum to total 100 points:

65% Lecture component:

15%	Quizzes and/or homework assignments.
20%	Midterm.
30%	Final.

35% Lab component:

15%	In-lab programming exercises, attendance, participation, and adherence to coding standards.
15%	Take-home programming assignments.
5%	In-lab practical exams.

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+. A C- in either component corresponds to roughly 70% of the total points for that component.

Approximate Time Requirements:

This is a four-unit CS 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. Computer Science and Engineering are challenging disciplines requiring extensive time to master.

Course evaluation:

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

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

Lecture schedule

Subject to change as the quarter progresses.

Please note that even though almost all the chapters in Carrano'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. Reading ahead is one of the most effective ways of doing better in class -- you'll be amazed how much more comprehensible and useful the lectures will be.

Week	Topics	Readings
1 Mar 31 - Apr 4	Overview of Data Structures and Algorithms. Data Abstraction: Interface x Implementation; Abstract Data Types. Review of Recursion; Introduction to Complexity Theory.	Textbook chapters 3 (Data Abstraction), 2 and 5 (Recursion), and the first section of chapter 9 (Efficiency of Algorithms).
2 April 7 - Apr 11	Review of advanced C++ topics: Templates, Exceptions, Inheritance, Polymorphism	Textbook appendix A and chapter 8.
3 Apr 14 - Apr 18	ADT List, array and pointer implementations Iterators, List iterators ADT Stack, ADT Queue Extra material: the SquareList data structure	Textbook chapters 4 (Linked Lists), 6 (Stacks), and 7 (Queues).
4 Apr 21 - Apr 25	Quiz 1 (Tue, Apr 22) Sorting I: SelectionSort (Min/Max), BubbleSort (Naive/Smart), InsertionSort, MergeSort	The second section of chapter 9 (Sorting Algorithms).
5 Apr 28 - May 2	Trees I: definitions, properties, tree traversals Midterm (Thu, May 01)	Textbook chapter 10 (ADT Binary Tree).
6 May 5 - May 9	Trees II: Binary Trees Binary Search Trees: definitions, properties Balanced BSTs: AVL trees, single and double rotations	Textbook chapter 10 (ADT Binary Tree), and the first section of chapter 12 (Balanced Search Trees).
7 May 12 - May 16	Binary Heaps: definitions, properties, Min/Max Tree representation, Array and Tree implementations	Textbook chapter 11 (Tables and Priority Queues).
8 May 19 - May 23	Quiz 2 (Thu, May 22) Priority Queues Sorting II: HeapSort, QuickSort General analysis of Sorting	Textbook chapter 11 (Tables and Priority Queues).
9 May 26 - May 30	ADTS in perspective: Positional/Non-positional ADTs ADT Set, ADT SortedArray, ADT SortedList ADT Map
10 Jun 2 - Jun 6	Quiz 3 (Tue, Jun 03) Hash tables and hash functions	The second section of chapter 12 (Hashing).
Tue Jun 10	Final Exam: 3:00 pm - 6:00 pm

Lab schedule

Subject to change as the quarter progresses.

Home programming assignments are due at 8:00 pm on the due date, unless indicated otherwise.

Week	Topics/Activities	Assignments
1 Mar 31 - Apr 4	Login assignments. How to send and read email using Pine. How to turn in your work electronically. Basic UNIX commands, Emacs, gcc.	lab 1.
2 Mar 7 - Apr 11	Implementing a simple ADT: ADT Counter. Debugging techniques.	lab 2.
3 Apr 14 - Apr 18	Testing	lab 3.
4 Apr 21 - Apr 25	Practical 1: Lists	lab 4.
5 Apr 28 - May 02	Course evaluation Midterm review	lab 5.
6 May 05 - May 09	Sort algorithms performance	lab 6.
7 May 12 - May 16	Trees	lab 7
8 May 19 - May 23	Heaps	lab 8
9 May 26 - May 30	No in-lab exercises. TAs will be in the labs for helping with homework 4.
10 June 2 - June 6	Finals review

Material available for download:

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!
Be aware that a subset of exams may be photocopied, for comparison with exams submitted for regrades. Also, be aware that lying to an instructor in order to be able to makeup a missed exam or in other ways to obtain a better grade can be treated as academic dishonesty. During exams, cell phones must be stored away in a place not visible (e.g., inside a backpack).
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, please turn off your cell phone.
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.
CS14 Frequently asked questions - FAQ

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, discussions, and possibly practical exams. Work ahead or on extra course-related material if you finish early.
During lab discussion time, students should not use the computers. Ideally, students would move their chairs to the whiteboard area.
Prepare for lab before arriving.
To reduce disruptions and provide for the best educational environment, all persons in lab during scheduled lab time should be formally registered in that section. In general, no swapping sections and no unregistered people in the lab are allowed, even if there are extra computers.

Grades

Scores as of 06/10/2003 (midterm, quizzes, lab, practical, all homework assignments).

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

Additional Resources

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.

	My own	Others
Lec 1:	pdf / pps	-
Lec 2:	pdf / pps	-
Lec 3:	pdf / pps	-
Lec 4:	pdf / pps	-
Lec 5:	pdf / pps	-
Lec 6:	pdf / pps	-

	Assignment	Due Date
1:	Vignere Cipher	Sunday, April 20, 8pm
2:	ADT Sorted List	Wednesday, May 7, 10 pm
3:	Stacks	Monday, May 19, 8 pm
4:	Ternary search trees	Wednesday, June 4, 8 pm

Lecture slides:

Demos:

Home programming projects:

Quizzes:

Exams: