UCR CS 141: Intermediate Data Structures and Algorithms

Winter Quarter, 2009





Lecture Schedule   Lab Session Topics  Email list   Turnin   Grade mapping  Previous offerings 

Overview

CS 141 introduces what many say is the core of Computer Science: data structures like graphs, and problem solving techniques. This material is essential in almost all of our upper-division courses. This is really the "science" in Computer Science!

CS 141. Intermediate Data Structures and Algorithms. (4) Lecture, three hours; laboratory, three hours. Prerequisite(s): CS 014 with a grade of "C-" or better; MATH 009C or MATH 09HC; MATH 111; proficiency in C++. Explores basic algorithm analysis using asymptotic notations, summation and recurrence relations, and algorithms and data structures for discrete structures including trees, strings, and graphs. Also covers general algorithm design techniques including divide-and-conquer, the greedy method, and dynamic programming. Homework and programming assignments integrate knowledge of data structures, algorithms, and programming.
Note: Students receiving less than a C- in the CS 14 prerequisite will be dropped automatically a few weeks into the quarter, as the course relies heavily on basic knowledge of and skills in data structures, discrete mathematics, and programming.

Basic information

Syllabus : PDF
Instructor : Tao Jiang (jiangATcs.ucr.edu)
Office hours: M 5-6pm and W 2-3pm. Office: EBU II 336.
Teaching Assistants and Office Hours: Monik Khare (mkhareATcs.ucr.edu), Office hour: Th 1-2pm.
Sima Lotfi (lotfisATcs.ucr.edu), Office hours: Fr 10-11am.
Office hours are held in EBU II 110.
Lecture: TuTh 2:10-3:30pm, SPR 2365. Labs: Sec 21, M, 11:10-2pm, EBU II 226, Monik Khare
Sec 22, M, 2:10-5pm, EBU II 226, Sima Lotfi
Academic Excellence Workshop (AEW): Tu 3:40-4:30pm, EBU II 103, Robert Halstead
Text Book: Introduction to the Design and Analysis of Algorithms, 2nd edition, 2007 by A. Levitin.
Lecture Notes: The following slides provided by the author of the textbook (with some extensions and updates by Prof. Jiang) will be used in class:
Introduction to algorithms and review of data structures
Asymptotic notations and analysis of algorithms
Morr recurrence relations and analysis of recursive algorithms (from CLRS)
Bruce force algorithms
The divide-and-conquer method
Decrease-and-conquer algorithms
Transform-and-conquer algorithms
Dynamic programming
Greedy and graph algorithms
Space-and-time tradeoffs and string matching
More on string matching, the KMP algorithm (from CLRS)
Lower bound for sorting

You may find a short tutorial on recurrence relations and a tutorial on C++ programming style useful.

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 in lecture
3 hours/week in lab
6 to 10 hours/week doing individual study (readings, homeworks, programming assignments, preparation for lectures, etc).
Please don't 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.

Lecture schedule

See the syllabus. Read the book before lecture! 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. The schedule is subject to change as the quarter progresses.

Lab session topics (tentative, will be adjusted according to progress)

General course features and policies (please read these carefully)

Lab guidelines (please read these carefully)

Electronic assignment turn-in

Grade mapping

The following mapping shows how your overall numerical scores will be translated into letter grades at the end of the quarter:

Course email list

Course mailing list (send mail now or access the archive): Be sure to sign up to receive important announcements, which will be madeonlythrough 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).

Previous course offerings' web pages

Additional Resources