15-105 FINAL EXAM INFORMATION - SPRING 2009

The following list of topics is a basic study list of things you should review for the final exam. The final will consist of 10 questions (10 pts each). The questions will be written in a similar format as you've seen on the midterm exams. NOTE: The list below contains more items than you will see on the exam, but the topics of the exam will focus on some subset of these items.

• History of Computing, famous people and their contributions - Babbage, Hollerith, von Neumann, Moore, Hopper, Turing, Dijkstra

• Algorithms - tracing an algorithm, converting an algorithm to a flowchart, reading a flowchart to analyze an algorithm, completing a missing step in a flowchart

• Data structures - how a stack and queue work, how to build a binary search tree, how to build a heap, how to store a graph

• Programming Languages - how a compiler works, EBNF notation, understanding and writing Prolog statements

• Algorithmic Techniques - tracing a recursive computation, building and using Huffman trees, shortest path in a graph

• Correctness and efficiency - using invariants to show a loop is correct, using induction, big O notation, comparing sorting algorithms (bubble vs. merge)

• Tractability and Undecidability - satisfiability, map coloring, traveling salesperson, P vs. NP, word correspondence problem, undecidability

• Universal Computing - Analyzing a simple Turing machine that solves a computational problem

• Parallel and Distributed Computing - determining the sequence of operations in a parallel system to achieve a given result, the effect of parallel computation on the notion of computability, pipelining, how operating systems multitask, the principle of deadlock

• Cryptography - Caesar cipher, public key systems: being able to encrypt or decrypt a simple message with signatures

• Artificial Intelligence - Turing test, describing the size of a game tree for a given two-player game, the difference between a heuristic and an algorithm