CS 311 Spring 2008: Data Structures and Algorithms

CS 311 Spring 2008
Data Structures and Algorithms

Department: Computer Science, UAF
Instructor: Glenn G. Chappell
Office: 201B Chapman
Office Hours: 1 p.m. MWF & 11:30 a.m. TTh, 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. See below for links.

Week Class Meetings Readings & Homework Handouts, Sample Code, Etc.
Week 14
& Finals 
5/5–5/9 
  • 5/9: Final Exam 10:15 a.m.–12:15 p.m. in the classroom
  • 5/5: Prefix Trees; external data
    Slides [PDF]
    
Week 13 
4/28–5/2 
  • 5/2: Hash Tables, cont’d
    Slides [PDF]
  • 4/30: Other balanced search trees; Hash Tables
    Slides [PDF]
  • 4/28: Tables in practice
    Slides [PDF]
  • 4/30: Read 14.1.
  • Assignment 8
    Due Fri 5/2
    Posted Mon 4/28
  • 4/28: Read 686–695.
Week 12 
4/21–4/25 
  • 4/25: Heaps and Priority Queues in Practice; 2-3 Trees
    Slides [PDF]
  • 4/23: Priority Queues; Heap algorithms
    Slides [PDF]
  • 4/21: Introduction to Tables
    Slides [PDF]
  • 4/25: Optional reading: 654–670.
  • 4/23: Read 650–653.
  • heapalgs.h [C++ header]
    Header for Heap algorithms
    Posted Fri 4/25
    Distributed in class Fri 4/25
Week 11 
4/14–4/18 
  • 4/18: No class (UAF SpringFest)
  • 4/16: Binary Search Trees; Treesort
    Slides [PDF]
  • 4/14: Trees in general; Binary Trees
    Slides [PDF]
Week 10 
4/7–4/11 
  • 4/11: Queues
    Slides [PDF]
  • 4/9: Stacks, cont’d
    Slides [PDF]
  • 4/7: Sequences in practice; Stacks
    Slides [PDF]
  • 4/11: Read 10.2.
  • Assignment 6
    Due Thu 4/17
    Posted Fri 4/11
    Revised Sat 4/12
  • 4/9: Read 10.1.
  • 4/7: Read 7.1–7.2.
  • slist.h [C++ header] UNFINISHED
    Header for class SList
    Singly Linked List class
    Posted Sat 4/12
  • da6_test.cpp [C++ Source]
    Test Program for classes SList, SLStack
    Used in Assignment 6, Exercises A & B
    Posted Sat 4/12
    Revised Fri 4/18
  • fibo5.cpp [C++ source]
    Computing Fibonacci numbers
    Version #5: recursion eliminated
    Posted Wed 4/9
    Distributed in class Wed 4/9
  • rpn.cpp [C++ source]
    Reverse Polish Notation expression evaluation
    Example application of a Stack
    Posted Wed 4/9
Week 9 
3/31–4/4 
  • 4/4: Node-based structures, cont’d; Linked Lists
    Slides [PDF]
  • 4/2: Generic containers; node-based structures
    Slides [PDF]
  • 3/31: Exception safety, cont’d; allocation & efficiency
    Slides [PDF]
  • 4/4: Read 6.1–6.2.
  • Assignment 5
    Due Tue 4/8
    Posted Mon 3/31
    Revised Tue 4/1
    Revised Wed 4/2
Week 8 
3/24–3/28 
  • 3/28: Exception safety
    Slides [PDF]
  • 3/26: Interfaces to data, cont’d; data structure implementation
    Slides [PDF]
  • 3/24: Data abstraction; Sequence data; interfaces to data
    Slides [PDF]
  • Quiz 7 Solutions [PDF]
    Posted Fri 3/28
  • Midterm Exam Solutions [PDF]
    Posted Wed 3/26
  • sequence.h [C++ header] UNFINISHED
    Header for class Sequence
    Smart array class
    Posted Wed 3/26
    Distributed in class Fri 3/28
    Revised Mon 3/31
  • sequence.cpp [C++ source] UNFINISHED
    Source for class Sequence
    Smart array class
    Posted Wed 3/26
    Distributed in class Fri 3/28
    Revised Mon 3/31
Week 7 
3/17–3/21 
  • 3/21: In-Class Midterm Exam
  • 3/19: Sorting algorithms III, cont’d; Radix Sort; practical sorting
    Slides [PDF]
  • 3/17: Sorting algorithms II, cont’d; sorting algorithms III
    Slides [PDF]
  
Spring Break  
Week 6 
3/3–3/7 
  • 3/7: Divide-and-conquer; sorting algorithms II
    Slides [PDF]
  • 3/5: Sorting algorithms I, cont’d; more on big-O; the limits of sorting
    Slides [PDF]
  • 3/3: Sorting algorithms I
    Slides [PDF]
  • 3/5: Read 472–484 (still more of 9.2).
  • 3/3: Read 466–472 (more of 9.2).
  • Quiz 5 Solutions [PDF]
    Posted Mon 3/17
  • iterative_merge_sort.cpp [C++ source]
    Iterative Merge Sort using random-access iterators
    Posted Fri 3/7
  • merge_sort.cpp [C++ source]
    Merge Sort using forward iterators
    Posted Fri 3/7
  • Handout on Applying the Master Theorem
    This was a copy of slide 19 on the Friday, 3/7 lecture slides
    Distributed in class Fri 3/7
  • insertion_sort.cpp [C++ source]
    Insertion Sort on an array
    Posted Wed 3/5
  • selection_sort.cpp [C++ source]
    Selection Sort on an array
    Posted Wed 3/5
  • bubble_sort2.cpp [C++ source]
    Bubble Sort
    Version #2: using forward iterators
    Posted Wed 3/5
  • bubble_sort1.cpp [C++ source]
    Bubble Sort
    Version #1: using an array
    Posted Wed 3/5
Week 5 
2/25–2/29 
  • 2/29: introduction to analysis of algorithms, cont’d; introduction to sorting
    Slides [PDF]
  • 2/27: Introduction to analysis of algorithms
    Slides [PDF]
  • 2/25: Recursive search with backtracking, cont’d
    Slides [PDF]
  • Quiz 4 Solutions [PDF]
    Posted Fri 2/29
  • spidertours_test.cpp [C++ Source]
    Test Program for function countSpiderTours
    Used in Assignment 4, Exercise A
    Posted Tue 2/26
  • nqueencount.cpp [C++ source]
    Counts solutions to the n-Queens Problem
    Example of recursive search with backtracking
    Posted Mon 1/25
  • Quiz 3 Solutions [PDF]
    Posted Fri 2/29
Week 4 
2/18–2/22 
  • 2/22: Eliminating recursion, cont’d; recursive search with backtracking
    Slides [PDF]
  • 2/20: Recursion vs. iteration; eliminating recursion
    Slides [PDF]
  • 2/18: Introduction to recursion; search algorithms
    Slides [PDF]
  • 2/22: Read 9.1 (ignore the part about Linked Lists).
  • 2/20: Read 5.1.
  • 2/18: Read 2.5.
  • nqueen.cpp [C++ source]
    Prints solutions to the n-Queens Problem
    Example of recursive search with backtracking
    Posted Fri 1/22
    Distributed in class Mon 1/25
    Revised Mon 1/25
  • binsearch4.cpp [C++ source]
    Binary Search
    Version #4: iterative (tail recursion eliminated)
    Posted Fri 2/22
  • binsearch3.cpp [C++ source]
    Binary Search
    Version #3: tail-recursive
    Posted Fri 2/22
  • fibo4.cpp [C++ source]
    Computing Fibonacci numbers
    Version #4: formula
    Posted Fri 2/22
  • fibo3.cpp [C++ source]
    Computing Fibonacci numbers
    Version #3: recursive (return 2 with wrapper)
    Posted Wed 2/20
  • fibo2.cpp [C++ source]
    Computing Fibonacci numbers
    Version #2: iterative
    Posted Wed 2/20
  • fibo1.cpp [C++ source]
    Computing Fibonacci numbers
    Version #1: recursive
    Posted Mon 2/18
    Distributed in class Wed 2/20
  • binsearch2.cpp [C++ source]
    Binary Search
    Version #2: recursive (improved)
    Posted Mon 2/18
    Distributed in class Wed 2/20
  • binsearch1.cpp [C++ source]
    Binary Search
    Version #1: recursive
    Posted Mon 2/18
Week 3 
2/11–2/15 
  • 2/15: Introduction to exceptions, cont’d
    Slides [PDF]
  • 2/13: Error handling, cont’d; introduction to exceptions
    Slides [PDF]
  • 2/11: Templates, cont’d; containers & iterators; error handling
    Slides [PDF]
  • Assignment 3
    Due Thu 2/21
    Posted Fri 2/15
    Revised Mon 2/18
  • 2/11: Read 2.1.
  • da3_test.cpp [C++ Source]
    Test Program for Assignment 3 Functions
    Used in Assignment 3, Exercises A, B, C, and D
    Posted Mon 2/18
  • allocate2.cpp [C++ source]
    Demo of out-of-memory handling using exceptions
    Posted Fri 2/15
  • throwing.cpp [C++ source]
    Demo of throwing & catching an exception
    Posted Wed 2/13
    Distributed in class Fri 2/15
Week 2 
2/4–2/8 
  • 2/8: Managing resources in a class, cont’d; templates
    Slides [PDF]
  • 2/6: Managing resources in a class
    Slides [PDF]
  • 2/4: Simple class example, cont’d; pointers & dynamic allocation
    Slides [PDF]
  • sarray_test.cpp [C++ Source]
    Test Program for class SArray
    Used in Assignment 2, Exercise A
    Posted Sat 2/9
  • intarray.h [C++ header]
    Header for class IntArray
    RAII class for dynamically allocated arrays of ints
    There is no associated source file
    Posted Wed 2/6
    Distributed in class Fri 2/8
Week 1 
1/28–2/1 
  • 2/1: Software design principles III; silently written & called functions, cont’d; simple class example
    Slides [PDF]
  • 1/30: Software design principles II; operator overloading, cont’d; silently written & called functions
    Slides [PDF]
  • 1/28: Software design principles I; parameter passing; operator overloading
    Slides [PDF]
  • Quiz 2 Solutions [PDF]
    Posted Wed 2/6
  • timesec.h [C++ Header]
    Header for class TimeSec
    Example of simple class with operators
    Posted Fri 2/1
    Preliminary version distributed in class Mon 2/4
    Revised Mon 2/4
  • timesec.cpp [C++ Source]
    Source for class TimeSec
    Example of simple class with operators
    Posted Fri 2/1
    Preliminary version distributed in class Mon 2/4
    Revised Mon 2/4
  • bday_test.cpp [C++ Source]
    Test Program for class BDay
    Used in Assignment 1, Exercise A
    Posted Fri 2/1
  • Coding Standards
    Standards for coding portions of CS 311 assignments
    Posted Wed 1/30
  • silent.cpp [C++ Source]
    Demo of silently written & called functions
    Posted Wed 1/30
    Distributed in class Wed 1/30
  • Quiz 1 Solutions [PDF]
    Posted Mon 1/28
Week 0 
1/24–1/25 
  • 1/25: Course overview; the structure of a package
    Slides [PDF]
  • 1/25: Read 1.1 (skipping the part on UML, if you wish).
  • Syllabus
    Posted Fri 1/25
    Distributed in class Fri 1/25

External links last checked May 2, 2008.

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.
Phil Ottewell’s STL Tutorial
This is an STL tutorial that many people seem to think well of. I did not learn STL from this tutorial myself, so I cannot say how good it is pedagogically. However, it does appear to be thorough, correct, and (unlike a number of STL tutorials on the web) up-to-date.
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.

On following rules
A very short article that makes a good point. From kirit.com.
The RAII (Resource Acquisition Is Initialisation) Programming Idiom
An introduction to RAII by Jon Hanna, a programmer living in Dublin who has written a number of worthwhile articles.
Back to Basics
An essay about how knowledge of low-level ideas and algorithmic efficiency affects high-level software development. Written by Joel Spolsky of Fog Creek Software, as part of Joel on Software, a blog-ish site about software development.
Guidelines for Error Handling in C++
A short summary of some ideas about error-handling by Anders Johnson, an engineer at NVIDIA.
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.
How Hashes Really Work
A basic article on Hash Tables. Covers roughly the same ideas we looked at in class. Also includes Perl code for a “toy” Hash Table. Written by Abhijit Menon-Sen and found on perl.com.
A Hash Function for Hash Table Lookup
This rather advanced article by Bob Jenkins appeared in Dr. Dobb’s Journal in 1997. It covers a hash function that (apparently) is currently used in the Perl language. Also see Bob Jenkins's website for more on hashing and many other topics.

CS 311 Spring 2008 / Updated: 9 May 2008 / Glenn G. Chappell / ffggc@uaf.edu Valid HTML 4.01!