Difference between revisions of "CS Courses Standard Content"

From Computer Science
Jump to: navigation, search
(52 intermediate revisions by one other user not shown)
Line 3: Line 3:
Note: as of summer 2018, this document contains information about all courses that are required in the CS or IT majors.  Other CS courses are not listed here yet.
Note: as of summer 2018, this document contains information about all courses that are required in the CS or IT majors.  Other CS courses are not listed here yet.
Points of contact for the standard information course.  <br>
=Points of Contact=
Steve Baker - CS 151, 469, 479  <br>
Steve Baker - CS 151, 469, 479  <br>
Laci Egri - CS 303, 420  <br>
Laci Egri - CS 303, 420  <br>
Line 12: Line 12:
Rob Sternfeld - CS 101, 201, 457  <br>
Rob Sternfeld - CS 101, 201, 457  <br>
Prerequisites <br>
CS 151 is prerequisite for - CS 170, 201, 260 <br>
CS 101 is prerequisite for - CS 151<br>
CS 151 is prerequisite for - CS 170, 201, 260, 303 <br>
CS 170 is prerequisite for - 479 <br>
CS 170 is prerequisite for - 479 <br>
CS 201 is prerequisite for - CS 202, 303, 469, 479 <br>
CS 201 is prerequisite for - CS 202, 469, 479 <br>
CS 202 is prerequisite for - all 400 level except 469, 479 <br>
CS 202 is prerequisite for - all 400 level except 469, 479 <br>
CS 303 is prerequisite for - CS 420, 421, 457, 458 <br>
CS 303 is prerequisite for - CS 420, 421, 457, 458 <br>
Line 22: Line 23:
Courses with no prerequisite - CS 151, 256 <br>
Courses with no prerequisite - CS 151, 256 <br>
= CS Courses Standard Content Pages =
Items to spin off as standalone videos / tutorials <br>
* [[CS 101 Fundamentals of Computing]]
Editors - vim, emacs, pico, atom.  Should be able to edit text files, save changes, make copies.<br>
* [[CS 151 Introduction to Computer Science]]
IDEs - eclipse, MS visual studio.  Should be able to create a project, add source files, compile and run, debug.<br>
* [[CS 170 Web Programming]]
Debugging - gdb.  Should be able to compile with debug information, use gdb to find where seg fault occurs, set breakpoints and look at variable values, step line by line through code.<br>
* [[CS 201 Computer Science I]]
Unix tools - grep, sed, awk, find, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection.<br>
* [[CS 202 Computer Science II]]
* [[CS 256 Structured Design]]
== Programming Assessment ==
* [[CS 260 Object Oriented Programming]]
===Catalog Description===
* [[CS 303 Discrete Structures]]
* [[CS 420 Theory of Computing]]
Basic C programming and data structures.  5 questions.  Must pass with 3 and 2 halves for - passing CS 499 and Cs 685/695/699, getting higher than a C in CS 500, getting a C or higher in CS 202.
* [[CS 421 Formal Methods]]
Most important prerequisite skills/knowledge: <br>
* [[CS 451 Architecture]] 
Most important skills/knowledge gained: <br>
* [[CS 452 Software Engineering]]
Normal Content<br>
* [[CS 456 Systems Programming]]
C programming, with one program from five different types… <br>
* [[CS 457 Data Base Processing]]
Simple program that requires a loop or nested loops.<br>
* [[CS 458 Algorithms]] ''(needs information)''
Program that scans through text a character at a time to do something.<br>
* [[CS 469 Unix/Linux Administration and Networking]]
Linked list traversal.<br>
* [[CS 470 Programming Languages]]
Binary tree traversal.<br>
* [[CS 471 Operating Systems]]
Bit operations.<br>
* [[CS 473 Networking]]
* [[CS 479 Web Programming II]]
===Important Assignments and/or Exam Questions===  
* [[CS 499 Senior Seminar]]
Standard resources (textbook or online)
== CS 101 Fundamentals of Computing ==
Catalog Description
The main focus of the course is to give students a practical understanding of computing to become well-informed citizens and professionals in the computing age.  Topics may include a basic study of - computational thinking, computer security, big data, artificial intelligence, and current trends in computing.
Most important prerequisite skills/knowledge: typing and basic computer use - web browser, email, etc.
Most important skills/knowledge gained: basic understanding of how computers work, basics of programming, how information is stored and transferred between computers, do’s and don’ts of security, basic understanding of concepts of computational complexity and artificial intelligence
Normal Content
Course Outline
We will spend 1-2 weeks on each of the following topics.
What is inside a computer: CPU, RAM, hard drive, etc.
Internet 101: how data is moved around the internet
Computer and internet security: how do you know your data is secure?
Servers and such: logging into a server, transferring files
Html basics: creating web pages, a little bit of javascript
Block programming: scratch.mit.edu, code.org, blocky
Computational problems: things computers can do really well, and things that are impossible for computers to solve
Artificial intelligence: different meanings of the term, examples
Learning Outcomes
The following are the most important learning outcomes for each of the 8 topics listed in the course outline.
What is inside a computer
Name the different components that make up a computer.
Describe what the terminology associated with a component means (e.g., Ghz for CPU’s is the speed of the CPU, GB for the size of a hard drive).
Evaluate the tradeoffs between different components (e.g., one CPU versus another)
Internet 101
Explain the basic infrastructure of the internet and associated terminology.
Explain the infrastructure of a home network, and be able to configure a home network.
Explain how web browsing and email works, in terms of which parties are involved (e.g., server and client), where data is stored, and what communication is involved.
Computer and internet security
Explain the concepts of encryption/decryption, digital signing, and the difference between public-key and private-key encryption.
For given situations, be able to say whether a given interaction is secure or not.
Know the key terminology of internet security (e.g., rsa, sha, https, etc.).
Servers and such
Explain what servers are used for
Be able to log in to a server to transfer files to a server, and login via ssh to issue commands to the server
How is data stored on a server, and how do we access data
Html basics
Explain the basic structure of an html document, and understand that an html document is a plain text file that has markup tags to say how to display different parts of the webpage.
Be able to create simple html webpages.
Be able to put webpages onto a web server.
Block programming
Understand the concept of a computer program as instructions for the computer.
Be able to design simple programs in a graphical programming environment (one where there is no possibility for syntax errors, e.g., scratch).
Computational problems
Explain some examples of computational problems, and understand how problems are framed (input to the problem, correct output, running time of finding the solution).
Basic skills in evaluating efficiency of an algorithm.
Explain some examples of computational problems that either cannot be solved, or require inordinate amount of time to solve (e.g., halting problem).
Artificial intelligence
Understand the concept of the “Turing test” as a test of artificial intelligence.
Know the history of some famous examples of “artificial intelligence” (e.g., chess playing, Jeopardy playing, chat-bots).
Explain some examples of artificial intelligence techniques (e.g., spam filtering, facial recognition, expert medical systems).
Important Assignments and/or Exam Questions
Standard resources (textbook or online)
The Beauty and Joy of Computing - course on CS Principles, including programming in SNAP
Computer Science Principles - a similar course by Amit Jain at Boise State with much of the content online
Introduction to Computing - a similar course by Nick Parlante at Stanford with much of the content online
HTML tutorial, CSS tutorial, More on CSS, Javascript tutorial
Introduction to Computing: Explorations in  Language, Logic, and Machines by David Evans
A Computer Science Tapestry by Owen Astrachan
Blown To Bits: Your Life, Liberty and Happiness After The Digital Explosion by Hal Abelson, Ken Leeden and Harry Lewis
== CS 151 Introduction to Computer Science ==
Catalog Description
History of computers and computer science, principles of process description, and problem analysis. The basic structures of sequence, iteration, and selection. Programming style, artificial intelligence, current applications.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Ability to use Unix at the command line.
Basic understanding of files and directories
Can take a specification and produce code implementing it.
JavaScript (ECMAScript) programming and debugging
Understanding of primitive data types and basic Boolean logic
Basic programming concepts such as scope, functions, conditionals and loops.
Simple algorithms for searching and sorting and simple mathematical concepts as they relate to programming such as numeric bases, summation and modulus arithmetic.
Normal Content
Using unix - getting around in the shell, dealing with files and text editors.
Making directories / folders, what are they?
Making and editing files, what are they?
Unix file permissions, ls -l output decoding
Wild-cards (at least * and ~)
List of required commands: passwd, chfn, man, ls, cp, mv, rm, mkdir, rmdir, chmod and some editor, ssh/scp/rsync?
Using the 151check program and auto-checking their assignments
Basic HTML elements: html/head/body, lists, tables, textual formatting
Basic CSS styling: selectors, box model properties, colors, fonts
Probably will deprecate this portion of the class or move to the end if doing ES in the browser examples.
Used as a lighter introduction to files and editing
ECMAScript programming:
Numbers: Integers/Floats, Bases, formatting, comparing, min-max
Strings: comparing, searching, more emphasis on what is a character?
Arrays (Some on objects), min-max element, searching/sorting
Common methods for the above data-types.
Using command line parameters
Console output, some formatted output
Variables and scope
if, if-else, if-else chaining
Simple Boolean logic: NOT, AND, OR, Boolean expressions
Functions and methods, method-chaining
while, do-while and for loops.
Nested loops
Iteration over arrays/objects with for-in / for-of
Dealing with some file-data (strings/characters or JSON encoded arrays)
Comparing and counting things
min-max of 2/3/4 elements, finding second largest/smallest
Searching: linear search then later binary search
Sorting: insertion and selection sort
Caesar cipher encryption?
Arrays as stacks/queues: push/pop, shift/unshift operations
Bases - converting to/from binary and decimal, Hexadecimal and Octal
Modulus arithmetic
Some functions: min/max, floor/ceil, abs, pi, sin, cos
Important Assignments and/or Exam Questions
Using Unix - copying, creating files and directories, using a text editor.
Hello world - creating a basic program and getting it to run.
Unit conversion - converting between degrees/radians, etc.
Looping and iteration over some datum - summation, min-max finding
2 dimensional data and nested looping - making a multiplication chart
Data validation - ask for phone number and check that what they typed is valid. Also for other types of data (e.g., email address, age, …). (students have great difficulty with this type of problem.)
Caesar cipher encryption/decryption (playfair setup, but not called that)
Interactive programs?
Auto-testing has difficulty with anything random.
Standard resources (textbook or online)
Mozilla Developer Network (MDN)
Tutorials Point
== CS 170 Web Programming ==
Catalog Description
An introduction to World Wide Web programming methods and scripting languages. Includes Hypertext Markup Language (HTML), Cascading Style Sheets (CSS), Dynamic Hypertext Markup Language (DHTML), JavaScript, and VBScript.  Prerequisite - C or better in CS 151.
Most important prerequisite skills/knowledge:
Basic understanding of at least one programming language’s syntax and primary data structures.
Variables, primitives, and literals
Most important skills/knowledge gained:
Client-server relationship and front-end back-end architecture
Editors, multi-file projects, code linters, and workflow
The JavaScript event loop and asynchrony
The JavaScript prototype and the `this` keyword
EcmaScript latest additions
Regular expressions
Intro to PHP: Hypertext Preprocessor
Separation of concerns and ideal abstraction
Build tools and test suites
Simple back-end in NodeJS
Normal Content
Using Unix (refresher)
Client Server relationships
Understanding Apache as a System Service
Front-end Back-end Architecture
HTML and CSS (refresher)
Document Object Model (DOM tree)
Code Editors, Linters, and Workflow
JavaScript Event Loop and Asynchrony
setTimeout() and setInterval()
Latest EcmaScript Additions:
Arrow Functions
Rest and Spread operators
.forEach() and .map()
Binary, octal, hex literals
Template sting and interpolation
The JavaScript Prototype
Objects, prototypes, and new
The “this” keyword
Regular Expre ssions
ES6 classes
Abstraction techniques and code reuse
Building web components
Intro to PHP (Hypertext Preprocessor)
Build Tools - webpack, gulp (time permitting)
Testing tools - jasmine, mocha, jest, ava (time permitting)
Common frameworks (time permitting)
Important Assignments and/or Exam Questions
Standard resources (textbook or online)
(optional) JavaScript: The Good Parts by Douglas Crockford
(optional) JavaScript Patterns by Stoyan Stefanov
Mozilla Developer Network (MDN)
== CS 201 Computer Science I ==
Catalog Description
This course begins with a history of programming languages, then focuses on programming in a particular language. The following topics are covered in some detail: variables, expressions and operators, control structures, simple data types, arrays, classes, and objects. Algorithm design and security issues are also discussed.  Prerequisite - C or better in CS 151.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
Data formats and number systems (binary, decimal, octal, hex), signed/unsigned, two’s complement, floating point, long, int, short char, C strings
C Programming - all keywords and operations
C compiler, command-line arguments
C library functions - formatted I/O, C strings,
I/O with different data formats and number systems
Basic data structures - unsorted array, sorted array, linked list, heap, stack, queue, binary search tree.  Can do all on paper, do code for some in class and as assignments.
Important Assignments and/or Exam Questions
Standard resources (textbook or online)
Taking CS 201 and CS 202 Simultaneously
If a student requests taking CS 201 and 202 simultaneously to stay on track to graduate on time, the following must be met.
At least an A- in CS 151
Number systems (binary, octal, decimal, hex)
Firm understanding of programming fundamentals - variables / data types, arrays, control flow, loops, scope, string manipulation, pointers. 
Ability to write basic programs in C or python - anything that can be done with a few nested control structures (loops, if’s).
Review all of tutorialspoint - data structures & algorithms
Good understand of the following data structures - unsorted array, sorted array, linked list, stack, queue, hash table, binary search tree.  For each can do the following - explain the operations (insert, delete, lookup), run examples on the board, explain the running time of the basic operations
Programming assessment - problems 1, 2, 5 correct, get problems 3 and 4 correct possibly with assistance
Taking CS 201 and 303 Simultaneously
To take CS 303 simultaneously, you must
At least a B in CS 151
Meet items b), e), f) from the above list
CS 202 Computer Science II
Catalog Description
This course is a continuation of CS 201. It involves a deeper study of programming languages, but emphasizes programming in a particular language. Topics include algorithm design and analysis, data structures, recursion, threads, network programming, graphics, security, and ethics.  Prerequisites - C or better in CS 201.
Most important prerequisite skills/knowledge: basic programming concepts, ability to use unix
Most important skills/knowledge gained: C programming and debugging, data structures understanding (can explain lookup/insert/delete for each DS, work small examples on paper, know running times) and coding (can finish partially complete DS code, write new functions to traverse DS)
Normal Content
Review (2 weeks)
C Programming - all keywords and operations, libraries and header files
Data formats and number systems (binary, decimal, octal, hex), signed/unsigned, two’s complement, floating point, long, int, short char, C strings
I/O with different data formats and number systems
Basic data structures - unsorted array, sorted array, linked list, heap, stack, queue - code for all in class and as assignments
Search and sorting - linear and binary search, selection and insertion sort, mergesort, heapsort, quicksort - code for all in class and as assignments
Asymptotic analysis and running time (1 week) - big O/Omega/Theta, little o/omega, definitions, basic proofs, polynomials / exponentials / logarithms, recursion trees
Memory organization (1 week) - text, data, heap, stack, malloc, free, pointer arithmetic
Unix and debugging (1 week) - gdb, grep, sed, awk, find, compiler options, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection
Disk organization (1 week) - inodes, superblocks, etc.
New data structures (4 weeks) - binary search tree (including balanced), hash table, skip list, trie, B tree - code for some in class and as assignments
Graphs (1 week) - terminology, adjacency matrix, adjacency list, basic algorithms (BFS, DFS, shortest path, minimum spanning tree) - do all algorithms on the board, code for some in class, running time for all
Classes and objects in C++ (2 weeks) - data abstraction and encapsulation, defining classes, creating objects, inheritance, protection, virtual functions and polymorphism
The Standard Template Library (1 week)
Comparison of C++ and other OO Languages (Java, Python, etc.) (1 week)
Important Assignments and/or Exam Questions
Programming assessment - must pass with 3 and 2 halves to get a C or better
Data structures programming, exam/homework question - given prototype for insert/lookup/delete, can give correct code
Data structures programming, exam/homework question - given prototype for function that should use data structure functions, can give correct code
C programming play computer, exam question - given any short C program (a few dozen lines, say) and sample input, can trace execution and final output
Some large project that is interesting - game, etc.
Standard resources (textbook or online)
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
The C Programming Language by Kernighan and Ritchie
Online courses/tutorials - MIT course - Practical Programming in C , How to Think Like a Computer Scientist, C++ Version - an online textbook, CS 50: Intro to CS I at Harvard - has videos, lecture notes, Reference on C and C++, The C Programming Language, C Programming Tutorial, Fresh2fresh C Tutorial
== CS 256 Structured Design ==
Catalog Description
An introduction to structured programming and top-down design; applications to a wide variety of practical programming problems.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
Important Assignments and/or Exam Questions
Standard resources (textbook or online)
== CS 260 Object Oriented Programming ==
Catalog Description
Object oriented programming concepts and methods. Includes encapsulation, data abstraction, class development, instantiation, constructors, destructors, inheritance, overloading, polymorphism, libraries, and packages.  Prerequisite - C or better in CS 151.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
Important Assignments and/or Exam Questions
Standard resources (textbook or online)
== CS 303 Discrete Structures ==
Catalog Description
This course is an introduction to discrete mathematics for computer science. The course covers the basic topics from set theory (including functions and relations), logic, number theory, counting, graph theory, and discrete probability. It involves a detailed study of proof techniques.  Prerequisite - C or better in CS 201.
Most important prerequisite skills/knowledge: Willingness to work hard.
Most important skills/knowledge gained: Capable of constructing rigorous mathematical proofs using direct proof, proof by contradiction, induction, etc.
Normal Content
Logic: proof tables, existential quantification, universal quantification, proposition, propositional function, De Morgan’s law (R. Ch. 1 - “R.” refers to the Rosen book, see below.)
Basic set theory: sets, intersection, union, complement, Venn diagram, inclusion-exclusion principle (R. Ch. 2)
Proof techniques: direct proof, contrapositive proof, proof by contradiction, weak induction, strong induction (P. Part 2 and R. Ch. 5 - “P.” stands for the “Book of Proof”, see below.)
Counting: permutations, combinations, binomial theorem, identities (e.g. {Pascal’s identity) pigeonhole principle and applications, double counting (R. Ch. 6)
Discrete probability: sample space, events experiments, outcomes, distributions, conditional probability, random variables, independence, expectation, linearity of expectation (R. Ch. 7)
Optional topics: Monty Hall problem, 100 prisoners problem, probabilistic method to prove lower bound on Ramsey numbers
Number theory: modular arithmetic division algorithm, modular exponentiation, primes, sieve or Eratosthenes, gcd, lcm, Euclidean algorithm, Bezout’s theorem, inverses, fundamental theorem of arithmetic, solving linear congruences, affine cipher, RSA (R. Ch. 4)
Graph theory: basic graph terminology, undirected graphs, bipartite graphs, degree of a vertex, handshaking theorem, matchings, Hall’s marriage theorem (optional) (R. Ch. 10)
Sample Exam Questions
What is the decryption function for an affine cipher if the encryption function is c = (15p + 13) mod 26?
Show that if 7 integers are selected from {1,2,3, ..., 12}, then there must be a pair of these integers with a sum equal to 13. What if only 6 integers are selected rather than 7? Can you still conclude that there must be a pair of these integers with a sum equal to 13?
A k-regular graph G is one such that deg(v) = k for all v ∈ G. Prove that if G is a k-regular bipartite graph with k > 0 and the bipartition of G is A and B, then |A| = |B|.
What is the probability of these events when we randomly select a permutation of 1,2,3,4?
1 precedes 4
4 precedes 1
4 precedes 1 and 4 precedes 2
4 precedes 1, 4 precedes 2, and 4 precedes 3
4 precedes 3 and 2 precedes 1.
Let Xn be the random variable that equals the number of tails minus the number of heads when n fair coins are flipped. Compute the expected value of Xn. (Hint: Define a set of a random variables and express Xn in terms of these random variables. Then use linearity of expectation. Explain clearly everything you do.)
Prove by induction that for any positive integer n, the inequality (1 + x)n ≥ 1 + nx holds for all x ∈ R with x > −1.
Suppose that the domain of the propositional function P(x) consists of the integers −1, 0, and 1. Write out each of these propositions using disjunctions, conjunctions, and negations: (a) ∃xP(x), (b) ∃x¬P(x), (c) ¬∃xP(x), (d) ¬∀xP(x).
Standard resources (textbook or online)
“Discrete mathematics and its applications”, 7th edition, by Kenneth Rosen. ISBN: 978-0073383095 (R.)
https://www.people.vcu.edu/~rhammack/BookOfProof/ (P.)
Experimental resource: discrete math course of zyBooks, http://www.zybooks.com/
== CS 420 Theory of Computing ==
Catalog Description
A sampling of the different areas of theoretical computer science: finite state concepts, formal grammars and automata, computability, Turing machines, and program verification.  Prerequisite - C or better in CS 202 and CS 303.
Most important prerequisite skills/knowledge: Willingness to work hard. Knowing how to write a formal mathematical proof.
Most important skills/knowledge gained: Basic understanding of fundamental computational models such as DFAs, NFAs, Turing machines, etc. and their properties.
Normal Content - closely follows the first 5 Chapters of the course textbook (see below), except that some topics are not covered in class
Regular languages:
Finite automata (DFA):
Formal definition of finite automata, examples
Formal definition of computation, designing finite automata
Regular operators
Formal definition of a nondeterministic finite automaton (NFA)
Equivalence of NFAs and DFAs (with proofs)
Closure under regular operations (with proofs)
Regular expressions:
Formal definition of a regular expression
Equivalence with finite automata (with proofs)
Nonregular languages
The pumping lemma for regular languages (with proofs, students are expected to master how to use this lemma that certain languages are nonregular)
Context-free languages:
Context-free grammars (CFG)
Formal definition of CFGs, examples of CFGs
Chomsky normal form
Pushdown automata (PDA)
Formal definition of PDA, examples
Equivalence of PDAs with CFGs, proof not covered in class
Non-context-free languages:
Pumping lemma for CFGs (students are expected to master how to use this lemma that certain languages are not context-free)
Church-Turing  thesis:
Turing machines: formal definition, examples
Variants of Turing machines, nondeterministic Turing machines, enumerators
Definition of an algorithm
Decidable languages:
Decidable languages concerning regular languages, context-free languages
Diagonalization method, examples of undecidable and Turing-unrecognizable languages
Some undecidable problems, reduction via computation histories
Computable function, mapping reducibility
Sample Exam Questions
Give a formal definition of a finite automaton.
Let Bn = {ak | k is a multiple of n}. Show that for each n ≥ 1, the language Bn is regular.
Use the pumping lemma to show that the language {0n1n0n1n} is not context free.
Let Σ = {1,2,3,4} and C = {w ∈ Σ* | in w, the number of 1s equals the number of 2s and the number of 3s equals the number of 4s}. Show that C is not context-free.
Define the following terms: (a) Turing-recognizable language, (b) co-Turing-recognizable language, (c) decidable language, (d) enumerator, (e) linear bounded automaton.
What does it mean that language A is mapping reducible to language B?
Let Q = {<M1,M2> | M1 and M2 are TMs and L(M1) = L(M2)}. Give a proof that Q is undecidable. You are allowed to use results from class.
Standard resources (textbook or online)
Introduction to the Theory of Computation, 3rd Edition, by Michael Sipser. ISBN 978-1133187790
== CS 421 Formal Methods ==
Catalog Description
Elements of formal logic; various approaches to automation including resolution; restrictions and search methods; inductive theorem-proving; Knuth-Bendix completion; Boyer-Moore theorem-prover; applications.  Prerequisite - C or better in CS 202 and CS 303.
Most important prerequisite skills/knowledge:
Student must have knowledge of  Discrete Structures
Most important skills/knowledge gained:
A  knowledge of  deductive logic and its applications in Computer Science.
Normal Content
This is meant to be a “Logic in Computer Science”  course.
The main topics covered are Propositional and First Order Logic Syntax and Semantics,proofs of valid arguments via resolution are stressed. Invalidity of arguments is demonstrated through the building of models for the premises and negated conclusions. The use of Automated Reasoning programs such as the OTTER theorem prover and MACE2 model builder is shown.
Reasoning with equality , is discussed using equality theories and paramodulation.
Reasoning in Inductive Theories is  covered.
Applications covered are:  Program Analysis, Design of Logic Circuits, Plan Generation,Question Answering, Answer Extraction,  and Logical Foundations of  Databases.
Important Assignments and/or Exam Questions
Assignments include chapter summaries of textbook chapters, and use of theorem provers and model builders ;  pencil and paper quizzes are given over the course content.
Standard resources (textbook or online)
Symbolic Logic and Mechanical Theorem Proving    by C-L Chang and R.C.T. Lee (Academic Press, 1973,  ISBN-10: 0-12-170350-9)
== CS 451 Architecture ==
Catalog Description
Data representation, number systems and codes, gates and logic, combinational logic, sequential circuits, flip-flops, memory and storage, computer organization, microprogramming, architectures of supercomputers and micros.  Prerequisite - C or better in CS 202 and CS 303.
Most important prerequisite skills/knowledge:
Student must have knowledge of  Programming and Elementary Data Structures and
Boolean Algebra and Logic.
Most important skills/knowledge gained:
A  knowledge of the working of a simple computer.
Normal Content
The course begins with a review of Logic Circuit Design: Combinational Circuits and Sequential Circuits. Covered topics include logic gates, decoders , encoders, multiplexers, ROMs, universal gates, adders, flip-flops, latches, Karnaugh Maps, equivalent states, counters, bit pattern detectors, incrementers, multipliers, etc.
This is followed by the discussion of Instruction Set Architectures, and an example architecture: The Relatively Simple Computer. Basic Computer System Organization is considered : CPU, Memory, I/O units, Buses, Linear ad Two dimensional memory organizations.
Hardware description using RTL and methods of implementing RTL code are described.
Next is the coverage of CPU Design: Registers, Instruction Sets, State diagrams, RTL Code, design of
register section, control units, ALUs, and generation of control signals are covered. This is the hardwired control approach.
Also covered are Microprogrammed Control and its variations: Horizontal Microcode, Vertical Microcode, and string control signals in the  ROM.
Next comes the coverage of Cache memory organization, and virtual memory. Topics covered are associative memory, and the associative , direct and set associative mappings and LRU and FIFO cache replacement strategies, and a simulation and estimation of hit ratios. Paging is covered in detail for implementing virtual memory, and a brief coverage of segmentation is provided.
Input/output is considered: polling, wait states, interrupt driven I/O, vectored interrupts, and Daisy Chaining, DMA transfers and transfer modes and I/O channels are covered.
CISC and RISC computers and pipelining are covered next.
Finally, an introduction to parallel and alternative computer architectures is given.
Important Assignments and/or Exam Questions
Assignments include chapter summaries of textbook chapters ;  pencil and paper quizzes are given over the course content.
Standard resources (textbook or online)
Computer Systems Organization and Architecture by John D. Carpinelli (Addison-Wesley, 2000, ISBN-10: 0-201-61253-4)
== CS452 Software Engineering ==
Catalog Description
This course studies the software life cycle: specification, object-oriented programming and design, program development, validation, testing, debugging, documentation, maintenance, revision control, CASE tools.  Prerequisite - C or better in CS 202.
Most important prerequisite skills/knowledge:
Student must have completed  a course in Object Oriented Programming
Most important skills/knowledge gained:
Object Oriented Analysis and Design : UML, Processes, Pragmatics, OCL, Model Driven Architecture.
Normal Content
The course begins with a review of Object Orientation, and of the Software Crisis. Next methods of classification are covered. That is followed by a coverage of UML and various diagrams. Next comes the discussion of Software Development Methods: Incremental and Iterative development, planned and agile methods, phases, milestones , macro and micro processes, are described.  Pragmatic issues are covered next: Personnel, Teams, Documentation, Reuse, Tools, Architecture, are discussed next. Next comes the development of functional, static, and dynamic views for example case studies, and a design procedure is given after the completion of these views. Also covered are 3-level architectures, and Jacobson’s stereotypes. The course concludes with a discussion of Object Constraint Language, and Model Driven Architecture. Use of tools for validation of models is described.
Important Assignments and/or Exam Questions
Study of a UML Modeling tool such as Modelio
An Object Oriented Design Case Study
Quizzes covering aspects of  UML , Processes, Pragmatics, Design, OCL and MDA.
Standard resources (textbook or online)
[1] Object-Oriented Analysis and Design with Applications (Third Edition)    by Grady Booch et al (Addison-Wesley, 2007,  ISBN-13: 978-0-201-89551-3)
[2] UML in Practice  by Pascal Roques (Wiley, 2004, ISBN-13: 978-0470848319) 
[3] The Object Constraint Language (Second Edition) by Jos Warmer & Anneke Kleppe (Addison-Wesley, 2003, ISBN 978-0-321-17936-4)
== CS 456 Systems Programming ==
Catalog Description
An introduction to both program translation and operating systems. There will be a survey of topics such as: top-down and bottom-up parsing, scanning, code generation, symbol table management, linkers and loaders, batch processing systems, interacting processes, multiprogramming systems, and memory management.  Prerequisite - C or better in CS 202.
Most important prerequisite skills/knowledge:  C programming.
Most important skills/knowledge gained: Solid understanding of the Unix/Linux API.  Basic understanding of programming language translation.
Normal Content
Version control: Make, RCS, Git
File system I/O - open/close/read/write, printf/scanf, opendir/closedir/readdir/stat
Local interprocess communication: signals, socketpairs, shared memory.
Fork and execve: how shells work.
Regular expressions (review!)
Condensed introduction to x64 assembly language.
How assemblers work.
Structure of ELF files -- use of tools like objdump, readelf, nm, od.
Lex/flex and yacc/bison examples starting with a simple calculator and then a simple programming language (something on the level of Dartmouth BASIC).
Important Assignments and/or Exam Questions
Write a variant of ls(1) requiring accessing permissions and subdirectory traversal.
A basic shell (command interpreter) with a read, parse, execute loop using a PATH, I/O redirection and pipes.
Assembly language programming exercises, with a view to introducing the subset of assembler needed for compiler code generation.
Extend calculator example done in class -- student might add parenthetical expressions or named (one line) functions, for example.
A working compiler for a simple programming language.
A working assembler would be a less time consuming alternative if more time was spent on the shell.
Standard resources (textbook or online)
The manual.
Linux System Programming: Talking Directly to the Kernel and C Library, Edition 2, Robert Love (O’Reilly)
flex & bison, by John Levine (O’Reilly)
== CS 457 Data Base Processing ==
Catalog Description
Data independence, relational model, relational algebra and calculus, query languages and SQL, conceptual modeling, database design, data dependencies and normalization, access methods, tables, queries, forms, macros and reports, database administration, introduction to transaction processing, concurrent transactions, and recovery. Case studies of commercial database systems such as Oracle and Microsoft SQL Server.  Prerequisite - C or better in CS 202 and CS 303.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
Database Models
Relational Algebra
SQL - A reasonably comprehensive introduction to SQL.  SQLite is a very good, easy to use, vehicle for this part of the course.
Database design: logical design, physical design, security design.
Database design: ER diagrams, normal forms, functional dependencies, transitive closure, etc.
Transactions: query processing, ACID, logging, indexing, hashing, B+ trees, joins.
SQL - More advanced features (PL/SQL functions, triggers, etc.)
NOSQL: discuss a subset of the following (whatever’s hot)
DataFrames - Python/pandas
many more possibilities
Important Assignments and/or Exam Questions
Relational algebra exercises (pencil and paper) with a variety of joins.
Single table SQLite assignment for experience using SQLite features and basic queries.
Multi-table SQLite assignment in the context of normal forms.  An example: students at a university with tables for personal data (addresses), financial data (tuition payments), and performance data (credits, grades).
Assignment to practice C or Python (or whatever) interface to SQLite.
Postgres/Oracle assignment using multiple databases, tables, triggers, transactions, etc.  Examples could include the student/university database with the addition of classes, grades, adding, dropping, room assignments, courses, scheduling, faculty schedules, etc..  A more standard example is a company with employees, customers, suppliers, departments, etc.
(Mongodb, etc.) Pick smaller database problems and implement them using SQL, mongodb and redis (for example).  Compare performance.
Standard resources (textbook or online)
Stanford Database Course with Jennifer Widom (available from YouTube).  Not a full course, but a nice outline that goes at a slower pace than one might expect from Stanford. PDF files are also available for a more comprehensive version of the course.
== CS 458 Algorithms ==
Catalog Description
Among the topics covered are: review of basic data structures and their implementations; graphs, both directed and undirected; analysis of algorithms; sorting, searching, and merging, both internal and external methods; memory management algorithms; mathematical algorithms; and, as time allows, advanced topics such as NP-complete problems. Prerequisite - C or better in CS 202 and CS 303.
Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
Important Assignments and/or Exam Questions
Standard resources (textbook or online)  
== CS 469 Unix/Linux Administration and Networking ==
Catalog Description
Includes installation and configuration of Unix/Linux operating system software; set-up of hardware and software for Unix/Linux networking including TCP/IP, FTP, Telnet, DNS, DHCP, and Apache; Unix/Linux administration tasks including directories, users, tuning, backup, security, and networking.  Prerequisite - C or better in CS 201.
Most important prerequisite skills/knowledge: Basic Unix skills, some prior programming experience
Most important skills/knowledge gained:
Comprehensive overview of command line tools used by a system administrator
More advanced bash scripting
Ability to install and configure a Linux system
Some Virtual Machine experience
Normal Content
Wild-cards and regular expressions
Files and directories:
The file-system tree, path traversal, links
Unix permissions and ACLs
The FHS standard: where things go in the file-system
Bash scripting
Invocation and startup, job control
Command lists, pipelines, redirection
Positional parameters and special variables, data types, the environment
Functions, variable scope
Conditionals and loops
Bash built-ins: read, printf, alias, etc
The core-utilities: sed, col, grep, tr, basename, dirname, etc.
Processes and threads:
Attributes of processes: understanding ps,top, etc output
/proc filesystem
Resource limits
Memory layout: security issues: buffer overflows, ASLR
The boot process: boot loaders, the kernel, init, runlevels, init scripts
Disks: Block devices, partitioning, making file-systems, mounting/unmounting them, checking them, configuring fstab
Swap and virtual memory
RAID: levels, MD devices and mdadm
Basic MySQL administration: DB and user administration and backing up/archiving databases
Common Administrative tasks:
User/group administration
Log files, accounting files and reporting
SSH and related tools for key generation and management, scp, rsync
Various networking terms / OSI model
SSL/TLS certificates (openssl), creating signed certificates, setting up a CA purpose of certs, anatomy of a cert
IPv4 networking: Packets, Ethernet, ARP, DNS, CIDR, basic routing
The Linux Firewall (iptables) (time permitting)
Important Assignments and/or Exam Questions
Various man page reading assignments
Bash scripts: iterate over command line parameters and do something with them, find the largest file in a directory tree, etc.
Create a Virtual Machine and install Linux onto it.
Root administration tasks on a provided VM:
Setup and configure accounts
Setup and configure services: http and mysql
Install and web service(s) requiring a working web server and mysql instance
Create a certificate authority and sign other students cert requests
Standard resources (textbook or online)
The Unix man pages
Tutorials Point
== CS 470 Programming Languages ==
Catalog Description
The purpose of the course is to develop an understanding of the organization of programming languages and introduce the formal study of programming language specification and analysis. Topics covered usually include: language definition structure, data types and structures, control structures and data flow, run-time consideration, interpretative languages, lexical analysis, and parsing.  Prerequisite - C or better in CS 202.
Most important prerequisite skills/knowledge:
Student must have knowledge of  Programming and Elementary Data Structures
Most important skills/knowledge gained:
Functional, Logic, Object-Oriented and Concurrent programming paradigms, syntax and semantics of programming languages.
Normal Content
The course begins with a history of programming languages, and the various  programming paradigms are introduced. The Logic Programming paradigm is covered using Prolog as the example. Backtracking, unification, recursion, the cut , depth first search are covered. Stack overflows, occurs check , and floundering problems are covered. Applications covered are list processing, state space problem solving, constraint processing, expert systems, natural language processing and parsing.
The Functional Programming paradigm  is illustrated using Haskell. Covered are list processing and the conversion to  tail recursion using the method of accumulating parameters, fixed point computation, square root computation and sorting, testing of perfect numbers, and implementing the Sieve or Eratosthenes using Lazy Evaluation, available in Haskell. Proofs of list properties using structural induction are covered, and the implementation of data structures using Haskell is covered.
The Object Oriented Programming paradigm is covered using Smalltalk: introduced are the elements of the GUI: browsers, Workspaces, and Transcripts, Defining classes, and objects, inheritance and aggregation hierarchies are introduced. Avoidance of conditional code through polymorphism, polymorphism within and across inheritance hierarchies is considered, and the model –view – controller pattern through the use of the dependency mechanism are described. The issue of aggregation vs. inheritance is discussed  via a concrete example.
The Concurrent Programming paradigm is introduced. Three synchronization problems are considered: Serialization, Mutual Exclusion and the Rendezvous. Semaphores are introduced and the use of Semaphores  in solving the synchronization problems are discussed. Implementations of the solutions are given in Smalltalk, using the Process and Semaphore implementations available in Smalltalk.
Finally aspects of the syntax and semantics of programming languages are covered.
Important Assignments and/or Exam Questions
In each of the programming paradigms, short assignments, and a larger assignment are given.
Standard resources (textbook or online)
[1] Learn Prolog Now  http://www.learnprolognow.org/
[2] Learn You a Haskell for Great Good  http://learnyouahaskell.com/
[3] Squeak Smalltalk  https://squeak.org/
[4] The Little Book of Semaphores http://greenteapress.com/semaphores/LittleBookOfSemaphores.pdf
[5]  Syntax and Semantics of Programming Languages    http://homepage.divms.uiowa.edu/~slonnegr/plf/Book/
== CS 471 Operating Systems ==
Catalog Description
Major topics include system structure, memory management, and process management. Hands-on experience using the department’s minicomputer facilities are an important part of the course.  Prerequisite - C or better in CS 202.
Most important prerequisite skills/knowledge:
C Programming to the CS201/CS202 Level
Understanding logical (boolean) operations to the CS303 Level
Functions every citizen should know - close, execve, fclose, fgetc, fopen, fork, fprintf, fputc, fread, free, fscanf, fseek, fstat, fwrite, getchar, getpid, getuid, lseek, malloc, memcpy, memset, open, printf, pthread_create, pthread_exit, pthread_join, pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock, putchar, random, read, realloc, scanf, sem_init, sem_post, sem_wait, shm_open, shm_unlink, sleep, srandom, stat, strcasecmp, strcat, strcmp, strcpy, strlen, time, unlink, usleep, wait, write
Most important skills/knowledge gained:
An Operating System is a complex computer program that mediates access to three essential resources: CPU, memory, and devices.  The main goal of this class is gain an understanding of how these three objectives are met.  A secondary goal is to understand how some of the ideas which originated as solutions to operating systems problems have contributed to solutions to other problems.
Normal Content
Review - functions every citizen should know, basic data structures in C (1-2 weeks)
Device Management, typically focusing on storage devices and filesystems (3 weeks)
ext2 file system in detail
Other filesystems at a high level
Process/Thread Management (3 weeks)
Single CPU execution - time slicing, scheduling
Multi-core execution
Shared data - semaphores, other mechanisms, synchronization issues, race conditions
Memory Management (3 weeks)
Memory organization, virtual memory, pages, page faults, CPU cache
Other Topics, as time allows
Important Assignments and/or Exam Questions
Process Management: writing a simple scheduler for a simplified OS.  A basic data file driven version of this assignment might use a data file which lists a sequences of jobs.  For each job, the data file would specify the time and resource demands of the job.  Output would include snapshots of the process table at any given time.  A more challenging version of this assignment would call for a realistic process table (red-black trees, etc.).
Memory Management: an implementation of a basic memory management scheme, e.g., the buddy system.  A basic version of this assignment could use a data file similar to the one used in the Process Management assignment.  An alternative, more challenging assignment would be implementing a library to replace malloc.
Device Management: a program that requires students to read and write to a filesystem, updating inodes, directories, and block bitmaps.  The ext2 filesystem is a useful simple example for which one can find a wealth of online resources.  The ‘read’ portion of this assignment is significantly easier than the ‘write’ portion.
    For at least one of these three assignments, the more ambitious variant should be expected.
Learning Outcomes
Source code for unix system calls - can trace through and explain the code, can make modifications.
Unix system calls - can write programs that use the calls to mimic unix utility commands.
Synchronization primitives - can explain proper use and write correct code that uses primitives to avoid race conditions or logical errors.
Common scheduling algorithms - can explain common algorithms and tradeoffs.
Process accounting - can explain in detail at least one process accounting system.
File systems - can explain in detail the layout of at least one modern file system, can explain basic properties and tradeoffs of a number of others.
Virtual memory - can explain fundamental concepts and their impact on performance, can explain in detail the mechanism of at least one modern memory management system.
Modern computer and operating system - can explain the basic architecture of modern computers and operating systems, including how an operating system ensures proper sharing of the following between different programs and users - CPU, disk, memory, other devices.
Standard resources (textbook or online)
Understanding the Linux Kernel, Bovet and Cesati
Unix Filesystems, Pate
The Little Book of Semaphores
The ext2 File System
The Unix Timesharing System
Operating Systems: Three Easy Pieces
== CS 473 Networking ==
Catalog Description
The course is an introduction to networking and includes detailed study of Internet protocols and socket programming. Topics include a study of IP, UDP, and TCP protocols, as well as application layer protocols such as HTTP and SMTP. Students learn to program both a client and server.  Prerequisite - C or better in CS 202.
Most important prerequisite skills/knowledge:
C programming.
Most important skills/knowledge gained:
Understanding of data flow on the internet.
Understanding the fundamentals of network security and encryption.
Ability to write client and server programs in C.
Normal Content
History and Operation of Packet Networks and Switched Networks
Layered Protocols: TCP/IP and (maybe) OSI.
Socket programming - TCP/UDP - in C.
Example higher level protocols examined in some detail (e.g., SMTP or HTTP).
Encryption and the four horsemen of the apocalypse: symmetric block ciphers, cryptographic hashing functions, public key cryptosystems, and cryptographic random number generation.  Discussion of SHA, AES, RSA, TLS.
Important Assignments and/or Exam Questions
Reading and analyzing packet dumps.
TCP Client/Server programming in C.  Writing client and server programs for a specific purpose -- a multiuser game is a popular variant.  The application level data might be text.  Useful option: instructor writes the server, student writes the client.
UCP Client/Server programming in C: Similar to the TCP assignment, but this is a natural place to require detailed packet design (bit fiddling) and introduce big endian/little endian issues.
Standard resources (textbook or online)
The original BSD Interprocess Communication tutorials are still very useful.
Unix Network Programming, Volume 1: The Sockets Networking API (3rd Edition) 3rd Edition
by W. Richard Stevens  (Author), Bill Fenner (Author), Andrew M. Rudoff (Author)
== CS 479 Web Programming II ==
Catalog Description
Advanced programming for the World Wide Web and the Internet. This course includes client and server side programming with HTML/CSS/ECMAScript on the client side and PHP/mysqli scripting on the server. As well as some server side configuration using the Apache web server.  Prerequisite - C or better in CS 170 and CS 201.
Most important prerequisite skills/knowledge: Basic understanding of HTML, CSS and JavaScript (ECMAScript) in the browser
Most important skills/knowledge gained:  HTML forms, client side ECMAScript-ing and server side PHP scripting and MySQL. Understanding of basic web security concepts.
Normal Content
Review of CS170 concepts:
Basic HTML: basic formatting, lists, tables
Extensive HTML forms review
Basic CSS: selectors, box model, colors, fonts
JavaScript/ECMAScript review: basic data-types, variables and scope, functions, conditionals, loops.
The DOM, document and window objects, events and the event object
PHP Scripting:
Data-types and scoping
Super-Globals: $_GET, $_POST, etc.
Language features: functions, conditionals, loops: while, for, foreach
Databases and tables
SQL syntax: creating table, insert, update, delete and select
The PHP Mysqli interface (switch to PDO?)
simple vs. prepared statements
Security, escaping strings, input validation, etc
AJAX: Asynchronous client/server pages via XMLHttpRequest and JSON encoded data.
HTTP authentication schemes including HTTP auth, PHP sessions, creating long lived sessions using sessions cookies coupled with a user and sessions tables, password hashing, SSL/TLS security
WebSockets (time permitting)
Important Assignments and/or Exam Questions
CS170 style review problems:
Creating static HTML forms and submitting to a PHP form handler
Dynamic PHP pages using $_GET variables
Simple ECMAScript dynamic server pages (PHP generated server side data requested via XMLHttpRequest() on the client.)
Creating tables and inserting data into a MySQL database via PHP from files / web forms.
Paginated display of a database w/ column sorting via server side PHP/Mysqli
Chat client/server (time permitting)
Standard resources (textbook or online)
W3Schools, Mozilla Developer Network (MDN)
PHP.net, Mariadb.org, etc.
== CS 499 Senior Seminar==
Catalog Description
The senior seminar is taken by students in their last year.  The course prepares students for the process of applying for and interviewing for jobs or a graduate program.  Students also present on current topics in computer science.  Prerequisite - senior standing, C or better in CS 202.
Most important prerequisite skills/knowledge: ready to graduate
Most important skills/knowledge gained: solidify/refresh basic programming, can handle interview questions, well-prepared application materials
Normal Content
Creating application materials - resume, cover letter
Technical application materials - github with sample projects, personal website with information linked
Practice interview questions - basic programming, at least one other type (database, web, etc.)
Job search and applying for jobs
Presentation skills
Important Assignments and/or Exam Questions
ISU CS programming assessment - must pass to pass the class
Hackerrank programming problems - basic programming and at least one other category
Application materials - create and make adjustments based on feedback
Visit Career Center to receive feedback on application materials
Mock interview with CS 499 instructor
Mock interview at Career Center
Pick one project from coursework and create powerpoint presentation, give presentation to the class, make corrections based on feedback
Standard resources (textbook or online)
Cracking the Coding Interview by G. L. McDowell (any edition)
Accompanying website https://www.hackerrank.com/
ISU Career Center
Communications of the ACM - http://cacm.acm.org/

Latest revision as of 02:01, 14 November 2022

Basic Information About CS Courses

Note: as of summer 2018, this document contains information about all courses that are required in the CS or IT majors. Other CS courses are not listed here yet.

Points of Contact

Steve Baker - CS 151, 469, 479
Laci Egri - CS 303, 420
Arash Rafiey - CS 256, 458
Geoff Exoo - CS 456, 471, 473
R.B. Abhyankar - CS 421, 451, 452, 470
Jeff Kinne - CS 170, 202, 260, 499
Rob Sternfeld - CS 101, 201, 457


CS 101 is prerequisite for - CS 151
CS 151 is prerequisite for - CS 170, 201, 260, 303
CS 170 is prerequisite for - 479
CS 201 is prerequisite for - CS 202, 469, 479
CS 202 is prerequisite for - all 400 level except 469, 479
CS 303 is prerequisite for - CS 420, 421, 457, 458
Math 115 is corequisite for - CS 201
Math 115 is prerequisite for - CS 202, 303
Courses with no prerequisite - CS 151, 256

CS Courses Standard Content Pages