One Minute Evaluations for 25-27 November

CS 305 - Computer Algorithms I

• Topic: Learned about binary trees.

  Question: I want to learn more about recursion in functions.

  One minute response: You eventually want to read (and understand) Structure and Interpretation of Computer Programs by Abelson and Sussman. Depending on your knowledge and experience, you may want to start with Simply Scheme: Introducing Computer Science by Harvey and Wright, The Schemer's Guide: Second Edition by Ferguson, Martin, and Kaufman, or How to Design Programs by Felleisen, Findler, Flatt, and Krishnamurthi.

• Topic: Traversal trees intro; flatten and fold lists and trees.

  Question: When flatten and fold are done they leave a balanced tree, can that be traversed by a mechanism that returns the original linked list?

  One minute response: I'm not understanding the question. If you flatten a folded list, you'll get the original list back.

• Topic: Binary trees - folding a linear structure to create a tree; flatten a tree to make a linear structure.

• Topic: We talked about binary trees, how to traverse then, and how to convert them to and from lists.

  Question: What is the C++ syntax for multiple return values?

  One minute response: C++ itself doesn't have any syntax for multiple return values. The closest you can get is the std::make_pair() helper function if you're returning two values. Otherwise, it would be a constructor associated with a struct you have to create.

• Topic: We continued with binary trees, folding and flattening.

  Question: If traversal is so expensive and it's complicated, why use a tree?

  One minute response: That is always a good question to keep in mind when selecting data structures for an algorithm. A tree is often a good model for the data. Also, if you're careful, the cost of the complications are less than the benefits of reducing traversal expense.

• Topic: Binary trees.

• Topic: We talked about binary trees.

  Question: No questions at this time.

• Topic: We started our introduction to binary trees!

  Question: To reduce the decision making of finding an element, is it helpful to reduce the tree, flattening into a list then doing a linear search?

  One minute response: In either tree or list form you have to touch about the same number of nodes, so it doesn't make much difference (ignoring the overhead for flattening the tree in the first place). It may make sense for adding (for binary search trees) and removing (for any binary tree) elements, particularly if you're going to be doing many of them in succession. Both operations are more expensive (and difficult) in their tree form than in their list form.

• Topic: Intro to binary trees and relations to (doubly) linked lists.

  Question: Have a great Thanksgiving!

  One minute response: Thanks; same to you.

• Topic: Learned about binary trees.

  Question: When will you make your test cases available? You've seen this question before.

  One minute response: They are available; see the testing directory in the assignment directories.

• Topic: We discussed binary trees, their benefits, and how to recursively go through them.

  Question: Is it expensive to flatten and fold (go from list to tree and vice versa)?

  One minute response: Both folding and flattening touch a linear number of nodes. Linear behavior is not bad, as long as n is not too large (which is determined by circumstances).

• Topic: We learned about binary trees.

  Question: { }.

• Topic: Binary Trees, fold and flatten operators.

• Topic: Binary trees: Structure, algorithms, and translation to lists.

  Question: Nothing that won't be covered next time.

• Topic: We learned about binary trees.

  Question: Has there been any progress to the creation of a bst stl in the past 10 years?

  One minute response: Binary search trees are already available from the STL (although not explicitly) in the form of the sorted associated containers (sets and maps, multi-sets and multi-maps). A more general tree abstraction apropriate to the STL gestalt has been more difficult to design.

This page last modified on 16 July 2003.