One Minute Evaluations for 28-30 October

CS 305 - Computer Algorithms I

• Topic: We talked about dynamic memory and linked lists.

  Question: Would you say a doubly linked list is more efficient for extremely large lists since it may cut traversal time?

  One minute response: Only if a majority of list access occur at either end of the list, in which case a doubly-linked list can find elements at the end of the list more quickly than can a singly-linked list. If the list access are distributed throughout the list, or are grouped at only one end, then singly- and doubly- linked lists have about the same access costs, and doubly-linked lists have twice the overhead of singly-linked lists.

• Topic: We discussed lists, with a detour into pointers and dynamic memory, and using pointers to implement lists.

  Question: What expression for array indexing do you keep referring to on the test?

  One minute response: The one we went over in class; the one that's given in the text (Section 3.2); the one that's described on the answers to the first test (green white).

• Topic: We learned linked lists.

  Question: I'm ok with everything.

  One minute response: Great.

• Topic: Dynamic storage management (manual), linked lists, ptr management, intro to doubly linked lists.

  Question: When can MSM be [?] to a list in terms of size?

  One minute response: I don't understand the question.

• Topic: Linked lists.

  Question: How much space and element shifting would you need to be doing to make using linked lists partial on today's machines?

  One minute response: It's not so much a hardware question as a software one; the work on optimizing code that uses pointers hasn't produce spectacular results (it's a hard problem) and hasn't filtered out to production compilers. As far as the hardware's concerned, pointers are just numbers, so pointer manipulations are among the most efficient operations a machine can perform.

• Topic: Linked list, manual vs. automatic storage, malloc and free vs. new and delete.

• Topic: Dynamic memory, pointers, indirection, and linked lists.

• Topic: We talked about dynamic memory and linked lists.

  Question: What is the benefit of having doubly linked lists?

  One minute response: Efficient bi-directional traversals and somewhat easier node manipulations (at the cost of doubling the link overhead).

• Topic: Manual storage management, automatic storage, lists.

• Topic: Finished with linked lists, using nodes, and linked list functions.

  Question: No questions.

• Topic: We learned about linked lists.

  Question: How do we reference a class within a class.

  One minute response: Within the enclosing class you can access the enclosed class as normal. Outside the enclosing class, and depending on the access permissions, you have to use the scope operator (public), you have normal access (protected) or you can't access it (private).

• Topic: We learned about linked lists.

  Question: Is there a sort faster than radix?

  One minute response: No, not unless you have some special knowledge you can exploit (which is why radix sort is O(n)).

This page last modified on 16 July 2003.