CS 345 Final Exam Review

Final Review

• Exam will consist of no more than 25 multiple choice questions. I will reuse some questions from the midterm exam. Be sure to study the midterm redo in D2L. You should still have access to the midterm. Each question includes your response and the correct answer.

(1) Choose quizzes from Assessment menu, (2) find midterm exam in list, (3) select attempts from menu attached to quiz title.

• HINT: review the homework assignment solutions. Walk through the hw requirements and note how certain requirements were met (in the solution)

you coded alot of programs in this course. As you may have noted from the midterm my questions are geared towards your understanding of how and why certain code works and possibly works better than other code – the algorithmic level. Please keep this in mind as you prepare.

DSAP Chapter 1 basic python skills

• loops
• list comprehensions
• range function
• return statements
• branching
• exceptions
• functions (formal arguments, actual parameters)
• variable scope
• mutable and immutable data types
• pass by reference pass by value
• unit tests in python

DSAP Chapter 2 object oriented programming

• classes
  • definitions,
  • object instantiation,
  • class methods,
  • constructors,
  • class attributes
  • Abstract Data Types

DSAP Chapter 4 recursion

• types (linear, binary, multiple, tail recursion)
  • be able to recognize these types in code
• understand the trace on p. 170 fig. 4.10
  • be able to read and trace recursive code

DSAP Chapter 6 stacks, queues, and deques

• understand the behavior of stacks and queues implemented as lists (arrays)
• understand the algorithm efficiency of these ADT’s implemented as lists.

DSAP Chapter 7 linked lists

• understand the behavior of stacks and queues implemented as linked lists.
• understand the algorithm efficiency of stacks and queues implemented as linked lists.
• understand circular queues and related operations: rotate, enqueue, dequeue

Algorithm Analysis: Problem Solving with Algorithms…

• understand the reason for doing algorithm analysis
• be able to perform algorithm analysis on short bits of code
• understand O() notation and the difference between the three that we discussed at length (1), (n), (n*n)
• pay attention to the discussion about efficiency of lists in python (e.g., pop() vs. pop(0))
• **Do the exercises: **

pdf

interactive

New since midterm:

trees

• Schedule: 12, 13, 14
• DSAP Chapter 8
• Concepts:
  • you should be able to recognize traversal orders (preorder, postorder, inorder, breadth first)
  • heaps (min heap and max heap)
  • heap order property
  • how do heaps maintain heap order property (review percUp and percDown) ?
  • why are priority heaps efficient for certain applications?
  • difference between binary trees and other trees

Advanced Python:

• Generator/Iterators, lazy evaluation
• overrides and overloads: know the difference
  • __gt__, __lt__, __get__
• understand deque: deque
• understand why python list operation pop(0) is inefficient.

Hashmaps

• Schedule: 15
• understand the purpose and operation of a hash function.
• understand the purpose and operation of a compression function.
• what is a collision and what is one way we explored handling collisions