Spring 2025 Courses
5800 /Theory Foundations:
Instructor
Dr. Elise de Doncker
B-240 CEAS
Phone: (269) 276-3102 (Office), 276-3101 (Dept. office), 276-3122 (fax)
(but preferably contact me by e-mail:) elise [dot] dedoncker [at] wmich [dot] edu
Office hours
MW 13:30 - 14:30
Please let me know if you plan on coming; other times by appointment.
Prerequisites
CS 3310
Catalog Description
The course gives an introduction to the theory of computation emphasizing automata, grammars and their applications in the specification of languages and computer systems, models of computation, and complexity. Analytic and problem solving abilities will be reinforced, and concepts covered in the course will be applied to real-world problems.
Texts
Required:
Languages and Machines, Thomas A. Sudkamp, 3rd edition, Addison Wesley (ISBN: 0-321-32221-5)
Recommended:
Introduction to Automata Theory, Languages and Computation, John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, 2nd edition, Addison Wesley (ISBN: 0-201-44124-1)
Automata, Computability, and Complexity: Theory and Applications, Elaine A. Rich, Pearson Prentice Hall (ISBN: 0-13-228806-0; ISBN: 978-0-13-228806-4)
Grading:
There will be two tests and a final examination. Tentatively, the tests will carry about 45% of the grade, the lowest of the two tests will be dropped.
Other graded work will include assignments, a project and presentation. Problems with cheating or class attendance may lead to a failing grade.
The following scale will be used to determine your final grade on the basis of your final average:
A: 92.0 - 100.0, BA: 88.0 - 91.9, B: 82.0 - 87.9, CB: 78.0 - 81.9, C: 72.0 - 77.9, DC: 68.0 - 71.9, D: 60.0 - 67.9, E: below 60.0.
Grader: Edwin Jose, edwin.jose@wmich.edu
Academic Integrity Policies
You are responsible for making yourself aware of and understanding the policies and procedures in the Undergraduate Catalog that pertain to Academic Integrity. These policies include cheating, fabrication, falsification and forgery, multiple submission, plagiarism, complicity and computer misuse. If there is reason to believe you have been involved in academic dishonesty, you will be referred to the Office of Student Judicial Affairs. You will be given the opportunity to review the charge(s). If you believe you are not responsible, you will have the opportunity for a hearing. You should consult with me if you are uncertain about an issue of academic honesty prior to the submission of an assignment or test.
Additional instructor's notes: The above policy on academic dishonesty includes cheating by submitting tests, programming assignments or projects where the work (even in part) has been downloaded from the internet; this also applies to text in assignments and project reports. Collaboration among students on submitted work is not allowed. If you are caught there will be consequences.
Useful links
https://wmich.edu/step/successcenter Tutoring help for prerequisite classes
http://www.stanford.edu/~ullman/ialc.html Homepage of the book by Hopcroft, Motwani and Ullman
http://www.cs.utexas.edu/~ear/cs341/automatabook/ Homepage of the book by Elaine Rich
https://cs-wmu.slack.com slack team cs-wmu
Syllabus:
Topics/modules with Bloom classifications are listed below:
K = Know the terminology
C = Comprehend so as to paraphrase/illustrate
A = Apply it in some way, in homework assignments or projects
N = Elective
Review of discrete mathematics and proof methods (A), cardinality/countability (C)
Formal languages, the Chomsky hierarchy: languages, their grammars, and automata (regular (A), CFL (A), CSL (K), recursive enumerable (C)), their grammars, and automata (D/NFA (A), PDA (A), LBA (K), TM (A)), stochastic automata (Markov models (N))
Undecidability: Church-Turing thesis (C); some undecidable problems (C), reductions (K), relation to recursive enumerable (r.e.) languages (C), recursive languages (C), Turing machines (C)
Intractable problems, complexity: Non-deterministic time and space complexity (C), Polynomial time and space, classes P and NP (C), some NP-Complete problems (K)
Applications to compiling: lexical analysis (C), parsing (C), (LL(k), LR(k) (N)), ambiguity (C)
Models of computation: lambda-calculus (N) (in relation to functional languages), (partial-) recursive functions (C), Markov algorithms (N) (in relation to logic programming languages), cellular automata (N)
Learning outcomes
A. General learning outcomes:
Reinforce analytic development and problem solving abilities, and develop a foundation in computer science.
Show progress with regard to understanding the theory of computation (for use, e.g., in further graduate level courses), including knowledge and use of terminology and how the theory connects with real-world applications, possibly in different and new areas.
Apply the concepts covered in the course to written and practical problems, e.g., by combining problem solving with computer programming and the use of software tools as part of assignments and a semester project. The latter may be done in teams or individually.
B. Content specific outcomes:
(for students who earn a grade of B or better):
The students will demonstrate an introductory to intermediate-level knowledge of definitions and theorems for problem solving relating to automata, grammars and formal languages.
Students will demonstrate the ability to apply proof techniques and other mathematical concepts, as well as algorithms to questions concerning automata, grammars and languages.
The students will demonstrate knowledge of the theory of computability/ decidability.
Students will demonstrate the ability to synthesize knowledge and use tools of automata, grammars and computational models to solve problems relating to language specification and machine computation.
References:
Introduction to Automata Theory, Languages, and Computation
J. E. Hopcroft, (R. Motwani) and J. D. Ullman, Addison Wesley
Fundamentals of the Theory of Computation - Principles and Practice
Raymond H. James and Greenlaw Hoover, Morgan Kaufmann
Models of Computation - Exploring the power of computing
John E. Savage, Addison Wesley
The Theory of Computation
Bernard M. Moret, Addison Wesley
An Introduction to Formal Languages and Automata
Peter Linz, D. C. Heath and Co.
The Theory of Computability - Programs, Machines, Effectiveness and Feasibility
R. Sommerhalder and S. C. Van Westrhenen, Addison Wesley
Theory of Computation
W. S. Brainerd and L. H. Landweber, Wiley
Machines, Languages and Computation
P. J. Denning, J. B. Dennis and J. E. Qualitz, Prentice-Hall
Languages and Machines, An Introduction to the Theory of Computer Science
Thomas A. Sudkamp, Addison Wesley
Projects:
Implement and anlyze an algorithm or compare different algorithms for the same problem. You need to program the algorithm(s). You may add a user interface or graphical display. Notes:
- Up to 2 students will be allowed per project team.
- Relative scores for the parts of the project deliverables will be as follows: Proposal: 10 pts.; Prelim. design: 15 points; Design: 20 pts.; Testing design: 10 pts.; Final report and presentation: 45 pts.
- Read in your test data from a file.
Semester project ideas
Implement a regular expression parser: Take as input the regular expression; convert regular expression to NFA.
Implement a simulator for a vending machine, elevator, traffic light control.
Implement a yacc/bison description of a parser for a language.
For example, use bison (yacc) to generate a parser (syntax checker) for a subset of the BNF representation of Java (listed, e.g., in Appendix IV of the text book by Sudkamp). Your subset should include specifications of: while, if and if else statements. For the expressions, use arithmetic expressions and operators.
Write example Java code (4 conforming examples) to show the capabilities of your parser for checking the constructs you implemented. Add (2) examples where an error is detected.
Submit a typescript or log showing your bison (yacc) input code, generation of your parser source code, its compilation and linking into your parser executable, (6) examples with Java code as inputs, running through the parser, and output.
Add a report with a description of your work, including your selection of examples, and a general discussion of accomplishments and of difficulties encountered.
Also see the construction of the High Order Calculator (hoc) using Lex and Yacc in the book by Kernighan, Brian W. and Pike, Rob (1984), "The Unix Programming Environment", Prentice Hall (ISBN 0-13-937681-X).
Example of a parser generator project: "Generate and implement a bison (yacc) grammar which incorporates a part of XML, that includes the syntax for the given example. Your grammar should adhere to XML as given at the url http://www.w3schools.com/xml. You can check the syntax of your XML code using the XML validator at http://www.w3schools.com/xml. Generate a lexical analyzer which inputs XML code and recognizes your terminals (tokens). You may use flex (lex). Generate and run your parser. Extend your parser to handle more features of the example.
Implement a conversion of a general context-free grammar to Chomsky Normal Form or Greibach Normal Form
Implement the CYK algorithm to decide membership in the language of a given a context-free grammar.
Implement a Pushdown automaton (PDA) simulator: for PDA (transitions) and a string given on input. Apply to various examples. Supply a suitable user interface.
Implement a Turing machine simulator: for a Turing machine transition table and a string given on input. Apply to various examples. Supply a suitable user interface.
CS 6260/5950 :
Advanved Parallel Computations:
Instructor
Dr. Elise de Doncker
Department of Computer Science
College of Engineering and Applied Sciences
B-240 Parkview Campus
Kalamazoo, MI-49008
Phone: (269) 276-3102 (office), 276-3101 (Dept. office) 276-3122 (fax)
(but preferably contact me by e-mail: elise [dot] dedoncker [at] wmich [dot] edu)
Office hours
MW 14:30 - 15:30
Please let me know if you plan on coming; other times by appointment.
Texts
Required:
An Introduction to Parallel Programming. Peter S. Pacheco, Morgan Kaufman Elsevier, Inc. (978-0-12-374260-5)
OR
An Introduction to Parallel Programming. Peter S. Pacheco and Matthew Malensek, 2022 Elsevier, Inc. (978-0-12-804605)
CUDA by Example - An Introduction to General-Purpose GPU Programming. Jason Sanders and Edward Kandrot, Addison-Wesley (ISBN: 978-0-13-138768-3)
Parallel Programming - Techniques and Applications. B. Wilkinson and M. Allen, Pearson Prentice Hall (ISBN: 0-13-140563-2)
Recommended:
Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox. Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger and Roman Dementiev (ISBN: 978-3030252090)
Programming Massively Parallel Processors: A Hands-on Approach 3rd Edition. David B. Kirk and Wen-mei W. Hwu (ISBN: 978-0128119860)
Parallel Programming in C with MPI and OpenMP. Micheal J. Quinn, McGraw-Hill (ISBN: 978-0071232654)
Parallel Programming for Multicore and Cluster Systems. Thomas Rauber and Gudula Rünger, Springer 2010 (ISBN: 978-3-642-04817-3)
Structured Parallel Programming: Patterns for Efficient Computation. Michael McCool, James Reinders and Arch Robison, ISBN: 978-0124159938
An Introduction to Parallel Programming. Peter S. Pacheco, Elsevier 2011 (ISBN: 978-0-12-374260-5)
Using MPI - Portable Parallel Programming with the Message-Passing Interface. W. Gropp, E. Lusk and A. Skjellum, The MIT Press
Introduction to Parallel Computing. A. Grama et al., Benjamin/Cummings Publishing Company
Introduction to High Performance Computing for Scientists and Engineers. Georg Hager and Gerhard Wellein, ISBN: 978-1439811924 (or eBook ISBN: 978-1439811931)
Introduction to Parallel Algorithms and Architectures: Arrays - Trees - Hypercubes. F. Thomson Leighton, Morgan Kaufmann Publishers
Catalog description
Advanced topics in parallel computations such as algorithms, complexity and parallel performance in the areas of graph algorithms, numerical algorithms, computer graphics, and aspects of parallel environments and languages. Students will be expected to read research papers and complete a semester project involving the use and implementation of parallel programming paradigms on current machines.
Learning outcomes
Students will give class presentations, showing their mastery of the topics studied and demonstrating their research work.
Students will be able to apply performance evaluation techniques to analyze/measure the efficiency and scalability of parallel algorithms.
Students will be able to use parallel environments (MPI, OpenMP), CUDA.
Students will understand the effects of parallel overhead on performance.
Students will be able to apply parallel strategies and paradigms to design parallel/distributed algorithms.
Students' progress and achievements towards reaching the course goals and objectives will be apparent from such measures as: the results and creativity displayed in course assignments; and the contents and delivery of their presentations.
Grading
There will be two tests and a final exam. Other graded work includes assignments, presentations and a semester project.
The following scale will be used to determine your final grade on the basis of your final average: A: 92.0 - 100.0, BA: 88.0 - 91.9, B: 82.0 - 87.9, CB: 78.0 - 81.9, C: 72.0 - 77.9, DC: 68.0 - 71.9, D: 60.0 - 67.9, E: below 60.0. Problems with attendance may lead to a failing grade.
Academic Integrity Policies
You are responsible for making yourself aware of and understanding the policies and procedures in the Undergraduate Catalog that pertain to Academic Integrity. These policies include cheating, fabrication, falsification and forgery, multiple submission, plagiarism, complicity and computer misuse. If there is reason to believe you have been involve in academic dishonesty, you will be referred to the Office of Student Judicial Affairs. You will be given the opportunity to review the charge(s). If you believe you are not responsible, you will have the opportunity for a hearing. You should consult with me if you are uncertain about an issue of academic honesty prior to the submission of an assignment or test.
Additional instructor's notes: The above policy on academic dishonesty includes cheating by submitting tests, assignments or projects where the work (even in part) has been downloaded from the internet; this also includes programs, as well as text in (written or programming) assignments and project reports. Cooperation among students on submitted work is not allowed. If you are caught there will be consequences.
Links
http://www.cs.wmich.edu/hpcs High Performance Computational Science Laboratory (HPCS), home of thor
https://www.amazon.com/Programming-Massively-Parallel-Processors-Hands-dp-0128119861/dp/0128119861/ref=dp_ob_image_bk Kirk and Hwu 3rd edition book and ebook at Amazon
https://smile.amazon.com/gp/product/0124159931?ref=em_1p_1_im&ref_=pe_27541010_564465120 McCools, Reinders and Robison book and ebook at Amazon
http://www.cs.usfca.edu/~peter/ipp/index.html Pacheco text book site, with link to source code archive
http://www.elsevierdirect.com/companion.jsp?ISBN=9780123742605 Pacheco book companion website, with link to source code archive, figures, etc.
https://www.amazon.com/CUDA-Example-Introduction-General-Purpose-Programming/dp/0131387685#reader_0131387685 NVIDIA site for the book "CUDA by Example" (where you can look in the book and buy it; and its source code is available for download)
http://www.netlib.org Top 500 supercomputers, software repository and more
http://www.netlib.org/utk/people/JackDongarra/talks.htm Jack Dongarra talks
http://www.psc.edu/media/training/OpenACC-GPU_Oct2012/IntroductionToOpenACC.pdf OpenACC
http://www.hpcwire.com/jobs Job lists in high performance computing. Subscribe to HPCwire!
http://technews.acm.org/archives.cfm Archive ACM Technews
http://www.linuxjournal.com Linux journal
http://www.linux-mag.com Linux magazine
http://www.globus.org Globus (grid computing)
http://www.geant.net/pages/home.aspx Géant network Europe
http://www.ibm.com/developerworks/web/library/wa-cloudgrid Article on Cloud versus Grid Computing
http://www.mcs.anl.gov/research/projects/mpi/ MPI homepage. Download and install MPICH2.
http://www.cs.wmich.edu/~elise/courses/cs626/presentations-s09.htm Presentations CS 6260 Spring 2009
kumar.pdf Paper on load balancing and scalability