CS Courses Standard Content

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

Prerequisites

CS 151 is prerequisite for - CS 170, 201, 260
CS 170 is prerequisite for - 479
CS 201 is prerequisite for - CS 202, 303, 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

TODO/Possible New Pages

Items to spin off as standalone videos / tutorials
Editors - vim, emacs, pico, atom. Should be able to edit text files, save changes, make copies.
IDEs - eclipse, MS visual studio. Should be able to create a project, add source files, compile and run, debug.
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.
Unix tools - grep, sed, awk, find, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection.

=Catalog Description

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. Most important prerequisite skills/knowledge:
Most important skills/knowledge gained:
Normal Content
C programming, with one program from five different types…
Simple program that requires a loop or nested loops.
Program that scans through text a character at a time to do something.
Linked list traversal.
Binary tree traversal.
Bit operations.

Important Assignments and/or Exam Questions

Standard resources (textbook or online) CS Programming Assessment Wiki Page

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.

Prerequisites

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

Standard 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

• TODO

Standard resources

• 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: None 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 HTML and CSS 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: Data-types: 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 Conditionals: if, if-else, if-else chaining Simple Boolean logic: NOT, AND, OR, Boolean expressions Switch? Functions and methods, method-chaining Loops: 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) Algorithms: 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 Math: Bases - converting to/from binary and decimal, Hexadecimal and Octal Summation Modulus arithmetic Bases 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) W3Schools 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 Functions Collections 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 Events setTimeout() and setInterval() Promises 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) KnockoutJS Vue React

Important Assignments and/or Exam Questions

Standard resources (textbook or online) (optional) JavaScript: The Good Parts by Douglas Crockford https://www.amazon.com/JavaScript-Good-Parts-Douglas-Crockford/dp/0596517742 (optional) JavaScript Patterns by Stoyan Stefanov https://www.amazon.com/dp/0596806752/ref=rdr_ext_tmb Mozilla Developer Network (MDN) https://developer.mozilla.org/en-US/docs/Web

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 Nondeterminism: 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 Undecidability: Diagonalization method, examples of undecidable and Turing-unrecognizable languages Reducibility: 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) XML Mongodb Redis levelDB DataFrames - Python/pandas Cassandra 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 Signals Resource limits Memory layout: security issues: buffer overflows, ASLR Libraries 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 Quotas Networking: 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: Output Data-types and scoping Super-Globals: $_GET, $_POST, etc. Language features: functions, conditionals, loops: while, for, foreach MySQL/MariaDB: Databases and tables Data-types 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/