Data Structures and Algorithmssouthwest University, China

Data Structures and AlgorithmsSouthwest University, China

Outline of Lecture Topics and Schedulefor November 2016

Revised 12 November 2016Original26 October 2016
This schedule will be updated as necessary during the November teaching period

Week 1: Lists

7 Nov 2016

intro, algorithms, data structures,

sequential search, step search, binary search,

big0,

8 Nov 2016

big O (revise),

stacks, array implementation

queues, array implementation

abstract data types (ADTs)

Java interfaces and generic types

9 Nov 2016

sorting algorithms: insert, select,

recursion

10 Nov 2016

insertion sort and select sort revise,

quicksort

merge sort

student feedback+ week 1 assignment

Week 2: Trees

14 Nov 2016

linked lists, linked list implementations of queues and stacks

15 Nov 2016

review linked list insertion and deletion

trees, tree representations,

binary trees, tree traversals,

16 Nov 2016

Review week 1 assignment

binary search trees and operations

binary tree find min and remove min operations

17 Nov 2016

priority queues: linked list impl

priority queues: binary heap impl

student feedback+ week 2 assignment

Week 3: Graphs (updated 20 Nov)

21 Nov 2016

Review assignment 2

Revision topics

Graphs, graph data structures

22 Nov 2016

Breadth first search

Minimum Spanning Tree algorithms - Kruskal, Prim

23 Nov 2016

Quiz

Implementation of Prim’s algorithm

24 Nov 2016

Java collections API: deques, sets, maps, hash tables,

Course feedback

Text Book

Data Structures & Problem Solving Using Java (4th edition)

Mark Allen Weiss

ISBN-13: 9780321541406 ISBN-10: 0321541405 Pearson Education

(other editions are also fine)

UWA Lecture Notes

Notes from the Data Structures & Algorithms unit at the University of Western Australia.

Recommended Reading for the SWU Data Structures Course

Theme / Text book reference (Weiss) / UWA notes
Intro / ch 5. algorithm analysis / Topic01-IntroDS.pdf
Topic02-IntroAlg.pdf
Topic06-Complexity.pdf
Topic07-BigO.pdf
Lists / ch 6.6 stacks and queues
ch 16 stacks and queues (implementation) / Topic03-Abstract.pdf
Topic04-Queues.pdf
Topic05-Lists.pdf
Lists / ch 8.1-8.3 sorting algorithms / Topic01-IntroDS.pdf
Topic07-BigO.pdf
Topic08-Amort.pdf
Lists / ch 7.1-7.5 recursion
ch 8.5-8.6 sorting algorithms
Trees / ch 17. Linked lists
Trees / ch 18.1 trees
ch 18.4 tree traversals / Topic10-Trees-Graphs.pdf
Topic11-TreeReps.pdf
Trees / ch 19.1-19.3 binary search trees / Topic12-Traversals.pdf
Trees / ch 6.9 priority queues (specs)
ch 21. priority queues (impl)
ch 13.2 event-driven simulation / Topic13-PriorityQueues.pdf
Graphs / ch 6 the collections api / Topic16-Maps.pdf
Topic17-SetsTablesDictionaries.pdf
Topic19-Hash.pdf
Graphs / ch 14.1 graphs and paths / Topic10-Trees-Graphs.pdf
Topic11-TreeReps.pdf
Graphs / ch 14.5.1 topological sorting / Topic12-Traversals.pdf
Graphs / ch 24.2.2 minimum spanning trees / Topic14-MST.pdf

Summary of Experiment Class Topics and Schedule 2015

Class 1 / Java revision / Development environment / ch 1. primitive java
Class 2 / Java revision / Correctness / ch 2. reference types
Class 3 / Java revision / Array exercises / ch 3. objects and classes

Class 4. Binary Search. Week 1 Problem Sheet Questions 4 and 5. If time, measurement of sorting functions, Week 1 Assignment Question 4. Recursion. Week 1 Problem Sheet Question 23 (factorial function) and Question 25 (1s in binary). If time, study and run the recursive FractalStar.java application (week 1 code bundle). See Weiss for details.

Class 5. Sorting. Week 1 Problem Sheet Question 28. Sorting measurement.

Class 6. Linked list. Write a linked list implementation of the Set interface from the Java Collections Framework. You need only implement the core methods: add, remove, isEmpty, contains, size and toString. Use provided classes such as LinkedListStringQueue.java from week 1 for ideas on how to implement these methods. Remember that a Set must not contain any duplicates: your code should enforce this condition. If time, implement the set operations Union, Intersection and SetDifference.

Class 7. Binary tree. Week 2 Problem Sheet Questions 10 and 11. Use your tree traversal code written during lectures (BinaryTreeNode.java, BinaryTreeDemo.java) as a starting point for this question. Note you are not being asked to implement a Binary Search Tree. Reading: Weiss Chapter 14.

Class 8. Graphs. Use AdjacencyMatrixGraph.java and add some code for Week 3 Problem Sheet Questions 11,12, 13, 15, 17. Reading: Weiss Chapter 14.

Class 9. Revision Questions for the Exam