CSSE230 – Data Structures and Algorithms

Fall 2016–17 (aka 201710)

Schedule Overview

All non-Moodle web pages for the course are available from this index page.

This schedule page will begin with the schedule from a previous term, which will be updated as we go. We’ll try to update assignments and readings at least a week in advance. We’ll update daily schedules and slides just before class.

Preparation is to be completed before the class session.

Unless otherwise noted, all assignments are due at 11:00 PM on the day indicated.

Dr. B's weekly scheduleAssistant lab hours (some in F217, some in Percopo and Lakeside)Click here for personnel and location details.

Schedule last updated Thu Sep 8.

Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Week Session Preparation Due Topics Resources Major Programs
0

1

Fri Sep 2

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

Tue Sep 6

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

Wed Sep 7

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
1

4

Fri Sep 9

Details
  • MCSS Linear Algorithm
 Stacks and Queues
2

5

Tue Sep 13

Details
  • 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

Wed Sep 14

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
2

7

Fri Sep 16

Details
  • §18.1-18.3
  • More recursive binary tree methods.
  • Binary tree traversals
 Doublets
3

8

Tue Sep 20

Details
  • Study for Exam 1, take practice exam on Moodle
  • StacksAndQueues partner evaluation (on Moodle)
  • Exam 1
    Tuesday
    7:00 - 9:00 PM
    Section 1, Olin 203
    Section 2, Olin 231
    Section 3, Olin 233
    Night exam. No class today to compensate.
  Doublets
3

9

Wed Sep 21

Details
  • §18.4
  • Iterators: Simple and lazy ones
 Doublets
3

10

Fri Sep 23

Details
  • §19.1
  • Binary Search Tree (BST) methods: insert, remove, contains.
 Binary Search Tree
4

11

Tue Sep 27

Details 		 
  • Doublets partner eval
  • Size vs. Height in a binary tree
 Binary Search Tree
4

12

Wed Sep 28

Details
  • § 19.4
  • Need for trees that are height-balanced but not completely balanced
 Binary Search Tree
4

13

Fri Sep 30

Details
  • § 19.4
  • 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

Tue Oct 4

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

Wed Oct 5

Details
  • § 19.2
  • Practice with AVL Tree Rotations
  • Discuss usage of rank field
  • EditorTrees work time with your team
 EditorTrees
6

16

Tue Oct 11

Details 		 
  • EditorTrees workday
   EditorTrees
6

17

Wed Oct 12

Details
  • § 19.5
  
  • Red-black trees
 EditorTrees
6

18

Fri Oct 14

Details
  • Chapter 20
  • Hash Table intro
 EditorTrees
7

19

Tue Oct 18

Details
  • Review chapter 20
  • Hash Table implementation
 EditorTrees
7

20

Wed Oct 19

Details
  • §21.1-21.3
  
  • Priority Queues and Binary heaps
  • Heaps work time
 EditorTrees
7

21

Fri Oct 21

Details
  • §21.5
  • Heapsort
  • Heapsort work time
 EditorTrees
8

22

Tue Oct 25

Details
  • Study for the exam!
  • Exam 2
    Tuesday
    7:00 - 9:00 PM
    Section 1, Olin 203
    Section 2, Olin 231
    Section 3, Olin 233
    Night exam. No class today to compensate.
  2D Trees
8

23

Wed Oct 26

Details 		 
  • EditorTrees team member performance evaluation survey (required; Thursday 11:00 PM)
  • 2D Trees
 2D Trees
8

24

Fri Oct 28

Details 		 
  • TBA
   2D Trees
9

25

Tue Nov 1

Details
  • § 7.5
  • Extended Binary Trees
  • Intro to Recurrences
 HardyPartTwo
9

26

Wed Nov 2

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 Nov 4

Details
  • § 8.6 – 8.7 (skim Average case analysis of Quicksort)
  • Quicksort
  • Quicksort average case analysis
 HardyPartTwo
10

28

Tue Nov 8

Details
  • § 8.8
  • Quicksort improvements
  • Lower bound for sorting algorithms.
  • Radix sort
 SortingRaces
10

29

Wed Nov 9

Details 		 
  • HardyPartTwo partner eval
  • Worktime for sorting assignment
   SortingRaces
10

30

Fri Nov 11

Details 		 
  • Course evaluations
  • Discussion of Final Exam
  • Practice problems for final exam (no solutions posted, but can ask us)
 SortingRaces
11

31

Tue Nov 15

Details 		 
  • Final exam review packet (not collected)
  • Final Exam
    TBA