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, n2, 2n)
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.