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)

Week 1 (i.e. the week of Jan. 5):
Introduction of TA; class accounts and mailing list
Debugging and testing in C++; working on Linux
Review of linear, tree and graphical data structures
Counting execution time of a program
Top-down design of algorithms; pseudo-code
Asymptotic (big-O, Theta) analysis of running time
More details

Week 2:
Preview the first homework
More asymptotic analysis of algorithms
Treatment of for-loops using summation
Pointers and recursive algorithms/programs
More details

Week 3:
Preview the first programming assignment
Address questions concerning the first homework
Recurrence relations and analysis of recursive algorithms
Recursive programming - computing the Fibonacci function
More details

Week 4:
Preview (briefly) the 2nd homework
Address questions concerning the first programming assignment
Exhaustive search methods for Traveling Salesman and Knapsack problems
Review and analyses of Mergesort and Quicksort
More details

Week 5:
Review the first homework solutions
Address questions concerning for the 2nd homework
Address questions concerning for the midterm test review
Implementation of binary tree traversals
Some examples of Strassen's multiplication algorithms
More details

Week 6:
Review the first programming assignment solutions
Review the second homework solutions
Review data structrues for graphs and digraphs
Implementation and applications of DFS and BFS algorithms
More details

Week 7:
Discuss the second programming assignment
Review the midterm solutions
Some examples of AVL tree and 2-3 tree constructions and operations
Implementation of Heapsort
More details

Week 8:
Questions arising in the second programming assignment
Preview the third homework
Give an example of Floyd's algorithm
Implement the dynamic programming algorithm for Knapsack
(Optional) Design an O(VE)-time transitive closure algorithm
More details

Week 9:
Review the second programming assignment solutions
Questions arising in the third homework
Give an example of Dijkstras' shortest path algorithm
Can you give a counterexample to Dijkstras' algorithm when negative weights are allowed?
Write an efficient MST algorithm for graphs with edge weights that are either 1 or 2
More details

Week 10:
Review the third homework solutions
Review for the final exam
Some examples of the KMP algorithm for string matching
Comparison of KMP and BM
Implementation of KMP
More details

General course features and policies (please read these carefully)

Material covered: Lectures don't cover all required material, which also appears in the text and reference books and may be covered only in the lab sessions.
Academic dishonesty: Cheating will be strongly punished (typically with an F in the course). Please read carefully the UCR's official policy on academic dishoney 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 solve programming problems 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).

A couple more notes. 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.
Regrade policy: Regrade requests must be submitted in writing and within a specified period. The entire homework/test/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. To have a homework/test regraded, communicate with the TA(s) who graded the involved questions. For assignments, send email requests to the CS141 grader account (xxx@cs) with detailed explanations. Recording errors should also be pointed out to TAs or the instructor before the last class.
Final grades: Per university policy, changes to your final grade will be made only in the event of a clerical error. Asking your instructor how far you were from a cutoff and what extra work you can do to improve the grade is not appropriate.
Communicating with the instructors and TAs: When sending electronic mail to the instructors or TAs or graders, please include your full name, student ID number, and UCR email address, so that we may properly identify you (remember, many students have similar names). 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. During exams, cell phones must not be visible (e.g., store them inside a backpack).
Programming assignments: All programming assignments will be turned in electronically via CS141's Moodle webpage. Each file should begin with a report template header. Source code should comply with professionally accepted coding standards. In particular, all 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, but they are not a replacement for an explanatory section. 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. So don't 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. Feel free to ask questions.

Lab guidelines (please read these carefully)

Students are expected to attend the lab sessions in their entirety. The lab sessions typically consist of tutorials, discussions, reviews, practical exercises/tests, and time for students to work on homes and programming assignments.
During lab tutorial/discussion/review time, students should not use the computers. Ideally, students would move their chairs to the whiteboard area.
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.

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:

90+ -> A+
85+ -> A
80+ -> A-
77+ -> B+
73+ -> B
70+ -> B-
67+ -> C+
63+ -> C
60+ -> C-
57+ -> D+
53+ -> D
50+ -> D-
49- -> F

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

UCR CSE department's Resources For Students page.
GNU Emacs Reference Card (pdf, 80 KB).

Link to the CS 14 prerequisite course.