UCR CS 14: Introduction to Data Structures and Algorithms

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

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:

Peter Fröhlich (phf@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. 341.

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:

Honomount Rawat (hrawat@cs.ucr.edu)

: Tue, 1:00 pm - 3:00 pm.

Dale Kim (dkim@cs.ucr.edu)

: Mon, 11:00 am - 12:00 pm.; Wed, 12:00 pm - 1:00 pm.

Wei Wang (wangw@cs.ucr.edu)

: Wed, 4:00 pm - 5:00 pm.

Ashish Sharma (asharma@cs.ucr.edu)

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

Held in Surge Bldg. 282.

Lectures:

Section 1:	Tue & Thu	5:10 pm	-	6:30 pm	in	Humanities & Social Sci. Bldg. 1501,	taught by Wagner Truppel.
Section 2:	Tue & Thu	6:40 pm	-	8:00 pm	in	Statistics Bldg. B650,	taught by Peter Fröhlich.

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

Books:

: Required: Data Structures and Problem Solving Using C++, Mark Allen Weiss, 2nd ed., 2000 Addison-Wesley.; Required: The Practice of Programming, Brian Kernighan & Robert 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.; 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. In addition, the course is divided into two grading components combined as a weighted sum:

65% Lecture component:

15%	Quizzes.
20%	Midterm.
30%	Final.

35% Lab component:

15%	Weekly in-lab programming exercises, attendance, participation, and adherence to coding standards.
12%	Weekly out-of-lab programming excercises.
8%	Weekly homework.

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.

Detailed lecture schedule

Subject to change as the quarter progresses.

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

Date	Topics	Readings
Tue Jan 07	Introduction and Overview	W 1
Thu Jan 09	Abstract Data Types, Testing, Review of C++ Basics	W 2
Tue Jan 14	Arrays, C++ Templates and Exceptions, Array Implementation	W 3, 4
Thu Jan 16	Complexity, Basic Searching (linear, binary) and Sorting (bubble, selection)	W 6, 9.1, 9.2, 9.3, 9.8
Tue Jan 21	Lists [Quiz 1]	W 16, 17, 5.4
Thu Jan 23	Lists	W 16, 17, 5.4
Tue Jan 28	Trees	W 18
Thu Jan 30	Trees [Quiz 2]	W 18
Tue Feb 04	Trees	W 18
Thu Feb 06	Midterm Exam
Tue Feb 11	Sets, Basic Implementations	-
Thu Feb 13	Heaps	W 21
Tue Feb 18	Heaps	W 21
Thu Feb 20	Advanced Sorting (heap, merge, quick)	W 9, 21.6
Tue Feb 25	Binary Search Trees (basic) [Quiz 3]	W 19
Thu Feb 27	Binary Search Trees (balanced, AVL)	W 19
Tue Mar 04	Maps, Basic Implementations	-
Thu Mar 06	Hash Tables	W 20
Tue Mar 11	Hash Tables	?
Thu Mar 13	Review and Outlook [Quiz 4]	?
Tue Mar 18	Section 1 Final Exam: 7:00 pm - 10:00 pm
Thu Mar 20	Section 2 Final Exam: 7:00 pm - 10:00 pm

Detailed lab schedule

Subject to change as the quarter progresses.

In the table below, 'W' refers to Weiss' Data Structures and Problem Solving Using C++ while 'K&P' refers to Kernighan & Pike's The Practice of Programming.

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	Unix and C++ Basics	Read W 1, 2 and K&P 1. [lab 1]
2 Jan 13 - 17	Counter (interface/implementation, debugging, exceptions)	Read W 4 and K&P 5. Lab: Debugging. Home: Counter implementation. [lab 2]
3 Jan 20 - 24	Array (templates, testing)	Read W 3 and K&P 6. Lab: Test driver Home: Array implementation. [lab 3]
4 Jan 27 - 30	Basic Sorting (performance measurement)	Read W 6, 9.1, 9.2, 9.3, 9.8 and K&P 7. Lab: Bubble sort. Home: Selection sort, insertion sort, measurements. [lab 4]
5 Feb 03 - 07	List	Read W 16, 17, 5.4 and K&P 2. Lab: ListArray. Home: List implementation. [lab 5]
6 Feb 10 - 14	Tree	Read W 18 and K&P 4. Lab: Practical. Home: Binary Tree implementation. [lab 6]
7 Feb 17 - 21	Heap	Read W 21. Lab: none. Home: Heap implementation (min heap). [lab 7]
8 Feb 24 - 28	Advanced Sorting	Read W 9, 21.6. Lab: Simple heap sort. Home: Full heap and quick sort. [lab 8]
9 Mar 03 - 07	Binary Search Tree	Read W 19. Lab: Sorted List. Home: BST. [lab 9]
10 Mar 10 - 14	Hash Table	Read W 20 and K&P 2. Lab: Simple Hash Table. Home: Resizing Hash Table. [lab 10]

Material available for download:

Lecture slides:

	Wagner's
1:	pdf / pps
2:	pdf / pps
3-4:	pdf / pps
5:	pdf / pps
6:	pdf / pps

Assignments:

	Topic	Assignment	Archived code	Solution
1:	Warm-up [Christmas Tree/Forest]	pdf	-	-
2:	Debugging/Counter implementation	pdf	tar.gz	tar.gz
3:	Testing/Array implementation	pdf	tar.gz	pdf / tar.gz
4:	Sorting/Performance measurements	pdf	tar.gz	pdf / tar.gz
5:	Lists	pdf	tar.gz	pdf / tar.gz
6:	Practical / Trees	pdf	tar.gz	pdf / tar.gz
7:	Heaps	pdf	-	pdf
8:	Advanced Sorting / Performance	pdf	-	pdf
9:	Sorted Lists / Binary Search Trees	pdf	-	-
10:	Hash Tables	pdf	-	-

Quizzes:

	Questions	Solutions
[Entrance Exam] 0:	pdf	pdf
[Tue, Jan 21] 1:	pdf	pdf
[Thu, Jan 30] 2:	-	pdf (+ questions)
[Tue, Feb 25] 3:	-	pdf (+ questions)
[Thu, Mar 13] 4:	-	pdf (+ questions)

Exams:

Exam	Questions	Solutions
Midterm	-	pdf (+ questions)
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.
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, discussions, and possibly 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

: Please check carefully, and be sure to read the disclaimer!
Scores as of 02/12/03.
Scores as of 02/13/03.
Scores as of 02/19/03.
Scores as of 02/25/03.
Scores as of 03/07/03.
Scores as of 03/13/03.
Scores as of 03/22/03.
Scores as of 03/23/03.
Final grades.

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

UCR CS department's Online Documentation page.
UCR CS department's Cool Links and Resources For Students page.
GNU Emacs Reference Card (pdf, 80 KB).
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.