COSC261-13S1 (C) Semester One 2013

Foundations of Computer Science

15 points

Details:
Start Date: Monday, 18 February 2013
End Date: Sunday, 23 June 2013
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 3 March 2013
  • Without academic penalty (including no fee refund): Sunday, 19 May 2013

Description

This course deals with fundamental concepts and techniques in Computer Science. The first part includes probabilistic methods of Computer Science. The second part deals with automata theory. The third part consists of graph theory and compilers.

This course deals with fundamental concepts and techniques in computer science. They are used in many different areas of computer science, including algorithms, artificial intelligence, cryptography, language design, parsing, pattern matching, performance evaluation and optimisation.

The course covers:
* Probabilistic methods - from set theory and combinatorics to probabilities, random events and random variables, pseudo-random numbers, statistical analysis of experimental data
* Automata theory - finite automata, regular expressions, formal languages, context-free grammars, pushdown automata, Turing machines, computability, complexity
* Compilers - lexical analysis, syntax analysis, code generation

Prerequisites

(1) COSC121; (2) COSC122; (3) 15 points from Mathematics, Statistics, Engineering Mathematics or MSCI110. MATH101 is not acceptable. MATH120/STAT101 are strongly recommended.

Restrictions

COSC202, COSC222

Course Coordinator

For further information see Computer Science and Software Engineering Head of Department

Assessment

Assessment Due Date Percentage 
Assignment One 15%
Assignment Two 25%
Exam 60%

Textbooks / Resources

No textbooks are required, but see the following books for additional information:
• Michael Baron; Probability and Statistics for Computer Scientists; Chapman and Hall/CRC, 2006
• William Stewart; Probability, Markov Chains, Queues, and Simulation; Princeton University Press, 2009
• Seymour Lipschutz and Marc Lipson; Schaum's Outline of Discrete Mathematics; third edition, McGraw-Hill, 2007
• Carol Critchlow and David Eck; Foundations of Computation; version 2.3.1, 2011
• Michael Sipser; Introduction to the Theory of Computation; second edition, Course Technology, 2005
• Em Kinber and Carl Smith; Theory of Computing: A Gentle Introduction; Prentice Hall, 2001
• Niklaus Wirth; Algorithms + Data Structures = Programs; Prentice-Hall, 1975

More advanced or comprehensive books are:
• John Hopcroft, Rajeev Motwani and Jerey Ullman; Introduction to Automata Theory, Languages and Computation; Pearson, 2006
• Dexter Kozen; Automata and Computability; Springer, 1997
• Reinhard Wilhelm and Dieter Maurer; Compiler Design; Addison-Wesley, 1995
• Niklaus Wirth; Compiler Construction; Addison-Wesley, 1996
• Alfred Aho, Monica Lam, Ravi Sethi and Jeffrey Ullman; Compilers: Principles, Techniques, and Tools; second edition, Pearson, 2007

Indicative Fees

Domestic fee $719.00

International fee $3,325.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Computer Science and Software Engineering .

All COSC261 Occurrences

  • COSC261-13S1 (C) Semester One 2013
Previous year Next year