Difference between revisions of "CS Courses Standard Content"

From Computer Science
Jump to: navigation, search
(Prerequisites)
 
(62 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. 
+
=Points of Contact=
Steve Baker - CS 151, 469, 479   
+
Steve Baker - CS 151, 469, 479  <br>
Laci Egri - CS 303, 420   
+
Laci Egri - CS 303, 420  <br>
Arash Rafiey - CS 256, 458   
+
Arash Rafiey - CS 256, 458  <br>
Geoff Exoo - CS 456, 471, 473   
+
Geoff Exoo - CS 456, 471, 473  <br>
R.B. Abhyankar - CS 421, 451, 452, 470   
+
R.B. Abhyankar - CS 421, 451, 452, 470  <br>
Jeff Kinne - CS 170, 202, 260, 499   
+
Jeff Kinne - CS 170, 202, 260, 499  <br>
Rob Sternfeld - CS 101, 201, 457   
+
Rob Sternfeld - CS 101, 201, 457  <br>
 
    
 
    
Prerequisites
+
=Prerequisites=
CS 151 is prerequisite for - CS 170, 201, 260
+
CS 101 is prerequisite for - CS 151<br>
CS 170 is prerequisite for - 479
+
CS 151 is prerequisite for - CS 170, 201, 260, 303 <br>
CS 201 is prerequisite for - CS 202, 303, 469, 479
+
CS 170 is prerequisite for - 479 <br>
CS 202 is prerequisite for - all 400 level except 469, 479
+
CS 201 is prerequisite for - CS 202, 469, 479 <br>
CS 303 is prerequisite for - CS 420, 421, 457, 458
+
CS 202 is prerequisite for - all 400 level except 469, 479 <br>
Math 115 is corequisite for - CS 201
+
CS 303 is prerequisite for - CS 420, 421, 457, 458 <br>
Math 115 is prerequisite for - CS 202, 303
+
Math 115 is corequisite for - CS 201 <br>
Courses with no prerequisite - CS 151, 256
+
Math 115 is prerequisite for - CS 202, 303 <br>
 +
Courses with no prerequisite - CS 151, 256 <br>
  
Items to spin off as standalone videos / tutorials
+
= CS Courses Standard Content Pages =
Editors - vim, emacs, pico, atom.  Should be able to edit text files, save changes, make copies.
+
* [[CS 101 Fundamentals of Computing]]
IDEs - eclipse, MS visual studio.  Should be able to create a project, add source files, compile and run, debug.
+
* [[CS 151 Introduction to Computer Science]]
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.
+
* [[CS 170 Web Programming]]
Unix tools - grep, sed, awk, find, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection.
+
* [[CS 201 Computer Science I]]
 
+
* [[CS 202 Computer Science II]]
Course descriptions have been updated for the following courses:
+
* [[CS 256 Structured Design]]
== Table of Contents ==
+
* [[CS 260 Object Oriented Programming]]
 
+
* [[CS 303 Discrete Structures]]
Table of Contents
+
* [[CS 420 Theory of Computing]]
Programming Assessment
+
* [[CS 421 Formal Methods]]
CS 101 Fundamentals of Computing
+
* [[CS 451 Architecture]] 
CS 151 Introduction to Computer Science
+
* [[CS 452 Software Engineering]]
CS 170 Web Programming
+
* [[CS 456 Systems Programming]]
CS 201 Computer Science I
+
* [[CS 457 Data Base Processing]]
CS 202 Computer Science II
+
* [[CS 458 Algorithms]] ''(needs information)''
CS 256 Structured Design
+
* [[CS 469 Unix/Linux Administration and Networking]]
CS 260 Object Oriented Programming
+
* [[CS 470 Programming Languages]]
CS 303 Discrete Structures
+
* [[CS 471 Operating Systems]]
CS 420 Theory of Computing
+
* [[CS 473 Networking]]
CS 421 Formal Methods
+
* [[CS 479 Web Programming II]]
CS 451 Architecture
+
* [[CS 499 Senior Seminar]]
CS452 Software Engineering
 
CS 456 Systems Programming
 
CS 457 Data Base Processing
 
CS 458 Algorithms
 
CS 469 Unix/Linux Administration and Networking
 
CS 470 Programming Languages
 
CS 471 Operating Systems
 
CS 473 Networking
 
CS 479 Web Programming II
 
CS 499 Senior Seminar
 
 
 
 
 
 
 
 
 
== Programming Assessment ==
 
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)
 
http://cs.indstate.edu/info/policies.html#assessment
 
 
 
 
 
== 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:
 
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/
 

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

Prerequisites

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