CS216, Exam 3, Fall 2005:

About our final exam:

• When: Tuesday, December 13, from 9am through noon.
• Where: Our class meeting room, MEC 341
• Mix of New and "Old" Material: Around 50-65% of the material will be on material since Exam 2, but the remainder will review of material from the earlier exams.
• For the material from the previous two exams, I will try not focus on low-level detail but on higher-level important topics. But they might include questions on order-classes for algorithms' complexity.

These are the topics and the readings since Exam 2. You should also review the work you did for the labs:

1. Graphs. Basic definitions; data structures for graphs; shortest parth algorithm for unweighted graphs. (Slides and sections 9.1 and 9.3 through page 346 339 only.)
2. Some basic UNIX shell and command principles. (See the tutorials from Lab 8 Part 1.)
3. Huffman Encoding (See the slides and Section 10.1.2.)
4. The ADT Priority Queue and the binary heap data structure. (See the slides and pages 211-222 in the book.)
5. Memory Hierarchy, Locality, Processor Caches. (See the slides.)
6. x86: “Tiny Guide to x86 Assembly"
   • For Exam 3, you will be responsible for the C calling conventions (e.g. handling registers and parameters on the stack, etc.). You might be asked about code that jumps to a function and shares information between caller and callee solely through registers. So there might be a question like #10 in the Spring 2005 exam 2 sample exam.

Topics etc. from Exams 1 and 2:

• Exam 2: On the main page you will find a link (also available here) you'll find lots of info the topics that you studied for on Exam 2. This page also has links to 3 sample exams.
  Solution for Exam 2 will appear at that same place on the main page soon.
• Exam 1: There are sample exams on the main class home page. Also, the solution for our Exam 1 is there.

Some exam policies:

• This exam is closed note, closed book
• You will have three hours total to complete the exam if you need that much.
• There won't be a need for calculators for this exam.
• We'll follow the Engineering School rule that if you have three exams in 24 hours, you can request that one of your exams be changed. If you want to request that from me, contact me by Thursday, Dec. 8, and explain the situation. I will need to have your exam completed by noon on Weds., Dec. 14, at the latest in this situation.
• If you are an LNEC student needing extra time, contact me and let me know if you want to do it all in one go on the exam day, or if you need to split it into two parts.

Sample Exams:

We don't have sample exams for the final. (I'm not holding out on your; we've never done this for the final.) By this point, you have a good idea what our exams are like. Studying the topics lists here and materials given earlier are you best strategy for preparing for this exam. If you have questions or would like to see an example of something, contact the instructor and we'll try to help.

Concepts and Skills by Topic for the "New" Materials Part of the Final:

Graphs

• Definitions and terminology
• Representation of graphs in data structures
• Shortest paths in unweighted graphs using breadth-first search (Section 9.3 and 9.3.1, pp 333-339)
  • Use of queue in this algorithm; it's time-complexity
• Not on exam: topological search (section 9.2); Dijkstra's shortest-path on weighted graphs (section 9.3.2)

UNIX Concepts (Note: the questions here will mainly address principles and concepts and try to avoid the details of the individual commands.)

• I/O redirection and pipes (Tutorial 3 from Lab 8 part 1)
• File permissions (Tutorial 5)
• Processes and jobs (Tutorial 5)
• Important concepts of the make utility (see the Tutorial for Lab 8 part 2)

Huffman Encoding

• Concepts from slides and lecture, including lossy and lossless compression
• Using variable-length character codes using prefix codes
• Building a prefix-code-tree from a table of character frequencies
  • See notes, slides and the handout we gave out.
  • Note use of priority queue in this algorithm
• Cost of a Huffman tree
• Using a prefix-code-tree to decode a compressed file
• Overall software design of Huffman encoding and decoding -- don't forget how we designed and built programs to do this in Lab 8

Priority Queues and Heaps

• Priority Queue ADT: its definition (model of data stored, operations on that data)
• Data structures to implement this (arrays and linked lists for either an unsorted list or a sorted list; heap)
• Binary tree properties needed to store a binary heap in an array (e.g. the heap structure property)
• Heap order property. (Note the difference between a min-heap and a max-heap; see footnote on page 214).
• How these operations work: insert(), deleteMin() using the "percolate down" strategy. Also, building a heap of n items by calling insert() on each of the n items.
• Time complexity for insert(), deleteMin()

Memory Hierarchy, Locality, Processor Caches

• Definitions and principles: cycle; memory latency; temporal vs. spatial locality
• Caches: Level 1 and Level 2; why they're used
• Time-cost tradeoffs related to use of caches

x86 Assembly Language

• Questions will focus on the C calling conventions (e.g. handling registers and parameters on the stack, etc.).
• But, note that (as explained at the top) there will be questions that will review material from the earlier exams, including x86 questions from Exam 2. As I said, for the material from the previous two exams, I will try not focus on low-level detail but on higher-level important topics.