CS 311 Fall 2009: Data Structures and Algorithms

CS 311 Fall 2009
Data Structures and Algorithms

Department: Computer Science, UAF
Instructor: Glenn G. Chappell
Office: 201B Chapman
Office Hours: 10–12 MWF, or by appointment
Office phone: (474-)5736
E-mail: ffggc@uaf.edu
Paper mailbox: Inside the CS Department office, 202 Chapman

Announcements

Course Materials

Materials are listed with the most recent at the top.

Week Class Meetings Readings & Homework Handouts, Sample Code, Etc.
Week 15 
& Finals 
12/14–12/19 
  • 12/16: Final Exam 1–3 p.m.
  • 12/14: Course wrap-up
    Slides [PDF]
  
Week 14 
12/7–12/11 
  • 12/11: Other graph topics
    Slides [PDF]
  • 12/9: Spanning trees
    Slides [PDF]
  • 12/7: Introduction to graphs; graph traversals
    Slides [PDF]
Week 13 
11/30–12/4 
  • 12/4: Tables in various languages (cont’d); external data
    Slides [PDF]
  • 12/2: Tables in various languages
    Slides [PDF]
  • 11/30: Hash Tables (cont’d); Prefix Trees
    Slides [PDF]
  • Assignment 8
    Due Tue 12/8
    Posted Wed 12/2
  • 12/2: Read 14.1.
  • wordcount_test.txt [Text]
    Test input file for Assignment 8, Exercise A
    Posted Wed 12/2
  • usesetalgs.cpp [C++ source]
    Example using set algorithms and “exotic” iterators
    Posted Wed 12/2
Week 12 
11/23–11/25 
  • 11/27: No class (Thanksgiving)
  • 11/25: Hash Tables
    Slides [PDF]
  • 11/23: 2-3 Trees (cont’d); other balanced search trees
    Slides [PDF]
    
Week 11 
11/16–11/20 
  • 11/20: Notes on Assignment 7; Heaps & Priority Queues in the C++ STL; 2-3 Trees
    Slides [PDF]
  • 11/18: Binary Heap algorithms
    Slides [PDF]
  • 11/16: Introduction to Tables; Priority Queues
    Slides [PDF]
  • Assignment 7
    Due Tue 11/24
    Posted Wed 11/18
  • 11/18: Read/skim 615–619 (on Binary Heap algorithms).
  • bstree_test.cpp [C++ source]
    Test program for class BSTree
    Used in Assignment 7, Exercise A
    Posted Mon 11/23
  • heapalgs.h [C++ header]
    Header for Binary Heap algorithms
    Posted Wed 11/18
  • Quiz 9 Solutions [PDF]
    Posted Mon 11/16
Week 10 
11/9–11/13 
  • 11/13: Binary Search Trees; Treesort
    Slides [PDF]
  • 11/11: Introduction to Trees; Binary Trees
    Slides [PDF]
  • 11/9: Notes on Assignment 6; Queues
    Slides [PDF]
  • 11/13: Read/skim 539–555 (on Binary Search Tree Algorithms).
  • 11/11: Read 512–513 (on Binary Tree Traversals), 536–539 (on Binary Search Trees).
  
Week 9 
11/2–11/6 
  • 11/6: Stacks
    Slides [PDF]
  • 11/4: Sequences in the C++ STL
    Slides [PDF]
  • 11/2: Node-based structures; more on Linked Lists
    Slides [PDF]
  • Assignment 6
    Due Thu 11/12
    Posted Fri 11/6
  • 11/6: Read 7.1.
  • 11/4: Read 6.1.
  • da6_test.cpp [C++ source]
    Test program for classes SList, SLStack
    Used in Assignment 6, Exercises A & B
    Posted Sat 11/7
  • fibo6.cpp [C++ source]
    Computing Fibonacci numbers
    Version #6: recursion eliminated (brute force method)
    Posted Fri 11/6
  • rpn.cpp [C++ source]
    Reverse Polish Notation expression evaluation
    Example application of a Stack
    Posted Fri 11/6
  • Quiz 8 Solutions [PDF]
    Posted Wed 11/4
  • linked_list.cpp [C++ source]
    Linked List example, cont’d
    Posted Mon 11/2
Week 8 
10/26–10/30 
  • 10/30: Allocation & efficiency; generic containers; notes on Assignment 5
    Slides [PDF]
  • 10/28: Exception safety (cont’d)
    Slides [PDF]
  • 10/26: Basic array implementation; exception safety
    Slides [PDF]
  
  • tsmarray_test.cpp [C++ source]
    Test program for class TSmArray
    Used in Assignment 5, Exercise A
    Posted Fri 10/30
  • Quiz 7 Solutions [PDF]
    Posted Wed 10/28
  • Midterm Exam Solutions [PDF]
    Posted Wed 10/28
  • smarray.h [C++ header] UNFINISHED
    Header for class SmArray
    Smart array class
    Posted Mon 10/26
    Distributed in class Wed 10/28
    Revised Wed 10/28
    Distributed in class Fri 10/30
    Revised Wed 10/30
  • smarray.cpp [C++ source] UNFINISHED
    Source for class SmArray
    Smart array class
    Posted Mon 10/26
    Revised Wed 10/28
    Revised Wed 10/30
Week 7 
10/19–10/23 
  • 10/23: Where are we?; data abstraction; introduction to Sequences; array interface
    Slides [PDF]
  • 10/21: Midterm Exam
  • 10/19: Radix Sort; sorting in the C++ STL
    Slides [PDF]
  
  • radix_sort.cpp [C++ source]
    Radix Sort using forward iterators
    Posted Mon 10/19
  • pigeonhole_sort.cpp [C++ source]
    Pigeonhole Sort using forward iterators
    Posted Mon 10/19
Week 6 
10/12–10/16 
  • 10/16: Comparison sorts III (cont’d)
    Slides [PDF]
  • 10/14: Comparison sorts III
    Slides [PDF]
  • 10/12: The limits of sorting; divide-and-conquer; Comparison sorts II
    Slides [PDF]
  • 10/12: Read 472–484 (still more of 9.2).
Week 5 
10/5–10/9 
  • 10/9: Comparison sorts I; more on big-O
    Slides [PDF]
  • 10/7: Introduction to analysis of algorithms (cont’d); introduction to sorting
    Slides [PDF]
  • 10/5: Recursive search with backtracking (cont’d); introduction to analysis of algorithms
    Slides [PDF]
  • 10/9: Read 466–472 (more of 9.2).
  • 10/7: Read Back to Basics.
  • Assignment 4
    Due Tue 10/13
    Posted Mon 10/5
    Revised Thu 10/8
  • 10/5: Read 458–466 (beginning of 9.2).
  • insertion_sort.cpp [C++ source]
    Insertion Sort on an array
    Posted Fri 10/9
  • bubble_sort.cpp [C++ source]
    Bubble Sort on an array
    Posted Fri 10/9
  • Quiz 4 Solutions [PDF]
    Posted Fri 10/9
  • counthsw_test.cpp [C++ source]
    Test program for countHSW
    Used in Assignment 4, Exercise A
    Posted Thu 10/8
    Revised Fri 10/9
  • nqueencount.cpp [C++ source]
    Count solutions to the n-Queens Problem
    Example of recursive search with backtracking
    Posted Mon 10/5
Week 4 
9/28–10/2 
  • 10/2: Recursive search with backtracking
    Slides [PDF]
  • 9/30: Recursion vs. iteration (cont’d); eliminating recursion
    Slides [PDF]
  • 9/28: Search algorithms (cont’d); recursion vs. iteration
    Slides [PDF]
  • 10/2: Read 9.1.
  • 9/30: Read 248–250 (beginning of 5.1).
  • nqueen.cpp [C++ source]
    Print solutions to the n-Queens Problem
    Example of recursive search with backtracking
    Posted Fri 10/2
    Distributed in class Mon 10/5
    Revised Mon 10/5
  • binsearch4.cpp [C++ source]
    Binary Search
    Version #3: iterative (tail recursion eliminated)
    Posted Wed 9/30
  • binsearch3.cpp [C++ source]
    Binary Search
    Version #3: tail-recursive
    Posted Wed 9/30
  • fibo5.cpp [C++ source]
    Computing Fibonacci numbers
    Version #5: formula
    Posted Wed 9/30
    Distributed in class Fri 10/2
  • fibo4.cpp [C++ source]
    Computing Fibonacci numbers
    Version #4: recursive memoizing
    Posted Wed 9/30
    Distributed in class Fri 10/2
  • fibo3.cpp [C++ source]
    Computing Fibonacci numbers
    Version #3: recursive (return 2 + wrapper)
    Posted Wed 9/30
    Distributed in class Fri 10/2
  • fibo2.cpp [C++ source]
    Computing Fibonacci numbers
    Version #2: iterative
    Posted Wed 9/30
    Distributed in class Fri 10/2
  • Quiz 3 Solutions [PDF]
    Posted Wed 9/30
  • da3_test.cpp [C++ source]
    Test program for Assignment 3
    Used in Assignment 3, Exercises A–E
    Posted Mon 9/28
  • fibo1.cpp [C++ source]
    Computing Fibonacci numbers
    Version #1: recursive
    Posted Mon 9/28
    Distributed in class Fri 10/2
  • binsearch2.cpp [C++ source]
    Binary Search
    Version #2: recursive (improved)
    Posted Mon 9/28
  • binsearch1.cpp [C++ source]
    Binary Search
    Version #1: recursive
    Posted Mon 9/28
Week 3 
9/21–9/25 
  • 9/25: Introduction to Linked Lists; introduction to recursion; search algorithms
    Slides [PDF]
  • 9/23: Introduction to exceptions
    Slides [PDF]
  • 9/21: Containers & iterators; notes on Assignment 2; error handling
    Slides [PDF]
  • Assignment 3
    Due Thu 10/1
    Posted Fri 9/25
  • 9/25: Read 2.5.
  • 9/23: Read 66–69 (beginning of 2.1).
  • da3.h [C++ header] UNFINISHED
    Header file for Assignment 3
    Posted Fri 9/25
  • da3.cpp [C++ source] UNFINISHED
    Source file for Assignment 3
    Posted Fri 9/25
  • list_size.cpp [C++ source]
    Linked List example: create & find size
    Posted Fri 9/25
  • allocate2.cpp [C++ source]
    Demo of out-of-memory handling using exceptions
    Posted Wed 9/23
  • throwing.cpp [C++ source]
    Demo of throwing & catching an exception
    Posted Wed 9/23
    Distributed in class Wed 9/23
  • ksarray_test.cpp [C++ source]
    Test program for class KSArray
    Used in Assignment 2, Exercise A
    Posted Mon 9/21
    Revised Wed 9/23
Week 2 
9/14–9/18 
  • 9/18: Managing resources in a class (cont’d); templates
    Slides [PDF]
  • 9/16: Software engineering concepts: some principles; managing resources in a class
    Slides [PDF]
  • 9/14: Software engineering concepts: testing; simple class example (cont’d); pointers & dynamic allocation
    Slides [PDF]
  • intarray.h [C++ header]
    Header for class IntArray
    RAII class for dynamic array of ints
    Posted Wed 9/16
    Distributed in class Fri 9/18
    Revised 9/18
  • Quiz 2 Solutions [PDF]
    Posted Wed 9/16
Week 1 
9/8–9/11 
  • 9/11: Software engineering concepts: invariants; silently written & called functions (cont’d); simple class example
    Slides [PDF]
  • 9/9: Software engineering concepts: abstraction; parameter passing (cont’d); operator overloading; silently written & called functions
    Slides [PDF]
  • 9/7: No class (Labor Day)
  • timesec.h [C++ header]
    Header for class TimeSec
    Example of simple class with operators
    Posted Fri 9/11
    Distributed in class Mon 9/14
    Revised Mon 9/14
  • timesec.cpp [C++ source]
    Source for class TimeSec
    Example of simple class with operators
    Posted Fri 9/11
    Distributed in class Mon 9/14
    Revised Mon 9/14
  • Quiz 1 Solutions [PDF]
    Posted Fri 9/11
  • birthday_test.cpp [C++ source]
    Test program for class Birthday
    Used in Assignment 1, Exercise A
    Posted Fri 9/11
  • Coding Standards
    Standards for coding portions of CS 311 assignments
    Posted Fri 9/11
  • silent.cpp [C++ source]
    Demo of silently written & called functions
    Posted Wed 9/9
    Distributed in class Wed 9/9
Week 0 
9/3–9/4 
  • 9/4: Course overview; the structure of a package; parameter passing
    Slides [PDF]
  • 9/4: Read pp. 4–9 (beginning of 9.1) in the text.
    Note: The above date is when the reading was assigned. It should be done by the next class meeting (Wed 9/9 in this case).
  • Syllabus
    Posted Thu 9/3
    Distributed in class Fri 9/4
    Revised Fri 9/4

External links last checked December 7, 2009.
C++ FAQ LITE
A useful source of answers to C++ questions, by Marshall Cline.
SGI - Standard Template Library Programmer's Guide
Some very nice, well organized documentation for the STL. It is not a tutorial, but if you know what you are looking for, and you already have a basic idea how the STL works, then you can find what you want quickly and easily. I have found the Table of Contents link to be the most useful starting point when I reference this page. Note: This site includes documentation for some non-standard additions to the STL: slist, rope, etc.
Dictionary of Algorithms and Data Structures
A very large listing of algorithms and data structures, hosted by the U.S. National Institute of Standards and Technology. Covers a lot of ground. However, entries can be very terse and formal, and the list is by no means comprehensive (I tried finding “Priority Search Queue”; no luck).

Links to supplemental readings will be posted here as they are assigned. Links to these will also be in the “Readings & Homework” column of the Course Materials section, above.
On Following Rules
A short article that makes a good point. From kirit.com.
The Law of Leaky Abstractions
An essay about troubles involving abstractions. Written by Joel Spolsky of Fog Creek Software, as part of Joel on Software, a blog-ish site about software development.
Back to Basics
An essay about how knowledge of low-level ideas and algorithmic efficiency affect high-level software development. Another one from Joel on Software.
Guidelines for Error Handling in C++
A short summary of some ideas about error-handling by Anders Johnson, an engineer at NVIDIA.
Sorting a million 32-bit integers in 2MB of RAM using Python
This discusses how to write an external sort in Python. By Guido van Rossum, and found on his Neopythonic blog.
Introspective Sorting and Selection Algorithms [PostScript]
This is the original paper introducing the Introsort algorithm. It was written by David Musser of the Rensselaer Polytechnic Institute. It appeared in 1997 in the journal Software: Practice and Experience. I find the paper to be relatively readable; certainly it is worth skimming.
Exception Handling: A False Sense of Security
The 1994 Tom Cargill Article discussed in class. Cargill analyzes the exception-safety characteristics of a Stack implementation. He makes some good points; however, it turns out that with the interface he gives, it is impossible to implement a Stack in an exception-safe manner. Issues raised by this article led to a much improved understanding of exception safety in the mid 1990s, including many of the ideas mentioned in “Guidelines for Error Handling in C++” by Anders Johnson. (Compare the Stack interface in Cargill’s article with the interface to std::stack, particularly member function pop.)
Boost C++ Libraries
The homepage for “Boost”, a project begun by some members of the C++ standard committee. Its aim is to collect high quality C++ libraries and make them freely available. It is expected that many of the Boost libraries will, in some form, be in the next version of the C++ standard.

CS 311 Fall 2009 / Updated: 14 Dec 2009 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!