CS301: Foundations of Computer Science (Fall, 97) Computer Science Department, Colorado State University ------------------------------------------------------------------------ Contents * What's New? * Course Description * Time and Place * Instructor and Graduate Teaching Assistant * Text Book * Prerequisites * Grading * Schedule * Assignment and Test Information * Resources What's New? * Here is the final grades for the semester. Happy Holidays!! * Review session for the final will be held Monday evening, Dec. 15th, from 7pm to 9pm in the third floor, south, of USC. * Your graded Quiz 3 is available outside Chuck's office. I will also bring them and the answer sheet to class. * Turing Machines in java are linked to in the Resources section. * Please use e-mail or the phone to make appointments with Chuck. In CS301 class this week, all CS undergrads will be receiving a notice about setting up a required meeting with a faculty member for advising. If you didn't receive one, send e-mail to Chuck. Course Description In this class you will learn how to study computation, not in terms of semiconductors and integrated circuits, but in terms of abstract models of computation. The investigation of what these models of computation can and cannot do leads us to a theoretical understanding of the fundamentals of computation. The tools we will use include formal languages, finite state automata, pushdown automata, turing machines, and methods for measuring the complexity of algorithms. Time and Place * Time: Tuesdays and Thursdays, 9:30 - 10:45 PM * Place: SHEP 118 * Recitations: o Section 1: SHEP 120, Tuesdays, 4:10 - 5:00 PM o Section 2: WAGAR 132, Wednesdays, 4:10 - 5:00 PM Instructor and Graduate Teaching Assistant * Instructor: Chuck Anderson, anderson@cs.colostate.edu o Phone: 970-491-7491. FAX: 970-491-2466 o Office Hours: 225 USC, by appointment * Graduate Teaching Assistant: Sivakumar Venkatesan, sivakuma@cs.colostate.edu o Office: USC 3rd Floor South, Phone: 970-491-1140 o Office Hours: North Lab, 3rd Floor, USC, Tuesday, Wednesday, 7:00--9:00 pm Text Book * Text: John C. Martin, Introduction to Languages and the Theory of Computation, published by McGraw-Hill, 1997, second edition. Prerequisites To register for CS301, you must have taken CS200, CS201/M201, and M229. Grading Your grade will be based on homework, quizzes, and a final exam, weighted as follows: * 50% for homework assignments, * 30% for three Quizzes, each worth 10%, * 20% for Final Exam. Schedule * Aug. 26 - Sept. 9: Chapters 1 and 2. Mathematical review. * Sept. 11, 16: Chapter 3. * Sept. 18, 23: Chapter 4. * Sept. 25, 30: Chapter 5. * Oct. 2: Quiz 1 * Oct. 7, 9: Chapter 5. * Oct. 14, 16, 21, 23: Chapter 6. * Oct. 28: Review for Quiz 2 * Oct. 30: Quiz 2 * Nov. 4, Chapter 7. * Nov. 6, 11: Chapter 8. * Nov. 13, 18: Chapter 9. * Nov. 20: Chapter 10. * Nov. 24: Thanksgiving Break. * Dec. 2: Chapter 10. * Dec. 4: Quiz 3. * Dec. 9, 11: Chapter 12. * Dec. 16, 9:10 - 11:10 AM: Final Exam. Assignment and Test Information Be sure you read the Computer Science Department's Student Information Sheet. It explains the department's policies regarding late assignments and other important things. List of Assignments: * Assignment 1, due Sept. 9, 10:30 am * Assignment 2, due Sept. 18, 10:30 am * Assignment 3, due Sept. 25, 10:30 am. Points distribution for assignment #3 . * Assignment 4, due Oct. 9, 10:30 am. Points distribution for assignment #4 * Assignment 5, due Oct. 23, 10:30 am Points distribution for assignment #5 * Assignment 6, due Oct. 28, 10:30 am Points distribution for assignment #6 * Assignment 7, due Nov. 20, 10:30 am POints distribution for assignement #7 Resources You may post questions and discussions on the csu.cs.301 newsgroup. Here are some links to web pages with material relevant to CS301: * Susan Rodger at Duke University provides some fun, interactive tools in Java to build and simulate automata, Turing Machines, and other things. The main page is here. You can run a local version that allows you to save your automata you build. To run it, type ~cs301/jflap/run . Once it starts, read how to use it by clicking on "Help" in the menu bar. * Help on proof techniques * Alan Turing Internet Scrapbook, including a Turing Machine simulation in Java. * Turing Machines as Java Applets o Skinner o Brown , or sunsite, with sound o Java source code for a Turing Machine, by Suzanne Skinner o Another Java applet from Germany o A cool one from U.MIch. You can find the TM code by removing Turing.html from the path and browsing the directory. ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ ------------------------------------------------------------------------ CS301, Assignment 1: Chapters 1 and 2 Due September 9th, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 1 * 1.1: c, d, e * 1.3: e, g, using Venn diagrams and set identities * 1.6: f, g, h * 1.10: b. * 1.11: b, d * 1.14. Use truth tables. * 1.16. Hint: If there are two, they must be equal. * 1.17. * 1.18: c, d, e * 1.23: a, b * 1.27: a, b, c * 1.33: b, d * 1.34 * 1.42 * 1.43 * 1.49 * 1.50: a * 1.52 Chapter 2 * 2.4 * 2.5 * 2.7 * 2.13 * 2.14 * 2.19 ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 2: Chapters 2 and 3 Due September 18th, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 2 * 2.28 * 2.31 * 2.33 * 2.36 * 2.41 c, e, g * 2.42 c, d * 2.48 Chapter 3 * 3.1 c, d * 3.2 b, c, d * 3.5 * 3.6 d, e * 3.7 b ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 3: Chapters 3 and 4 Due September 25th, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 3 * 3.23 d, e * 3.31 * 3.32 * 3.33 * 3.38 * 3.41 a, b, c Chapter 4 * 4.1 a, b * 4.3 * 4.8 a, b * 4.11 a, b, c * 4.12 * 4.15 ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 4: Chapter 5 Due October 9, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 5 * 5.24 e,f * 5.25 b * 5.27 c, d * 5.30 b ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 5: Chapter 6 Due October 23, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 6 * 6.2 * 6.22 * 6.27a * 6.35a * 6.36b * 6.43b And, for extra credit, you may turn in 6.43d. ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 6: Chapter 7 Due October 28, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 7 * 7.13 a * 7.35 b * 7.36 b * 7.38 a,b * 7.40 ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu ------------------------------------------------------------------------ CS301, Assignment 7: Chapter 9 Due November 20, 10:30 AM Complete the following exercises from the textbook. Show all of your work. If not sure of the answer, make some guesses. Partial answers will be given partial credit. Chapter 9 * 9.1 * 9.2 * 9.4: a, c, d, e * 9.5 * 9.7 * 9.13 * 9.15: a, b * 9.20 ------------------------------------------------------------------------ Copyright © 1997 Chuck Anderson, anderson@cs.colostate.edu