CompSci 100e, Spring 2011, Prof. Rodger
Program Design and Analysis II
A continuation of Computer Science 6 and ENG 53. Object-oriented design and
programming using Java emphasizing abstract data types and
their lower-level implementations. Advanced data structures including
balanced trees, hash tables, graphs. Intuitive and rigorous analysis of
algorithms. We use the
- REVIEW SESSION: OPTIONAL, FRIDAY 1:15-2:30pm, LSRC D106,
(this room is one floor below Prof. Rodger's office).
- NOTE THESES HOURS are SUBJECT to CHANGE. Please check
before walking over.
- Week of April 25, 2011 - office hours this week
- Wednesday: Prof. Rodger, 1:15-2:45pm
- Thursday: Prof. Rodger 10-2:45pm
- Friday: Prof. Rodger - likely 11-1pm, then to review session (see above)
- Friday: Bala Office hours - 2:30-6pm North 007
- Week of May 2, 2011- Prof. Rodger office hours this week
- Monday: 2-3, 3:45-5:30pm
- Tuesday: 12:30-2:45pm
- Wednesday: 10:30-2:45pm
- The test is cummulative. Topics from Exam 1 and Exam 2 are
important and a big part of the exam, such as maps, sets, ArrayLists, Linked lists, Trees,
stacks, queues, priority queues, etc.
- I will highlight the Important Topics we have covered since Exam 2.
- Know difference between directed and undirected graph
- Know how to represent a graph (array of linked lists, 2d array,
- Understand how to traverse a graph and print out all the nodes
- depth first search, breadth first search
- understand Dijkstra's shortest path algorithm, how does it work?
- How do you represent a general tree?
- Balanced Trees: Red-Black Trees
- Understand the idea behind red-black trees. They balance themselves
coloring, recoloring and rotations. There are 5 properties for a red-black
tree. These have to be maintained during insertions and deletions.
Fixing up the tree to rebalance takes O(1) time.
- A red black tree is worst case of height 2 log n, so an insertion
and/or deletion are worst case O(log n) operations.
- You will not have to insert nodes into a red-black tree so you do not
have to understand the insertion other than it uses recolorings and 1 or 2
rotations with each insertion.
- Sorting algorithms and analysis
- Understand the analysis and how the sorts work for n squared sorts:
Selection sort and bubble sort. How many swaps do they do, what is their
worst case time? Think about what happens if you run them on different
types of data: reverse order, already sorted, random order.
- Understand how Heapsort works. What is the big-Oh running time?
(this is repeatedly applying deleteMin to a min heap).
- Understand the general idea of how Mergesort and quicksort work.
These are both recursive sorts.
- mergesort divides the array into two parts, recursively sorts
both halves and then merges the two halves. This is worst case
O(n log n). What is the recurrence relation?
- Quicksort selects an element (called the pivot) and then makes
a pass to put all elements less than it to its left, all elements greater
it to its right, and put the pivot where it belongs in sorted order.
Then it recursively sorts the two halves.
On Average, the pivot will be "in the middle" and this will be average
time O(n log n). But worst case the pivot is on the end each time and
is only one recursive call of size n-1, so worst case this could be
- Shellsort - understand the idea of how it works. It takes groups of
from the array and applies insertion sort to each group, and then finishes
by applying insertion sort to the whole array, but at that point the array
almost in sorted order so it finishes up quickly. You don't need to know
analysis for shellsort.
You don't need to know Timsort - we didn't talk about it
- Radix sort (also called "Non-comparison-based sorts) on the last slide
- Uses M buckets to sort. Puts elements in the buckets based on their
last digit, then pulls them out in that order.
Next, puts elements in the buckets based on their second digit (10's
position), and then pulls them out in that order.
- to sort N numbers with K digits with M buckets takes how long?
(the example I did was 10 2-digit numbers using 10 buckets).
- OLD ANNOUNCEMENTS BELOW HERE.
- The first day of class is January 13, 2011.
- HELP - How do I get help?
We will setup consulting hours and office hours, they will be posted on
the CompSci 100e web page starting next week.
You can also post questions on the course bulletin board. Please try to
be explicit as possible (Having trouble setting up your computer, please
tell us what type of computer, operating system, etc...).
This is a second course for Computer Science majors or those who want to gain
more experience with programming. The course assumes
prior experience with
programming (but not in Java) using such things as variables, conditionals, loops, functions,
and collections (lists, arrays). Prerequisite: CompSci 6, ENG 53 or the equivalent.
The Computer Science department
aims to excel in education and research. To ensure that our
courses fulfill student needs and expectations, you can submit
comments about this course anonymously here
These comments will be read only by the Director
of Undergraduate Studies for Teaching and Learning
and the course