create new tag
view all tags

Algorithm Analysis and Design

Midterm Study Guide

The questions will largely be similar to the exersises in the text and homework. Study the following sections carefully, and be able to solve any of the problems in the exersise or problems set sections refered to below.

Chapter 3

Know how to prove algorithm are in a given Asymptotic complexity. You will need to KNOW the definitions of O, o, Ω, ω, and Θ, and be able to prove a give funciton is in a given class.

Consider the exercises at the end of sections 3.1, 3.2, and the problems at the end of the chapter. You should be able to solve any of these.

Also be able to examine code blocks, and provide and justify asymptotic complexity analysis of the code.

Graph Theory

Be able to reason and prove statements about graphs as discussed in class.

Proof of alorithm Correctness

You be able to use induction and loop invariants to proof a given algorithm is correct. I will expet to see a base case, an inductive hypothesis, and proof of the inductive case, and a proof of termination with the correct results.

Chapter 16
  • Know what it means to be a greedy algorithm, and be able to write proofs and do run time about algorithms similar to those covered in this chapter.
  • Be able to describe and implement binary min heaps as described while doing Huffman Coding
  • Be able to answer questions like those on pages 421-422 (exercises 16.1-1 through 16.1-5)
Chapter 22

Graph Theory Algorithms

  • Representations of graphs
  • Cost of operations for the these representations
  • Be able to answer questions like those on pages 592-593 (exercises 22.1-1 through 22.1-4 only)
Chapter 23
  • Understand and about able to write proofs about minimum spanning trees
  • Be able to answer questions like those on page 629 (exercises 23.1-1 through 22.1-5 only)
  • Understanf Kruskel and Prim algorithms
  • Be able to answer questions like those on pages 637 (exercises 23.2-1 through 23.2-8)
Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r6 - 2016-11-12 - JimSkon
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback