| Week |
Session |
Preparation |
Due |
Topics |
Resources |
Major Programs |
| 1 |
1
Tue Mar 5
Details
|
- Read the Syllabus
- Notice that there is a lot of material to read at the beginning of the course, because a high percentage of that material should be review. Skim the parts that are review for you; carefully read the others. * Notice that there is a lot of material to read at the beginning of the course, because a high percentage of that material should be review. Skim the parts that are review for you; carefully read the others.
- Review Weiss Ch. 1–6 before Day 4 (this document may help guide your reading).
- Email your instructor if you forgot your SVN password (different from your normal Rose-hulman network password)
- Bookmark this schedule page in your browser.
- Install software for the course:
|
- Nothing today, but things due every other day of the first week!
- Always look at the Major Programs column, too, for the programming assignment of the week.
|
- Course introduction
- Growable Array analysis
-
Main activities for Week 1:
On your own: Skim/read some review material from the textbook and get back up-to-speed on programming by doing the WarmUpAndStretching assignment
In class: Foundations of algorithm analysis |
|
|
Warm Up and Stretching
|
| 1 |
2
Thu Mar 7
Details
|
- Review the Syllabus, bring questions to class
- Weiss §5.1, 5.2, 5.4–5.8, 7.2
- Continue review of Weiss Ch. 1–6 (due before session 4).
|
- Post to "Introduce Yourself" on Piazza; what you write can be as short or long as you wish.
- Complete Diagnostic Quiz 1 on ANGEL (Lessons → Diagnostic Quizzes) by Wednesday, 8:00 AM (no late days may be used)
- Complete Diagnostic Quiz 2 and Quiz 3 on ANGEL by Thursday, 8:00 AM (no late days)
- Make progress on WarmUpAndStretching.
|
- Growable Arrays completion and discussion
- Proving properties by mathematical induction.
- Review of Asymptotic analysis and formal definition of Big O.
- Big-oh’s cousins, big-Omega and big-Theta
- Limits and asymptotic behavior
|
|
Warm Up and Stretching
|
| 1 |
3
Fri Mar 8
Details
|
- Continue review of Weiss Ch. 1–6 (due before session 4)
- Know the definitions in the Key Concepts at the ends of Ch. 1–3 ( include Chapter 4 by Session 4)
|
- Written Assignment 1 All course assignments are due at 8:AM unless otherwise specified.
Submit to drop box in ANGEL.
Most weeks, written assignments will be due on Friday at 8 AM.
|
- Abstract data types (ADTs)
- Review of basic data structures
|
|
Warm Up and Stretching
|
| 2 |
4
Tue Mar 12
Details
|
- Finish review of Weiss Ch. 1–6
|
|
- Continue Data Structures Grand Tour
- Review
Comparable, function objects, Comparator.
|
|
Pascal Christmas Tree
|
| 2 |
5
Thu Mar 14
Details
|
|
- Hardy/Colorize partner preference survey (on ANGEL)
|
- MCSS Cubic and Quadratic Algorithms
|
|
Pascal Christmas Tree
|
| 2 |
6
Fri Mar 15
Details
|
|
|
- MCSS Linear Algorithm
- Pair Programming Video
- Finite State Machines and implementation strategies
- Colorize Intro
|
|
Pascal Christmas Tree
|
| 3 |
7
Tue Mar 19
Details
|
|
|
- Recursion overview
- Recursive size of linked list
- Recursive parseInt OR binary Search (instructor choice)
- Recursion exercise: Tree problem from WA3
|
|
Hardy Part 2
and ColorizeFSM partial pdf
|
| 3 |
8
Thu Mar 21
Details
|
- Ch. 15-17 (should be mostly review)
- §18.1-18.3
|
- Pascal partner evaluation (on ANGEL) due at 5 PM.
|
- Java Collections Framework
- Trees intro
|
|
Hardy Part 2
and ColorizeFSM partial pdf
|
| 3 |
9
Fri Mar 22
Details
|
- Install Weiss packages on your system so they will be available for you to use
|
|
- More binary trees
- Binary tree traversals
- Questions about Exam 1
|
|
Hardy Part 2
and ColorizeFSM partial pdf
|
| 4 |
10
Tue Mar 26
Details
|
|
|
- More tree methods (contains, duplicate, equals)
- Binary tree iterators
- Alternate approaches to iterators
- Size vs. Height in a binary tree
|
|
Displayable Binary Tree
|
| 4 |
11
Thu Mar 28
Details
|
|
|
- Exam 1
Tuesday
7:00 - 9:00 PM
Section 1, O269
Section 2, O267 Thursday's class is cancelled due to the exam.
|
|
Displayable Binary Tree
|
| 4 |
12
Fri Mar 29
Details
|
|
- Written Assignment 4
- Hardy/Colorize partner evaluation due today at 5 PM (on ANGEL)
- By 5:00 PM: Doublets partner preference survey (on ANGEL)
|
- Size vs. Height in a binary tree
- BST intro, contains method
- Finding kth element of a BST
- Threaded binary trees
- Finding kth element of a BST
- BST with rank
|
|
Displayable Binary Tree
|
| 5 |
13
Tue Apr 9
Details
|
|
|
- Discuss a few exam questions
- Doublets preview, meet partner
- Definition of Height-balanced tree
- Induction example: Fibonacci
- Completely-balanced trees: nice idea, but ...
- Height-balanced trees, maximum height
|
|
Doublets
|
| 5 |
14
Thu Apr 11
Details
|
|
|
- AVL Trees: How to find the node where rotation is needed
- Single and double rotations; effect on subtree height.
- Worktime
|
|
Doublets
|
| 5 |
15
Fri Apr 12
Details
|
|
|
- Practice with AVL Tree Rotations
- Doublets work time.
|
|
Doublets
|
| 6 |
16
Tue Apr 16
Details
|
|
|
- EditorTrees intro and teams
- Exhaustive search, non-attacking queens problem.
|
|
EditorTrees
|
| 6 |
17
Thu Apr 18
Details
|
|
- Doublets partner evaluation (5:00 PM)
|
- Student questions on EditorTree Requirements
- EditorTree work time
|
|
EditorTrees
|
| 6 |
18
Fri Apr 19
Details
|
|
|
|
|
EditorTrees
|
| 7 |
19
Tue Apr 23
Details
|
|
|
- Hash tables (continued)
- Editor Trees milestone 2 worktime
|
|
EditorTrees
|
| 7 |
20
Thu Apr 25
Details
|
|
|
- Exam 2
Tuesday
7:00-9:00 PM
Section 1, O269
Section 2, O267
- Covers material through session 18, WA6, EditorTrees insertion
- Thursday's class is cancelled due to the exam.
|
|
EditorTrees
|
| 7 |
21
Fri Apr 26
Details
|
|
|
- Extended Binary Trees
- Intro to Recurrences
|
|
EditorTrees
|
| 8 |
22
Tue Apr 30
Details
|
- § 7.5.2, 7.5.3
- § 8.1 - 8.5
|
|
- Recurrences and Master Theorem
- Sorting review/overview
- EditorTrees work time
|
|
EditorTrees
|
| 8 |
23
Thu May 2
Details
|
- § 8.4–8.7 (skip 8.4.1, skim Average case analysis of Quicksort)
|
|
- Quicksort
- Quicksort average case analysis
- EditorTrees work time
|
|
EditorTrees
|
| 8 |
24
Fri May 3
Details
|
|
|
- Quicksort improvements
- Lower bound for sorting algorithms.
- Radix sort
|
|
EditorTrees
|
| 9 |
25
Tue May 7
Details
|
|
|
- Radix sort
- Skip lists
- Skiplist project intro
|
|
SkipLists
|
| 9 |
26
Thu May 9
Details
|
|
- EditorTrees team member performance Evaluation Survey, by Thursday 5:00 PM.
|
- Priority Queues and Binary heaps
|
|
SkipLists
|
| 9 |
27
Fri May 10
Details
|
|
|
- Heapsort
- SkipLists work time
|
|
SkipLists
|
| 10 |
28
Tue May 14
Details
|
|
|
|
|
SortingRaces
|
| 10 |
29
Thu May 16
Details
|
|
|
- Worktime for sorting assignment
|
|
SortingRaces
|
| 10 |
30
Fri May 17
Details
|
|
- SortingRaces (Friday 11:59 pm. You may also use a late day if you have one.)
|
- Course evaluations
- Discussion of Final Exam
- Practice problems for final exam
|
|
SortingRaces
|
| 11 |
31
Tue May 21
Details
|
|
|
- Final Exam
Wednesday
8:00 AM - 12:00 noon
Section 1, O231
Section 2, O233
|
| |