CSSE230 – Data Structures and Algorithms

Winter 2013–14

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:59 PM on the day indicated.

Schedule last updated Tue Feb 18.

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
1

1

Tue Dec 3

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

Details
  • Review the Syllabus, bring questions to class
  • Weiss §5.1, 5.2, 5.4–5.8, 7.2
  • Continue reviewing Weiss Ch. 1–6.
  • Post to "Introduce Yourself" on Piazza ( link in syllabus)
  • Make progress on WarmUpAndStretching.
  • Growable Arrays completion and discussion
  • 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 Dec 6

Details
  • Continue reviewing Weiss Ch. 1–6; focus on §5.3
  • MCSS Cubic and Quadratic Algorithms
 Warm Up and Stretching
2

4

Tue Dec 10

Details
  • Finish review of Weiss Ch. 1–6
  • Read article Why Math?
  • MCSS Linear Algorithm
 Stacks and Queues
2

5

Thu Dec 12

Details 		   
  • Abstract data types (ADTs)
  • Review of basic data structures in the Java Collections Framework
 Stacks and Queues
2

6

Fri Dec 13

Details 		 
  • Trees Intro
  • Implementing a Binary Tree using recursive methods.
 Stacks and Queues
3

7

Tue Dec 17

Details
  • §7.1-7.3, 7.5.1
  • More recursive binary tree methods.
  • Binary tree traversals and iterators
 Binary Search Tree
3

8

Thu Dec 19

Details
  • Ch. 15-17 (should be mostly review)
  • §18.1-18.3
  • StacksAndQueues partner evaluation (on Moodle)
  • Lazy iterators
  • BST Insertion
 Binary Search Tree
3

9

Fri Dec 20

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

10

Tue Jan 7

Details 		 
  • Class cancelled due to snow
  • Continue work on current assignments
 Displayable Binary Tree
4

11

Thu Jan 9

Details 		 
  • EditorTrees team preference survey.
  • Size vs. Height in a binary tree
 Displayable Binary Tree
4

12

Fri Jan 10

Details 		 
  • Rank and efficiently finding kth element of a BST
  • Need for trees that are height-balanced but not completely balanced
 Displayable Binary Tree
5

13

Tue Jan 14

Details
  • § 19.4
  • Meet EditorTree team
  • AVL Trees: How to find the node where rotation is needed
  • Single and double rotations; effect on subtree height.
  • Exam 1
    Wednesday
    7:00 - 9:00 PM
    Section 1, O157
    Section 2, O159
    Section 3, O167
    Night exam. A future class, date TBD, will be cancelled to compensate.
EditorTrees
5

14

Thu Jan 16

Details 		 
  • Midterm course evaluation in Moodle.
  • Displayable Binary tree partner evals
  • Practice with AVL Tree Rotations
  • Student questions on EditorTree Requirements
  • EditorTrees work time.
 EditorTrees
5

15

Fri Jan 17

Details 		 
  • Red-black trees
 EditorTrees
6

16

Tue Jan 21

Details
  • §7.7
  • Exhaustive search, non-attacking queens problem.
 EditorTrees
6

17

Thu Jan 23

Details 		   
  • EditorTree work time
   EditorTrees
6

18

Fri Jan 24

Details
  • §20.1-20.7
  • Hash Table intro
 EditorTrees
7

19

Tue Jan 28

Details
  • § 7.5
  • Extended Binary Trees
  • Intro to Recurrences
 EditorTrees
7

20

Thu Jan 30

Details
  • Study for the exam!
  
  • Exam 2
    Thursday
    7:00 - 9:00 PM
    Section 1, O257
    Section 2, O259
    Section 3, O267
    Night exam instead of regular class.
  EditorTrees
7

21

Fri Jan 31

Details
  • § 7.5.2, 7.5.3
  • § 8.1 – 8.5 (skip 8.4.1)
  • Recurrences and Master Theorem
  • Sorting review/overview
 EditorTrees
8

22

Tue Feb 4

Details
  • § 8.6 – 8.7 (skim Average case analysis of Quicksort)
  • Quicksort
  • Quicksort average case analysis
 Doublets
8

23

Thu Feb 6

Details 		 
  • EditorTrees team member performance evaluation survey.
  • NO CLASS DUE TO NIGHT EXAM 1
   Doublets
8

24

Fri Feb 7

Details
  • § 8.8
  • Quicksort improvements
  • Lower bound for sorting algorithms.
  • Radix sort
 Doublets
9

25

Tue Feb 11

Details 		 
  • Skip lists
  • Skiplist project intro
 SkipLists
9

26

Thu Feb 13

Details
  • §21.1-21.3
  • Doublets partner evaluation
  • Priority Queues and Binary heaps
 SkipLists
9

27

Fri Feb 14

Details
  • §21.5
  • Heapsort
  • SkipLists work time
 SkipLists
10

28

Tue Feb 18

Details
  • §14.1
  • Graphs
 SortingRaces
10

29

Thu Feb 20

Details 		   
  • Worktime for sorting assignment
   SortingRaces
10

30

Fri Feb 21

Details 		 
  • SortingRaces (You may NOT use a late day for this assignment.)
  • Course evaluations
  • Discussion of Final Exam
  • Practice problems for final exam (no solutions posted, but can ask us)
 SortingRaces
11

31

Tue Feb 25

Details 		 
  • Final exam review packet (not collected)
  • Final Exam
    Monday
    6:00 PM - 10:00 PM
    Section 1, O231
    Section 2, O233
    Section 3, O205