Week 1, Monday Lecture

  1. What is a variable and what are its attributes?
  2. What is an l-value and how does it differ from an r-value?
  3. How does a reference (in C++) differ from a variable and a pointer?
  4. How is memory space freed for use by another value?
  5. If a memory pointer is changed, but the previously allocated space is not returned to the memory pointer, how can that space be reclaimed?

Week 1, Wednesday Lecture

  1. What is the difference between pass-by-value and pass-by reference?
  2. What is the difference between formal and actual parameters?
  3. If a parameter, that has been passed-by-reference, has its value changed does the value of the variable in the main program referenced by that parameter change?
  4. Which of pass-by-reference and pass-by value uses more space?
  5. Which of pass-by-reference and pass-by-value is faster? (Why?)
  6. Which of pass-by-reference and pass-by-value is better? (Why?)
  7. What is a member variable, and why is it often private?
  8. What is the signature of a function and how is it used?
  9. Why may it be convenient to use more than one type of constructor?
  10. What is a copy-constructor and why is it important?
  11. What is the difference between an accessor and a mutator?

 

Week 1, Friday Lecture

  1. What is code reuse and how do: inheritance, polymorphism and templates fit into this activity?
  2. What is a base class and how does it relate to a derived class?
  3. If there are two functions, one in the derived class and one in the base class, with the same signature, which one will be called if a pointer is used that is a pointer of the base class type? if a pointer is used is a pointer of the derived class type?
  4. What is a virtual function, and what makes a virtual function also a pure virtual function?
  5. What is the relationship between an abstract class and a concrete class?

Week 2, Monday Lecture

  1. When is a template used? and what can be accomplished through the use of a template?
  2. In the detailed model of a computer what is the meaning of the following terms: tfetch, tstore, t+, t-, t<, tcall, treturn, tf(x), t[.]
  3. Why does a for loop have 3 different estimates for performance?
  4. What is an estimate for the execution time for a statement of the following form: x = 10*y+7*z?
  5. Why is recursive function analysis important?
  6. How can a recursive function definition be analyzed?
  7. Why are data dependencies difficult to analyze?

Week 2, Wednesday Lecture

  1. How do data dependencies impact algorithm analysis based on the detailed model of a computers operation?
  2. What is a harmonic number, and what is the closed form representation of Hn?
  3. How is storage allocation and release modelled in the detailed computer model?
  4. Why is the detailed model flawed and how can it be simplified?
  5. In the simplified model, how are the various t values related?
  6. What is an arithmetic series?
  7. What is the closed form solution for the sum of the integers from 1 to n?
  8. What is a geometric series?
  9. What is a closed form solution for the sum of ai with i from 0 to n?
  10.   When evaluating the cost of execution of a pair of loops of the following form

for (int i = 0 ; i < n ; i++)

for (int j = 0; j < i; j++)

x = i + j;

How often is the j<i comparison performed?
How often is the i<n comparison performed?
How often is the addition statement performed?

 

Week 2, Friday Lecture

  1. How are data dependencies handled in the simplified model of computation?
  2. How are recursive functions handled in the simplified model of computation?
  3. How was the average value calculated for the data dependent Program 2.8?
  4. If you are able to write a program that in a fixed amount of time, reduces the problem complexity by a factor of 2, what performance would your expect?
  5. What if you could reduce the complexity by a factor of 10?
  6. What is the mathematical definition of O (big Oh)?
  7. What roles do the values of n0 and c play in the definition?
  8. If f(n) = O(g(n)) is f(n) < 100*g(n)?
  9. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)) why does f1(n) != f2(n)? (How could this be proven?
  10. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)) what does f1(n) + f2(n) = ?
  11. Why?

 

Week 3, Monday Lecture (Slides 88-112)

  1. What is the Rule-of-Sums for Asymptotic Analysis?
  2. When can f(n) = fa(n)+fb(n) be simplified to f(n) = O (fa(n))?
  3. What is the rule-of-products for Asymptotic Analysis?
  4. If fa(n) = Og(n) and f(n) = fa(n) * ga(n) what is an upper bound for f(n)?
  5. Prove that O is transitive.
  6. What is an asymptotic estimate for a polynomial of degree 21?
  7. What is an asymptotic estimate for logkn?
  8. How is a tight bound proven on a O estimate?
  9. What do we know about a particular program, given that its performance estimate is O(n) ? (give 4 examples!)
  10. Are there O estimates for all execution times?
  11. Why do we drop constants, and keep only the most significant terms in O expressions?
  12. What performance estimate is associated with exponential performance?
  13.   What is the specification for W and what does it mean?
  14. What is the lower bound on the value of a polynomial of degree 23?
  15.   What is the specification for Q and what does it mean?
  16. What is the specification for o (I.e. little oh) and what does it mean?
  17. If you are to estimate the performance for several sequential statements, how are their asymptotic estimates combined?
  18.   If you are to estimate the performance for statements in a loop, how are their asymptotic estimates combined?
  19. If you are to estimate the performance for data dependent (conditional)   statements, how are their asymptotic estimates combined?

 

Week 3, Wednesday Lecture (Slides 115-132)

  1. What is a Fibonacci Number?
  2. How can the performance of loops be estimated?
  3. How can the performance of recursive calls be estimated?
  4. What is a lower bound estimate for the performance of the recursive version of the Fibonacci number implementation?
  5. How can we analyse an estimate that contains both accurate terms and asymptotic estimates?
  6. What is a Bucket Sort?
  7. What is its performance, and how does the analysis of its performance estimate demonstrate the importance of using all of the available information regarding an algorithm?
  8. Given an estimate for the performance, how can that estimate be verified?
  9. Should the actual running time compare exactly with the g(n) term in the O(g(n) estimate?
  10. How can you compare the estimate with the value?
  11. Why may your estimate prove too big (and how would you tell this)?

 

Week 3, Friday Lecture (Foils 133-150)

  1. What is the importance of the foundational classes?
  2. What are the two most important foundational classes?
  3. What characteristics are missing from the built-in arrays available in C++?
  4. What are the two component classes for the implementation of the Array Class?
  5. How do you estimate the amount of memory required for this array?
  6. Given that the specification is for a template, how do you include the amount of space required for the data, when you do not know what type the data is?
  7. In the execution time estimate, for the constructor (Array(int n, int m), what does the term n*Script_T(T::T()) represent?
  8. In the execution time estimate, for the copy constructor (Array(Array<T> const& array), what does the term n*Script_T(T::T(T&)) represent?
  9. What happens to these times if type T is a built in type?
  10. What is an exception in C++?
  11. Given an array of type T, and length n, why is the following expression an estimate for the time to change the length of the array to m?

mScript_T(T::T()) + min(m,n)*Script_T(T::T(T&)) + n Script_T(T::~T()) + O(1)

  1. What is a sentinel? and why is it used in some linked lists?
  2. What are the potential special cases insertion/deletion into a linked list? For the list that follows, which ones apply to which of the 5 implementations shown in foil 148?
Insertion into an empty list.
Insertion at the start of a (non-empty) list.
Insertion at the tail.
Deletion from and empty list?
Deletion from at the head of the list.
Deletion from the tail

Week 4, Monday Lecture (Foils 151-161)

  1. Why is the constructor for the ListElement Object private?
  2. How can space be estimated based on a class definition?
  3. What would the estimate be if we used the LinkedList template to construct a list of LinkedLists of integers?
  4. What is the function of Purge, and why does the destructor take so long to execute?
  5. What special cases have been demonstrated in the member functions for this implementation of the LinkedList?
  6. How is the copy constructor implemented?
  7. How does the copy constructor differ from the assignment operator?

 

Week 4, Wednesday Lecture (Foils 161-174)

  1. How are the blackboard in EL 105 held up?
  2. Please review foils 162and 163 on your own.
  3. How can a multi-dimensional array be implemented using a one-dimensional array?
  4. What does the mapping from multiple dimensions to a one-dimensional mapping have to provide?
  5. How do row major and column major layout techniques differ?
  6. Why is the product term needed in the suggested mapping function?
  7. How can the multi-dimensional syntax of c++ arrays be used by the new Array2D class?
  8. What is the expected execution performance for matrix multiplication using the technique discussed in class?

Week 4, Friday Lecture (Foils 175-193)

  1. What are Abstract Data Types, and how do they relate to C++ Classes?
  2. What is a class hierarchy?
  3. What does an Abstract Class specify?
  4. Why can it not be instantiated?
  5. How does a concrete class differ from an Abstract class?
  6. In the hierarchy described in the text, what are objects? containers? and Wrappers? and how do they relate?
  7. What is the purpose of the NullObject Class?
  8. How is it instantiated?
  9. What is a visitor and how does it work?
  10. Why do we need/use visitors?

Week 5, Wednesday Lecture (Foils 194-210)

  1. What is an Iterator? and How does it differ from a Visitor?
  2. When would you use each?
  3. Which one must be written by the implementer of the class and which one could be written by the user of the class?
  4. What is the difference between direct containment and indirect containment?
  5. What are the advantages of each?
  6. How is Ownership used during the destruction of a container?
  7. What are searchable containers?
  8. What is a stack (in the abstract)?
  9. How is the Iterator specified in the stackasa... class?  Why?

Week 5, Friday Lecture (Foils 211-221)

  1. What is the differences among the Classes - Stack, StackasArray and StackasLinkedList?
  2. In the Array implementation, what does array[count] contain, and as a result of this design decision, how is data accessed (pushed or poped)?
  3. What is the (nested) class Iter used for?
  4. Why is it private?
  5. In the destructor (array or linked list) how does the indirect containment design decision interact with the ownership property?
  6. In the implementation of the Iterator for the StackasArray class, what are the special conditions? and what does return *stack.array[position] return?
  7. Although the implementations of StackasArray::Iter differs from StackasLinkedList::Iter, how does the user treat them differently?
  8. What is the effect of using the StackasArray class to implement a stack? What is the penalty case? What characteristic would cause this problem to be aggravated? (Foil 217)
  9. Compare and contrast StackasArray::Purge and StackasLinkedList::Purge.
  10. Compare the need for special-case tests in the implementation of StackasArray and StackasLinkedList.
  11. Compare the performance of StackasArray::Pop() and StackasLinkedList::Pop().
  12. Compare the performance of StackasArray::Accept and StackasLinkedList::Accept. ... as well as any other functions.

 

Week 6, Monday Lecture (Foils 222-241, leaving 225-231 as a reading exercise)

  1. Compare/Contrast the Iterator for the Array and LinkedList implementations of the stack.
  2. How could you design the test for an empty (or full) queue when that queue is implemented as an array.
  3. How is the wrap-around counter implemented?
  4. What are the common characteristics of the Array implementations for the Stack and the Queue?

Week 6, Wednesday Lecture (Foils 241-264)

  1. What are the similarities between the array implementations for the stack and the queue?
  2. In the linked list implementation of the queue, why are the insert/delete operations O(1)?
  3. How does the tree traversal change if a stack is used instead of a queue to store partially expanded trees?
  4. What is a Deque?
  5. What is the difference between specialization and generalization?
  6. Why might the generalization approach require two implementations?
  7. What has multiple inheritance been used for the implementation of the Deque?
  8. Why is the implementation of DequeueTail significantly slower than Dequeueing at the head (for a linked list implementation of a Deque)?
  9. What is the speed/space trade-off associated with the use of a doubly-Linked list?

Week 6, Friday Lecture (Foils 265-286) ... Foils 281-286 a Reading Example.

  1. What is the difference between an ordered list and a sorted list?
  2. What how does an ordered list, implemented as an Array<>, find an element?
  3. What how does an ordered list, implemented as a LinkedList<>, find an element?
  4. Complete the following table
Function Ordered List as Array Ordered List as LinkedList
Insert    
IsMember    
Withdraw    
Insert After/Before ...    
  1. How does the character of the O(n) InsertBefore (for Array version) compare to the O(n) InsertBefore (for the Linked List version)?
  2. Which is the better implementation?

 

Week 7, Monday Lecture (Foils 286-297), Reading 298-301

  1. What is a sorted list?
  2. How does a binary search work?
  3. How can it be implemented with an array implementation?
  4. What is the performance of a binary search?
  5. Complete the following table. (Intuitively!)
Function Array Implementation Linked List Implementation
Insert    
IsMember    
Find ... etc.    
  1.   Explain/Justify the differences between the performance of Find and FindPosition as a function of the implementation strategy?
  2. Given 2 implementations for a given problem, one based on an array and one based on a linked list, how could you compare the size needed for n data elements?  What is static vs dynamic storage? Usually which scheme has less overhead?

 

Week 7, Wednesday Lecture (foils 302 - 315)

  1. What is Hashing?
  2. What is its goal?
  3. Why is O(1) (worst case) Insert and Find not possible?
  4. What is a collision?
  5. Why are there more possible Keys than space?
  6. What is a hash function?
  7. What are the characteristics of a good hash function?
  8. What is spreading?
  9. What is it main drawback to the division method?
  10. How does the middle squares method work, what is its draw back?
  11. Repeat 10 for multiplication and Fibonacci methods.
  12. What are the steps required for the translation of a general object (i.e. non-integer) to an integer between 0 and M-1?

Week 7, Friday Lecture (Foils 316-332)

  1. How could strings of length n be converted to an integer between 0 and M-1?
  2. If addition is used, what are the drawbacks?
  3. If shifting is used, what must be remembered?
  4. What is the hierarchy associated with the ancestry of a ChainedHashTable?
  5. What does the member function H do?
  6. What are the two steps involved in H?
  7. How does a Hash Table, based on Separate Chaining operate?
  8. How may the order of insertion affect the performance of the hash table?
  9. How much space is required for the separate chained hash table with n values stored in a Hash Table with an array with M entries?  How does this compare with a sorted Array or a sorted LinkedList for this many entries?
  10. What is the worst case performance for a separate chained hash table? how does this compare with a sorted Array or a sorted LinkedList for this many entries?
  11. How is the average running time calculated?
  12. What are the main assumption used for this calculation? (equally likely keys for insertion and finding)
  13. What is the load factor for a hash table?
  14. What does a l of approximately 1 mean? 
  15.  

Week 8, Monday Lecture (Foils 333-349)

  1. Guest Lecturer

Week 8, Wednesday Lecture (Foils 350-367)

  1. What is quadratic probing?
  2. What is the sequence of probes used following a probe that contains an element, but not the one be sought?
  3. Why do we keep Scatter Tables that are to be probed quadratically less than 50% full?
  4. How does this probing technique reduce primary clustering?
  5. What is double hashing, and why use it?
  6. Show, by use of an example, how linear probing, quadratic probing and double hashing compare? ... for successful and unsuccessful searches?
  7. What are the good properties for a hash function, and how do these differ for a secondary hash function?
  8. How would a hash table with M = 72 cause a problem if double hashing were to be used? ... list 3 values of h' that would cause a problem.
  9. What is lazy cancellation, when is it used, what are the alternatives?
  10. hat is the worst case performance for a scatter table that uses double hashing?
  11. What assumptions are made for the uniform hashing analysis model?
  12. What does this mean relative to linear probing estimates?
  13. Compare the space required for the various hash and scatter tables discussed this term? Is one always smaller? (no)
  14. What is the expected Unsuccessful search time for a table with M = 23. for the following values of n (the number of entries in the table at the current time)?
n l (n/M) U(n)= 1/(1-l)
0 0 1
1 1/23 23/22
2 2/23 23/21
3 3/23 23/20
  1. By Extension, how many probes would be required to find the third element inserted into the table?
  2. And what would the average number of probes required for a table with 17 entries.
  3. How is this linearized and calculated?

Week 8, Friday Lecture (Foils 367-390)

  1. How is a tree defined?
  2. Explain the following terms: degree of a node, a leaf, child, parent, grandchild, grandparent, path, pathlength, level (depth) vs height, ancestor (as opposed to proper ancestor), descendant (vs proper descendant).
  3. What is an N-ary tree?
  4. What is the difference between an internal and an external node?
  5. What is the difference between an ordered and an oriented tree?
  6. How many external nodes are there on a four-ary tree with 100 internal nodes?
  7. Given 1000 nodes in a 5-ary tree, what is the minimum height of the tree (and what is the maximum height)?
  8. What is the maximum number of leaves on a tertiary tree of height 14?

Week 9, Monday Lecture (Foils 391-417)

  1. What is a binary tree?
  2. How many external nodes are there in a binary tree with 207 internal nodes?
  3. For a binary tree of height n, what is the minimum height?
  4. What is the difference between a breadth-first and a depth first traversal of a binary tree?
  5. What is the meaning of pre-order and post-order traversal in general and binary trees?
  6. Why is inorder traversal defined for binary trees and not for general trees?
  7. How do infix, prefix and post-fix expression notation relate to inorder, perorder and post order tree traversal?
  8. In the implementation described in the text, how is a generalized traversal (depth first) implemented?

Week 9, Wednesday Lecture (Foils 417-445)

  1. How is a queue used to implement a breadth first search?
  2. If a stack were used, what type of depth first search would be implemented?
  3. If a general tree is to be implemented why is a linked list used to store the list of siblings?
  4. If you know that the maximum number of children for a given general tree is m how could an array be used? when is the array preferred (2 cases ... 1) space based and 2) performance based).
  5. If we were to implement a Binary tree with 100 nodes as: a general tree, an N-ary tree (with N=2) and a Binary tree, which technique would require the most space (assume all pointers are the same size and that the tree uses indirect containment).
  6. What is a search tree and how do the node (key) values differ from a normal tree?
  7. Are Binary Search Trees (BSTs) unique? (I.e. for a given number of nodes is there only 1 tree that can store those values?
  8. What is the algorithm for searching a BST?
  9. For a BST with n = 127 nodes, what is the maximum number of comparisons required to find and element that is in the tree? what is the minimum number of comparisons required to find that an element is NOT in the BST?
  10. How many elements are in a perfect BST with a height h?
  11. How is a perfect BST defined?
  12. In a perfect BST, what is the worse case (successful) search time (measured in number of comparisons)?
  13. In a perfect BST, what is the worse case (unsuccessful) search time (measured in number of comparisons)?
  14. When analyzing the average case performance, what assumption is required, but invalid regarding searching for an element that is in the tree?

Week 9, Friday Lecture (Foils 446-473)

  1. If we assume that all nodes are equally likely targets for a search in a BST, and further we assume that all possible BST structures as equally likely for n nodes, what do we expect to be the number number of probes (comparisons) for a BST with n nodes?
  2. What is the number of probes to find that an element is not in the BST?
  3. Can we rely on the results of 1 and 2?  why?
  4. What is the difference between the average internal path length and the average depth of a node?
  5. What is the mathematical relationship between the average internal path length and the average external path length?
  6. What is the average internal path length for a tree with 100 nodes?
  7. How do we find the maximum in a given BST? (I.e. Write an algorithm in pseudo-code to find the Maximum element in a BST, and what is its asymptotic performance?)
  8. How do we find an element in a given BST? (I.e. Write an algorithm in pseudo-code to find an element in a BST, and what is its asymptotic performance?)
  9. What is the worst case for each of these previous (2) questions?
  10. How are items added to BST?
  11. How are objects removed from a BST?

Week 10, Monday Lecture (Foils 474-488)

  1. What is an AVL balanced binary search tree?
  2. How does the performance for an AVL balanced BST differ from that of an average BST?
  3. What is the balance condition for a node in an AVL balanced BST?
  4. What is the height of an AVL balanced BST as a function of the number of nodes in the BST?
  5. How are items inserted in to an AVL balanced BST?
  6. What is a single rotation, and how is it performed?
  7. What is a double rotation, and how is it performed?
  8. Both types of rotations assume that no node higher in the tree than the lowest node with a new balance factor of magnitude 2 will be affected by the insertion ... convince yourself you understand why this is true.
  9. When is a double rotation used?

 

Week 10, Wednesday Lecture (Foils 490, 516-531)

  1. What is a Priority Queue?
  2. What functionality is required of a Priority Queue?
  3. Which previously examined data structures could be used for a Priority queue?
  4. What is a complete Binary Tree? How is it defined?
  5. What is a complete N-Ary Tree? How is it defined?
  6. How many nodes are there in a complete tree of height h?
  7. How can an array be used to store a complete binary tree?
  8. How are the pointers in the tree stored?
  9. Where are the children and parent of node i located?
  10. What is a heap?

Week 10, Friday Lecture (532-542, 569-576)

  1. What is the ordering of the nodes in a binary heap?
  2. What is the structure of a binary heap?
  3. How is the structure maintained when an element is inserted into a heap? (O(1))
  4. How is the structure maintained when an element is deleted into a heap? O(1))
  5. How is the Order maintained when an element is inserted into a heap? O(log n)
  6. How is the Order maintained when an element is deleted into a heap? O(log n)
  7. If the heap is stored in an an array how are the links kept?
  8. Which element is deleted from a binary heap?
  9.   What are direct solution strategies?
  10. How do brute force techniques differ from greedy algorithms?
  11. Which of brute force and greedy algorithms always produce the optimum solution?
  12. Why would you settle for a solution that is non-optimal?
  13. What is an objective function?
  14. What is a constraint?

Week 11, Monday Lecture (Foils 576-616)

  1. What separates a greedy algorithm from a brute force algorithm?
  2. What is the definition of the 0/1 Knapsack Problem? (formal and informal)
  3. What is the weight, capacity and profit in the 0/1 Knapsack Problem?
  4. How do Greedy by Profit, Greedy by Weight and Greedy by Profit Density differ?
  5. How does a backtracking algorithm differ from the direct solution techniques (greedy or brute force)?
  6. What is the mathematical formulation of the balancing scales problem?
  7. What is the objective/goal function?
  8. How can the solution to this problem be represented in a tree form?
  9. What do the leaves in the tree represent?
  10. What do the interior nodes represent in the solution?
  11.   How do we implement a backtracking algorithm based on the tree representation?
  12.   If we just use a tree traversal technique to test the solutions, how many solutions must be tested?
  13. If we use a branch and bound technique, how many solutions are tested?
  14. How does a branch and bound technique reduce the solution space?
  15. What criteria is used to reduce the solution space?
  16. What is a divide and conquer algorithm technique?
  17. How are the various implementations similar?
  18.   What is the generalized expression for the execution time for a divide and conquer?
  19.   What is the meaning of the terms: a, b, n and k terms in the following expression: (T(n) = qT(ceiling(n/b)) + O(nk)).
  20.  

Week 11, Wednesday Lecture (Foils 617-622, 646-658)

  1. Review the 3 cases for analysis of a divide and conquer algorithm.
  2. What is a sorter?
  3. What are three general classes of sorting algorithms?
  4. What is the basic Insertion Sort Algorithm?
  5. What is an inversion?
  6. How many inversions are there in an average list of n distinct elements?
  7. In the basic insertion sort, how many inversions are corrected for each movement/comparison?
  8. What is the performance of the best/average/worst case basic insertion sort?
  9. What is the performance of the best/average/worst case binary insertion sort?

Week 11, Friday Lecture (Foils 659-678)

  1. What is the basic exchange sort? (how does it work)
  2. What is quicksort?
  3. What is a pivot and how is it selected?
  4. How does quicksort work?
  5. What is one suggested pivot selection technique?
  6. What is the recursive expression for the execution time for using quicksort on a list of n elements?
  7. What is the situation that yields the poorest performance?
  8. What is the situation that yields the best performance?
  9. What is worst case performance of quicksort?
  10. What is the best case performance of quicksort?
  11. What is the average case performance for quicksort?
  12.   What is a selection sort (and how does it work)?
  13. What is its performance?
  14. Complete the following table. (both the asymptotic estimate and the situation that leads to the best and worst cases.
  15. Technique Best Case Worst Case Average Case
    Straight Insertion      
    Binary Insertion      
    Bubble      
    Quicksort      
    Straight Selection      
    Heapsort      
    Merge Sort      
    Radix Sort      

Week 12, Monday Lecture (Foils 679-708)

  1. How does the heapsort relate to a straight selection sort?
  2. What is the function of the percolate operation, and what is its (execution time) cost?
  3. How can the percolate function be used to turn an unsorted array into a heap?
  4. What is the relationship between the time to turn an unsorted array into a heap and the sum of the heights of all of the nodes in a tree? Why?
  5. How does mergesort work and why does it need room for two copies of the data?
  6. Can a merge sort algorithm be used on 2 lists of different sizes?
  7. Can a merge sort be run on 10 lists of different sizes? why would you?
  8. What assumptions are needed to show that there is a lower bound on sorting, why is that lower bound (O(nlogn))?
  9. Name 2 distributed sorting techniques and explain how they break this lower bound?
  10. Explain the differences between bucket sorting and radix sorting.
  11.   In the sample execution times, why is quicksort faster than heapsort, despite them both having an asymptotic performance estimate of O(nlogn) ?

 

Week 12, Wednesday Lecture (Foils 709-732)

  1. What is a graph and where is it used. (Be sure to include ideas associated with data inter-related in complex and relatively unconstrained ways.
  2. What is the meaning of the following terms: Directed Graph, Digraph, vertex, edge, G=(V,E), directed arc, head, tail, emanate, incident, out-degree, in-degree, Path length, simple path, cycle, loop, length of cycle, simple cycle, Directed Acyclic Graph, DAGs, Undirected Graphs, Adjacency Matrix, Adjacently List, a Sparse graph, and a dense graph.
  3. How does the definition of an edge in Directed and Undirected Graphs differ?
  4. How do the terms emanating and incident change when Directed and Undirected graphs are compared?
  5. Where/How is data associated with edges and vertices in a graph?
  6. How much space is needed to implement an Adjacency Matrix? Adjacency List?
  7. Compare the performance of Adjacency Matrix and the Adjacency Lists in the finding of an edge, listing all of the edges, etc.

Week 12, Friday Lecture (Foils 733-755)

  1. What is needed to represent: an edge, a node?
  2. Why might a user of a graph need an iterator that iterates over the edges emanating from a given node?
  3. What is the execution complexity of a depth first traversal algorithm if the underlying graph is represented as Adjacency Lists? as an Adjacency Matrix?
  4. How much space is needed by each of these techniques?
  5. How does the traversal avoid revisiting a node more than once? why is this necessary?
  6. How does depth first traversal differ from breadth first traversal?
  7. What is a topological sort?
  8. What greedy algorithm can be used to find the topological sort sequence for a given graph?
  9. What is the purpose of a shortest path algorithm?
  10. What is a single-source shortest path problem?
  11. What is the weighted path?
  12. What is the meaning of the weighted path if all of the weights are the same?
  13. How can the shortest path be found if the graph  is a DAG?
  14.   How can negative weighted links be handled?
  15. Under what circumstances will Dijkstra's algorithm not work?