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

[11/20] Quiz Topics for Monday 11/23
Possible quiz topics for the Monday, November 23 class meeting:
- Given a drawing of a Binary Heap (as a tree) and an operation to be performed (insert or delete a given key), perform the operation using the algorithm discussed in the text (and in class), and draw the resulting Binary Heap (as a tree).
  - Note: If the operation is a Heap delete, then I am not going to tell you which item to delete!
- What is a “2-3 Tree”?
- Given a drawing of a 2-3 Tree and an insert operation to be performed, perform the operation using the algorithm discussed in the text (and in class), and draw the resulting tree.
[11/18] Assignment 7 Posted
Assignment 7 has been posted. It is due at 5 p.m. on Tuesday, November 24. This is another group assignment. A test program will be posted soon.

Course Materials

Materials are listed with the most recent at the top.

Week	Class Meetings	Readings & Homework	Handouts, Sample Code, Etc.
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).	`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]	Assignment 5 Due Thu 11/5 Posted Fri 10/30 10/26: Read Guidelines for Error Handling in C++.	`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).	`quicksort2.cpp` [C++ source] Quicksort Version 2: improved Posted Fri 10/16 Quiz 6 Solutions [PDF] Posted Fri 10/16 Midterm Exam Review Problems, Part 3 Posted Fri 10/16 Midterm Exam Review Problems, Part 2 Posted Fri 10/16 Midterm Exam Review Problems, Part 1 Posted Fri 10/16 `quicksort1.cpp` [C++ source] Quicksort Version 1: basic Posted Wed 10/14 Quiz 5 Solutions [PDF] Posted Wed 10/14 `iterative_merge_sort.cpp` [C++ source] Iterative Merge Sort using random-access iterators Posted Mon 10/12 `merge_sort.cpp` [C++ source] Merge Sort using forward iterators Posted Mon 10/12
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]	Assignment 2 Due Thu 9/24 Posted Thu 9/17 9/16: Read The Law of Leaky Abstractions.	`intarray.h` [C++ header] Header for class `IntArray` RAII class for dynamic array of `int`s 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)	9/11: Read On Following Rules. Assignment 1 Due Thu 9/17 Posted Fri 9/11 9/9: Read 1.2.	`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

Links

External links last checked October 28, 2009.

C++ & The Standard Template Library

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.

Data Structures & Algorithms

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

Readings

Assigned Supplemental Readings

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.

Not Part of CS 311, but Worth Looking At

C++, etc.

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: 20 Nov 2009 / Glenn G. Chappell / ffggc@uaf.edu

CS 311 Fall 2009 Data Structures and Algorithms