ProjectThe project is an opportunity to do a more in-depth examination of a topic. There is a wide choice of topics. Projects may or may not include a computer program; it is strongly suggested that those who are majoring in CS choose a topic that includes programming. Each project should include a bibliography and a written section. Projects that do not include programming will consist of a paper (at least 5 pages) that explains the topic; worked examples may be included. Project topics should be unique, so see me for clearance of the topic. Depending on the choice of topic, the project is due when the corresponding take-home exam is due and takes the place of the take-home part. Topic and format should be discussed ahead of time. The grading rubric is below. Some possible topics are listed below. Others are certainly possible. Most of the topics that we go over could become project topics if there is more depth. Sections from the text that we do not cover are also possibilities. Chapters 1-3 (due Oct 5): history topics such as Boole, Russell (and his paradox) and set theory, foundations of set theory, Godel, continuum hypothesis; Cantor and power sets; logic circuits; logic puzzles and information about Charles Dodgson; fuzzy logic; George Polya and proof strategies; theorem proving by computers. Chapters 4-7 (due Nov 18): prime numbers; Goldbach conjecture; more on RSA public key encryption; ISBN numbers, zip codes, and credit card numbers; Fibonacci numbers; Mersenne primes; computers and prime numbers: generating and testing; different base systems used by different peoples; Ackermann's functions and uses of Stirling numbers; recursive drawings in computer science; relational databases; further topics in relations such as total and partial orders; cardinality of sets; complexity of algorithms; fractals and chaos theory; solving one version of the Josephus problem using binary numbers; algorithms and complexity (sorting, searching, etc.); pseudo random numbers. Chapters 8, 12, 13 (due Dec 14): generating permutations and combinations; adjacency matrices and other representations for graphs; computer representationof graphs; Prim and Kruskal algorithms; additional combinatorial identites and formulas; binary trees; graph coloring; four-color problem; one-line drawings; Huffman coding; network flow problems; Dijkstra's shortest path algorithm; game trees andAVL trees; applications of graph theory to ecosystems or to sociology and psychology; de Bruijn sequences; Chinese mailperson problem; tree traversals; chess-playing programs.
Grading rubric (10 points total): Content – 6 points
|