UCR CS 141: Intermediate Data Structures and
Algorithms
Spring Quarter 2003
Lecture Schedule Lab
Schedule Email list
Turnin Grades Previous
offerings
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 112; 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.
UCR course schedule
UCR course
catalog Note: Students receiving less than a C- in the CS 12
prerequisite will be dropped automatically a few weeks into the quarter.
Instructor :
Sitanshu Kumar (sitanshu@cs.ucr.edu)
Office hours: Mon/Wed 1:00-2:00 Office:
Surge Bldg. 359.
Teaching Assistants and office hours:
Rui Jiang (rjiang@cs.ucr.edu),
Office hours: F 10-11
Ilker Basaran (ibasaran@cs.ucr.edu),
Office hours: M 10-11
Yu Luo (yuluo@cs.ucr.edu),
Office hours: T 10-11
Office hours are held in
Surge Bldg. 282.
Lectures:
MWF 2:10-3:00, STAT B650.
Labs:
Sec 21, M, 6:10-9:00, SURGE 171
Sec 23, T, 11:10-2:00, SURGE 171
Sec 24, T, 2:10-5:00, SURGE 171
Sec 26, F, 11:10-2:00, SURGE 171
Books:
Algorithm Design (Foundations, Analysis, and Internet Examples) by
Michael T. Goodrich and Roberto Tamassia, Wiley.
Lecture Slides:
All lecture slides are available here
Course grading:
The course is divided into two grading components, combined as a weighted sum:
65% Lecture component:
15%: Quizzes/Homeworks
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
Letter grades are roughly assigned according to the usual 90/80/70/60 scale:
90% and above corresponds 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+ may be given to students in the high 90's who also have turned in all
required material. On occassion scores may be curved, but always to the benefit
of the students, never the other way :-).
To ensure minimum competency in successive courses requiring a C- or better in
this course, 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 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,
lab preparation, 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.
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. AD below refers to the Algorithm Design textbook.
-
Week 1 : (AD 1) - Proofs: what is a proof, proving techniques
(constructive, contradiction, induction, disprove by example). Big O notation
(definitions, proofs).
(AD 2, AD 3.1, 3.2) - Basic data structures review (lists, trees, stacks,
queues, hashing), hashing, abstract data types, elements of good object
oriented programming.
-
Week 2 : (AD 4.1-4.4, AD 5.1) - Sorting review (brief discussion of
recurrence relationships). Greedy algorithms (e.g., fractional Knapsack)
Quiz 1
-
Week 3 : (AD 5.2) - Divide and Conquer (intro): Recurrence
Relationships: the three methods, applications to merge sort. Divide and
Conquer: Matrix Multiplication and Integer Multiplication.
-
Week 4 : MIDTERM 1 (including recurrence relationships and concept of
Divide and Conq.) (Sample Questions)
(AD 5.3) - Dynamic Programming: 0-1 Knapsack, Matrix chain multiplication
-
Week 5 : Dynamic Programming (cont).
(AD 6.1-6.3.1) - Graphs (intro, representations, DFS).
-
Week 6 : (AD 6.3.3) - Graphs (BFS).
Quiz 2
(AD 6.4, 6.4.2, 6.4.3, 6.4.4) - Directed graphs.
-
Week 7 : (AD 7.1, 7.2) - Weighted graphs (shortest paths). Weighted
graphs (all pairs shortest paths).
-
Week 8 : (AD 7.3.1, 7.3.2) - Weighted graphs cont. (minimum spanning
trees).
Quiz 3
(AS 9.1) - String matching, the KMP algorithm.
-
Week 9 - String matching (cont).
(AD 8.1 8.2 - for 8.2.4 no proofs) - Maximum Flow (intro).
-
Week 10 Maximum Flow (cont).
Misc - Review
Schedule is subject to change as the quarter progresses.
Topics to focus for Final
-
Week 1: Recursive functions: Fibonnaci
Debugging and Testing in C++;
Measuring the time of a program: the meaning of exponential execution time.
In-lab excercises
At-home prog 1
-- Linked lists
-
Week 3: Hashing
hashing time performance of good versus bad hashing
In-lab exercises
-
Week 4: Recursive algorithms: sorting: mergesort, quicksort
Recurrence relationships examples
implement recursive programs
In-lab exercises
At-home prog 3
-
Week 5: Study habits - Review Dynamic programming and new examples
In-lab exercises
-
Week 6: Graph representations: insertion deletion etc and their O()
performance
In-lab exercises
-
Week 7: Review BFS and DFS
(use of BFS in modeling a multi-choice problem i.e. a puzzle or game)
In-lab practical.
Implement a graph with just nodes and pointers At-home prog 4: TBA
In-lab exercises
Take Home
Assignment 4
-
Week 8: Shortest paths and all pairs
In-lab exercises
-
Week 9: Review string matching
In-lab exercises
-
Week 10: Review Maximum Flow - Course Review
In-lab exercises
Subject to change as the quarter progresses.
-
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 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
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. 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, 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).
-
Homework and lab reports: All turned-in assignments will be
turned in electronically. Each file
should begin with our 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. To encourage these important college
study habits, we may give a few simple pop quizzes during the quarter, at any
time during lecture.
-
Students are expected to attend the lab sessions in their entirety. You'll have
in-lab exercises, discussions, and possibly practical exams. If you finish
early, work ahead or on other course-related material.
-
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.
Quiz1 , Answers for
Quiz1
Quiz2 , Answers for
Quiz2
Quiz3 , Answers for
Quiz3
Midterm Qustions ,
Answers for Midterm
Solutions for Take-Home Assignment 1
Solutions for Take-Home Assignment 3
View All Grades
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).