| Week |
Session |
Preparation |
Due |
Topics |
Resources |
Major Programs |
| 1 |
1
Tue Mar 8
Details
|
- Read the Syllabus
- Bookmark this schedule page.
- Email your instructor if you forgot your SVN password
- Review Weiss Ch. 1–6 this week: many pages, mostly review. Carefully read the new stuff and skim the rest: this document may help guide you).
- Install software for the course:
- Java 8,
- Eclipse (current version - I use Java EE), and
- Subclipse (Update from Eclipse > Help > Install, URL = http://subclipse.tigris.org/update_1.8.x
|
- Nothing today
- Always look at the Major Programs column, too, for the programming assignment of the week.
|
- Course introduction
- Growable Array analysis
-
Week 1:
On your own: Skim/read review from the book and get back up-to-speed on programming by doing the WarmUpAndStretching assignment
In class: Algorithm analysis |
|
|
Warm Up and Stretching
|
| 1 |
2
Thu Mar 10
Details
|
- Weiss §5.1, 5.2, 5.4–5.8, 7.2
- Continue reviewing Weiss Ch. 1–6.
|
- Post to "Introduce Yourself" on Piazza
- Growable Arrays (at start of class)
- Make progress on WarmUpAndStretching.
|
- Growable Arrays discussion
- Review of Asymptotic analysis and formal definition of Big O.
- Big-oh’s cousins, big-Omega and big-Theta
|
|
Warm Up and Stretching
|
| 1 |
3
Fri Mar 11
Details
|
- Continue reviewing Weiss Ch. 1–6; focus on §5.3
|
- Homework 1 Submit to drop box in Moodle.
- Make progress on WarmUpAndStretching.
|
- MCSS Cubic and Quadratic Algorithms
|
|
Warm Up and Stretching
|
| 2 |
4
Tue Mar 15
Details
|
|
|
|
|
Stacks and Queues
|
| 2 |
5
Thu Mar 17
Details
|
- Finish review of Weiss Ch. 1–6, focus on ch. 6
|
- UML Diagram of Collections framework (from HW2)
|
- Abstract data types (ADTs)
- Review of basic data structures in the Java Collections Framework
|
|
Stacks and Queues
|
| 2 |
6
Fri Mar 18
Details
|
- Ch. 7.3 (review of recursion)
- Ch. 15-17 (List implementation (review); skim, but may help for assignment)
|
|
- Trees Intro
- Implementing a Binary Tree using recursive methods.
|
|
Stacks and Queues
|
| 3 |
7
Tue Mar 22
Details
|
|
|
- More recursive binary tree methods.
- Binary tree traversals
|
|
Doublets
|
| 3 |
8
Thu Mar 24
Details
|
- Study for Exam 1, take practice exam on Moodle
|
- StacksAndQueues partner evaluation (on Moodle)
|
- Exam 1
Thursday
7:00 - 9:00 PM
Section 1, Olin 157
Section 2, Olin 159
Section 3, Olin 167
Night exam. No class today to compensate.
|
|
Doublets
|
| 3 |
9
Fri Mar 25
Details
|
|
|
- Iterators: Simple and lazy ones
|
|
Doublets
|
| 4 |
10
Tue Mar 29
Details
|
|
|
- Binary Search Tree (BST) methods: insert, remove, contains.
|
|
Binary Search Tree
|
| 4 |
11
Thu Mar 31
Details
|
|
|
- Size vs. Height in a binary tree
|
|
Binary Search Tree
|
| 4 |
12
Fri Apr 1
Details
|
|
|
- Need for trees that are height-balanced but not completely balanced
|
|
Binary Search Tree
|
| 5 |
13
Tue Apr 12
Details
|
|
|
- AVL Trees: How to find the node where rotation is needed
- Single and double rotations; effect on subtree height.
- Intro EditorTree and need for rank field
- Meet team
|
|
EditorTrees
|
| 5 |
14
Thu Apr 14
Details
|
- Re-write any tree methods you haven't yet mastered
|
|
- Student questions on EditorTree Requirements
- Practice with AVL Tree Rotations
- Exam 2a in class
|
|
EditorTrees
|
| 5 |
15
Fri Apr 15
Details
|
|
|
- Practice with AVL Tree Rotations
- Discuss usage of rank field
- EditorTrees work time with your team
|
|
EditorTrees
|
| 6 |
16
Tue Apr 19
Details
|
|
|
|
|
EditorTrees
|
| 6 |
17
Thu Apr 21
Details
|
|
|
|
|
EditorTrees
|
| 6 |
18
Fri Apr 22
Details
|
|
|
|
|
EditorTrees
|
| 7 |
19
Tue Apr 26
Details
|
|
|
- Hash Table implementation
|
|
EditorTrees
|
| 7 |
20
Thu Apr 28
Details
|
|
|
- Priority Queues and Binary heaps
- Heaps work time
|
|
EditorTrees
|
| 7 |
21
Fri Apr 29
Details
|
|
|
- Heapsort
- Heapsort work time
|
|
EditorTrees
|
| 8 |
22
Tue May 3
Details
|
|
|
- Exam 2
Tuesday
7:00 - 9:00 PM
Section 1, Olin 157
Section 2, Olin 159
Section 3, Olin 167
Night exam. No class today to compensate.
|
|
2D Trees
|
| 8 |
23
Thu May 5
Details
|
|
- EditorTrees team member performance evaluation survey (required; Thursday 11:00 PM)
|
|
|
2D Trees
|
| 8 |
24
Fri May 6
Details
|
|
|
|
|
2D Trees
|
| 9 |
25
Tue May 10
Details
|
|
|
- Extended Binary Trees
- Intro to Recurrences
|
|
HardyPartTwo
|
| 9 |
26
Thu May 12
Details
|
- § 7.5.2, 7.5.3
- § 8.1 – 8.5 (skip 8.4.1)
|
|
- Recurrences and Master Theorem
- Sorting review/overview
|
|
HardyPartTwo
|
| 9 |
27
Fri May 13
Details
|
- § 8.6 – 8.7 (skim Average case analysis of Quicksort)
|
|
- Quicksort
- Quicksort average case analysis
|
|
HardyPartTwo
|
| 10 |
28
Tue May 17
Details
|
|
|
- Quicksort improvements
- Lower bound for sorting algorithms.
- Radix sort
|
|
SortingRaces
|
| 10 |
29
Thu May 19
Details
|
|
- HardyPartTwo partner eval
|
- Worktime for sorting assignment
|
|
SortingRaces
|
| 10 |
30
Fri May 20
Details
|
|
|
- Course evaluations
- Discussion of Final Exam
- Practice problems for final exam (no solutions posted, but can ask us)
|
|
SortingRaces
|
| 11 |
31
Tue May 24
Details
|
|
- Final exam review packet (not collected)
|
- Final Exam
Thursday
8:00 AM - 12:00 PM
Section 1&2, A-J last name, Olin 259
Section 1&2, K-Z last name, Olin 257
Section 3, Olin 267
|
| |
