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

smh: COSC 311 Algorithms and Data Structures
FALL 2015

0. Basics
  1. Required Textbook:
    Koffman & Wolfgang, Data Structures:Abstraction and Design Using Java, 2nd ed, Wiley, 2010, ISBN-10: 0470128704.

  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.
    An exception to the "Java only" rule is for the first project, while you are learning Java for your remaining -- in that case, only C, C++, C#, Python are allowed.
    Code must be runnable on COSC lab machines.

  5. Syllabus

  6. Calendar

  7. Coding Standards: coming (Keep it clean. Keep it readable. Keep it honest. Keep it simple.)

  8. Office Hours: MW 12:30 - 1:30p, T R 1:00 - 4:00 p


1. Lectures
Date Topic Reading Notes Assignments
Due at following class
11/16/2015
11/9/2015 B tree
11/2/2015 AVL trees - pseudocode for recursive implementation
10/28 AVL trees
A nice write-up is here 		In class "homework" solution
10/26 Priority queues (heaps)
Insert, delete, implement as binary tree, implement as 1D array
10/21 BST iterative implementations
Big-Oh
10/19 Trees chpt 6 Due 10/26
Self Check Exercises Section 6.1 (#1-5), p 303.
Self Check Exercises Section 6.2 (#1 - 4), p 306.
Self Check Exercises Section 6.4 (#1 - 6), p 331.
9/28/2015
9/23/2015 Stack applications: delimiter matching, evaluate postfix, infix -> postfix Chapter 3 Write pseudo-code to use a stack to:
(1) reverse a list
(2) test if a list is a palindrome
(3) return the maximum value of a list
Due 9/28/2015
9/21/2015 Queue and applications, Circular queue
Stack and applications, Stack in array
  1. Another way to avoid the full/empty buffer ambiguity in a circular queue on an array is to keep track of the number elements in the queue. Do not have keep one space empty.
    Give pseudo-code in the style of here
  2. Top of stack will increase on pushes. Alternatively, a tos will decrease on pushes. Give pseudo-code in the style of here where the stack grows toward decreasing index values (rather than toward increasing index values)
DUE: 9/23/2015
9/16/2015 For an unordered link list implemented in a 1D array (not the heap), give pseudo-code (in the style of pseudo code at link for today's topic) for insert element, delete any element, delete element with value = key, find index of element with value = key.
DUE: 9/23/2015.
9/14/2015
  • Demo of using shell to develop/run Java programs
  • Demo of using run time stack to trace simple recursive program.
  • Linked list -- pseudo code
no new homework
9/9/2015 Course overview
Program execution (use of memory) 		2.1 - 2.3
  • Screen shot of your running java on console (print numbers from 1 to 5): see here or here
  • Koffman: page 98 Self check exercises 4, 5




2. Projects

Project Due
Hashing for symbol table 12/14/2015
Priority queue implementation to create Huffman tree
mystery code (php source file) 		11/30/2015 12/7/2015
Stack-based arithmetic 11/11/2015
Memory manager
Unsorted list is O(n) for search 10/14/2015


3. Quizzes and Tests


4. Resources

5. Possibly useful papers


6. Code snippets
Last changed: