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
WINTER 2017

0. Basics
  1. Required Textbook:
    Goodrich, Tammasia, Goldwasser; Data Structures & Algorithms in Java, 6th edition
    Any format is fine. eText format can be rented from amazon.com for $36.45

  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. 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.

  7. Office Hours: M W 1:00 - 3:30pm
    See instructor home page


1. Homework
Distributed Due Identifier/
Link		 Precis
3/2 3/7 HW03/02 Recursively zip up two lists into one list
2/28 3/2 HW02/28 Recursively reverse a list
1/23 1/30 HW01/23 Use stack to evaluate postfix
1/17 1/19 HW01/17 Recursive print a linked list
1/12 1/17 HW01/12 Delete k-th element from end of linked list
1/10 1/12 HW01/10 Delete k-th element from linked list
1/5 1/10 HW 01/05 Compute prefix sums


2. Lectures
Date Topic Reading Resources
4/18 A couple data structures -- just for fun: trie, skiplist
More on rigorous definition of Big Oh
4/11
    Big Oh
  • How to count (i.e., obtain T(n)
  • Intuitive Big Oh from T(n)
  • Rigorous definition of Big Oh
GTG: 4.2, 4.3
Haynes' write-up on runtimeAnalysis.html
4/6 Sorts (mostly review). Lectures stressed quicksort, mergesort (internal and external), bogo sort, radix sort.
GTG: 12.1, 12.2;
GRG: 9.4.2;
4/4 Discussion of hashing project: char stream file, random file access -- especially "record-based" I/O
3/30 Test #2: Hashing, trees, BST, AVL, splay tree, Huffman; Priority queue
3/28 Priority queue insert and delete operations, Priority queue array representation
3/23 Priority queue introduction
3/2 Trees, expression tree, binary tree, first-child-next-sibling, binary search tree (BST) GTG: 11.1, 11.2 Recursive Code for BST
2/28 Hashing: load factor, rehashing, what makes a good hash function, closed addressing
2/16 Test #1
2/14 Tail recursion examples
Summary on recursion
Hashing -- open addressing, linear probe (insert, delete, find) 		Hash Tables: see GTG Section 10.2
2/7 Recursion G T & G: Chapter 5
Recursion - Watching it work 		recursion examples: pseudo-code
2/1 Expression tree. Postfix, infix tree traversal Expression tree is described GTG page 318
1/26 stack algorithms
1/24 Continue from 1/12 (circular queue, Stack operations, queue, dequeue) Infix <==> Postfix worksheet
1/17 Continue from 1/12
1/12 Demo: debugging
Linear Data Structures: array, singly linked list, doubly linked list, circular list, stack, queue, dequeue -- SEARCH!		 GTG: 3.1 - 3.4 (array, sll, dll, cl), 6.1 (stack), 6.2 (queue), 6.3 (dequeue)
1/10 Explanations of sorts: insertion, selection, bubble https://en.wikipedia.org/wiki/Insertion_sort, GTG 3.1.2
https://en.wikipedia.org/wiki/Selection_sort
https://en.wikipedia.org/wiki/Bubble_sort
1/5 Orientation to the course
Homework example Assignment A Solution 		Review Java: GT & G: Chpt 1, 2




3. Projects

Distributed Due Identifier/
Link		 Precis
4/4 4/18/2017 PP #2
input.dat		 Hashing to a random access file
2/7/2017 2/28/2017 PP #1 Simulation


4. Quizzes and Tests


Resources

Possibly useful papers


Code snippets
Last changed: