Home    Course Archive    My YouTube playlists    Video/Audio Library     Papers Archive    CV    My Keeper Shelf    Cultural References in Class Quotes

smh: COSC 311 Algorithms and Data Structures
FALL 2017

0. Basics
  1. Required Textbook:
    Goodrich, Tammasia, Goldwasser; Data Structures & Algorithms in Java, 6th edition
    Any format is fine. eText format is approximately $52.00
    Student Companion Site

  2. Do you need an alternative explanation of some data structures?
    The following book is ridiculously easy to read, but has incomplete coverage of algorithm analysis and advanced topics. It is inexpensive and well-written.
    Lafore, Data Structures and Algorithms in Java, 2nd Ed, Sams Publishing, 2002, ISBN-10: 0672324539.

  3. Do you need some extra help in Java? Suggestions:

  4. Language of Implementation: Java. All code will be in Java. We are a Java shop, for better or worse. Your code will be in Java.

  5. Syllabus

  6. Updated Calendar
    Original Calendar

  7. Coding Standards (Keep it clean. Keep it readable. Keep it honest. Keep it simple.)
    Points will be subtracted for bad readability (use of white space, choice of variable names) as well as for lack of functionality and poor design.

  8. Office Hours: M W 1:00 - 2:00 pm, T R 4:00 - 5:00pm


2. Lectures
Date Topic Read Do this
12/4 Sorts: radix, shell, bogo
Big Oh
11/29 Sorts: quick, merge, heap, counting
11/27 Skip list
11/22 Priority queue
11/15 Hourly #2
11/13 (2, 4) trees (insert, find, delete) GTG: 11.5 Do not turn in: Practice operations on (2, 4) tree
Note: insert values are changed from those given in class to avoid a case that was not discussed!
Final solution
11/8 For fun: Huffman code
11/6 AVL, Splay tree GTG:11.4
11/1 AVL tree GTG: 11.3
10/31 BST GTG: 11.1
10/18 Trees, expression tree, first-child-next-sibling,
binary search tree (BST)		 GTG: 8
10/16 Hourly #1
10/11 Hashing, database application
10/9 Recursive ops on linked list
(But recall how much code is needed to iteratively delete!: iterative linked list
Hashing 		GTG: 10.2 p 451: R-10.6, R-10.7, R-10.8, R-10.10.9.
10/4 Recursion summary
Recursion and Iteration side-by-side
Recursion, a few more examples
10/2 Recursion Recursion pseudo-code examples
Tracing ackermann(2, 1)		 GTG: chpt 5,
Recursion - Watching it work
9/25 Stack algorithms
9/20 Stack
  Paren matching
   function call/return
   postfix expression evaluation 		RandomAccessFile example on ints only
RandomAccessFile Example
GTG: 6.1
stack operations 		postfix <=> infix worksheet
9/18 Doubly Linked List (insert delete)
Double Ended Queue
Stack 		GTG:3.4
GTG: 6.3
GTG: 6.1
9/13 Queue
Circular queue implemented in array		 GTG: 6.2
Also GTG: 3.3 for circular linked list Java code 		R-6.7, R-6.9
9/11 bubble sort
selection sort
insertion sort
A couple contrasting sorts (to show not all sorts are O(n2)
    radix ==> O(k n)
    unique values, known (fixed) maximum data set size n ==> O(n)
9/6 Course overview


2. Homework

Identifier Title Distributed Due
hw1206 2D sorted array search 12/06 12/12
hw1115 Brute force 11/15 11/29
hw1005 Timing Fibonacci - memoize Thur 10/5 Mon 10/9
hw1002 Timing Fibonacci Mon 10/2 Mon 10/9
hw0920 random access file Wed 9/20 Mon 9/25
hw0913 sort singly linked list 9/13 9/20
hw0906 insert to 1D array (not destructive) 9/6 9/11




3. Projects

Title Distributed Due
Hashing on Random Access File
input.dat 		10/11/2017 10/30/2017, 11/7/2017 11/8/2017


4. Quizzes and Tests
Item/Link
Final (cumulative) Topics for Final
Quiz 11/27 on priority queue
Hourly #2 topics
    TREES:
  • General tree structure,
  • expression tree,
  • infix, postfix, prefix traversal,
  • expression tree,
  • BST,
  • BST find insert delete,
  • balance at a node, AVL tree insert,
  • Splay tree insert find,
  • (2, 4) tree insert delete
Quiz 11/1 on AVL insert


Resources

Possibly useful papers


Code snippets
Last changed: