CompSci 100e
Program Design and Analysis II
Course Description
A continuation of Computer Science 6 and ENG 53. Objectoriented design and
programming using Java emphasizing abstract data types and
their lowerlevel implementations. Advanced data structures including
balanced trees, hash tables, graphs. Intuitive and rigorous analysis of
algorithms. We use the
Eclipse environment.
Course Announcements
 REVIEW SESSION: OPTIONAL, FRIDAY 1:152: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:152:45pm
 Thursday: Prof. Rodger 102:45pm
 Friday: Prof. Rodger  likely 111pm, then to review session (see above)
 Friday: Bala Office hours  2:306pm North 007
 Week of May 2, 2011 Prof. Rodger office hours this week
 Monday: 23, 3:455:30pm
 Tuesday: 12:302:45pm
 Wednesday: 10:302: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.
 Graphs
 Know difference between directed and undirected graph
 Know how to represent a graph (array of linked lists, 2d array,
map, etc)
 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: RedBlack Trees
 Understand the idea behind redblack trees. They balance themselves
using
coloring, recoloring and rotations. There are 5 properties for a redblack
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 redblack 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:
Insertion sort,
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 bigOh 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
than
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
there
is only one recursive call of size n1, so worst case this could be
O(n squared).
 Shellsort  understand the idea of how it works. It takes groups of
elements
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
is
almost in sorted order so it finishes up quickly. You don't need to know
the
analysis for shellsort.

You don't need to know Timsort  we didn't talk about it
 Radix sort (also called "Noncomparisonbased 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 2digit 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...).
Required Background:
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.
Feedback
The
Computer Science department at
Duke
University 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
staff.