# What You Should Know By Now

The format:

**Topic**- List of subtopics/ "Be able to do *"
*Resources:*- List of resources pertaining to topic, with pointers to acquiring them as appropriate

Please feel free to comment on resources or add new ones that you find. At some point we should open up a ReadingRoom wiki page to collect info on course resources, how good they are, where to find them, what they're good for, etc. Whatever works. --Katie

**Resource Locations Key**

*CCL*- Computers and Cognitions Lab, aka AC 312. Lynn is sometimes here. There are lots of CS (and Cognitive Science) books here.*Olin Library*- The library in the OC has a few good books.*Your Algorithms Textbook*- whatever book you bought that covers, uh, algorithms. Cormen is a good example.*Your Theory Textbook*- I don't remember if this is what we called it, but if it covers finite state machines, P and NP, this is it. Hopcroft, Motwani, Ullman or Lewis and Papadimitriou is a good example; so is Sipser.*"see CourseLinks"*- means there is probably a relevant link in the hugetastic list we built over the summer. It is on Katie's todo list to reorganize that page so it is more useful and less daunting and crazy.

**And for your navigational eptitude:**

Contents

## Dec 14, 2004

By this date, you should know all of the topics below.

**Turing Machines (read, construct, what they can do)**- Halting
- Computability

**Graph Theory**- What is a graph (directed, undirected)
- Trees (traversal breadth-first and depth-first)
- Minimum spanning trees (Prim's Algorithm)
- Single source shortest path (Dijkstra's Algorithm)

**NP Completeness**- What it is (NP complete, NP hard, NP)
- Space between P and exponential
- Understand why SAT is NP complete (3-SAT, CNF)
- Short certificate (easy to verify)
- Understand what polynomial time reduction is (to show NP hardness)

## November 9, 2004

By this date, you should know all of the topics below. Note that all topics for this section except Godel's Incompleteness were covered on WrittenAssignment4.

**Propositional Logic**- Luger handout

**Predicate Logic**- Luger handout

- Basic proof-writing
**Prolog notation**Handouts: Louden, Tucker & Noonan

**Godel's Incompleteness Thm**

## After October 12, 2004

By this date, you should be familiar with all the concepts below.

**Pushdown Automata**- (this should be populated with subtopics)

**Context Free Grammars**- Parse tree
- Bacchus-Naur Form
- The difference between terminal and non-terminal symbols
- Some ways to resolve ambiguous grammars
- relationship between grammars and interpreters
*Resources:*- Your Theory Book
See details in ReadingRoom/Grammars

## October 1, 2004

By this date, you should be familiar with all the concepts below. They will be covered on the first exam. [NB: WrittenAssignment2 covers this material *except* the second FSM class (Regular expressions, pumping lemma...)]

**Finite state machines**- Produce a deterministic or nondeterministic FSM in circle-and-arrow or transition table representations
- Run a deterministic or nondeterministic FSM on a given input
- Understand how a DFSM can simulate an NFSM
- Regular expressions, RE/FSM relationship, Pumping lemma
*Resources:*- Your Theory Textbook
- the Discrete Math textbook (Rosen) ch 11
See details at ReadingRoom/FiniteStateMachines

**Bound-beating**- Hashing
- Bin-sort
- Order statistics
*Resources:*- Your Algorithms Textbook
- Cormen 2e: chapters 8, 9, 11

## September 20, 2004

By this date, you should be familiar with all the concepts below.

**Lisp/scheme**- Be able to write scheme procedures including recursive procedures
SICP 1.1 through 1.1.6 or Dybvig chapter 2 (except 2.8)

- Be able to identify tail recursive property; understand relationship to stack
SICP 1.2 especially 1.2.1, 1.2.3

- Be able to write higher order procedures
- Be able to build data structures and ADTs in scheme
SICP Chapter 2 through section 2.3, especially 2.1.1 - 2.1.2, 2.2.1 - 2.2.3, 2.3.1; or Dybvig

*Resources:*SICP Chapters 1 and 2 (see links, ResourcesForScheme or hard copy in CCL library)

Dybvig: especially chapter 2 except 2.8. (see links, ResourcesForScheme or hard copy in CCL library)

- Be able to write scheme procedures including recursive procedures
**ADTs**aka Abstract Data Types- Be able to write/use/analyze list, array, collection, stack, queue, and tree
*Resources:*- Your Algorithms Textbook
- Cormen 2e: chapter 10 ADTs; chapter 12 trees (see CCL library or Olin Library)
LOTS of web info. (Start a collection in our ReadingRoom, please!) --

*now at ReadingRoom/AbstractDataTypes*- See also resources on Collections, Stacks, Queues, Lists, Arrays

**Orders of growth**Be able to analyze straightforward algorithms and group by asymptotic order of growth (1, log n, n,n log n, n

^{2}, 2^{n})*Resources:*- Your Theory Textbook
- Your Algorithms Textbook

**Sorts**- Know (algorithms and analysis and whether analysis is worst/average/best) bubble, insertion, selection, heap, merge sorts
- quicksort (know algorithm, analysis, worst/average/best)
- Know information theoretic lower bound and why
*Resources:*- Your Algorithms Textbook
- Handout from Lewis and Denenberg: insertion, shell, selection, heap, and merge sorts
- Cormen 2e: chapter 3 analysis; ch 2 sorts; chs 6, 7 more sorts (see CCL or Olin library)
Lots of web resources (Start a collection in our ReadingRoom, please!) --

*maybe at ReadingRoom/SortingAlgorithms ?*Also see AlgorithmAnimations

**Trees**- Know list, structure, array representations; be able to deduce code
- Know pre/in/post order traversal, be able to write code
- Know log n depth, be able to make inductive argument
*Resources:*- Your Algorithms Textbook
- Cormen 2e: chapter 12 (see CCL or Olin library)
Lots of web resources (Start a collection in our ReadingRoom, please!)

**Enrichment/Optional/Just Cool**- We are not covering Cormen Ch4 -- recurrences -- but a serious algorithms student may want to learn this material for her own edification.