|
|
| (11 intermediate revisions by one other user not shown) |
| Line 13: |
Line 13: |
| | | | |
| | =Prerequisites= | | =Prerequisites= |
| − | CS 151 is prerequisite for - CS 170, 201, 260 <br> | + | CS 101 is prerequisite for - CS 151<br> |
| | + | CS 151 is prerequisite for - CS 170, 201, 260, 303 <br> |
| | CS 170 is prerequisite for - 479 <br> | | CS 170 is prerequisite for - 479 <br> |
| − | CS 201 is prerequisite for - CS 202, 303, 469, 479 <br> | + | CS 201 is prerequisite for - CS 202, 469, 479 <br> |
| | CS 202 is prerequisite for - all 400 level except 469, 479 <br> | | CS 202 is prerequisite for - all 400 level except 469, 479 <br> |
| | CS 303 is prerequisite for - CS 420, 421, 457, 458 <br> | | CS 303 is prerequisite for - CS 420, 421, 457, 458 <br> |
| Line 21: |
Line 22: |
| | Math 115 is prerequisite for - CS 202, 303 <br> | | Math 115 is prerequisite for - CS 202, 303 <br> |
| | Courses with no prerequisite - CS 151, 256 <br> | | Courses with no prerequisite - CS 151, 256 <br> |
| − |
| |
| − | =TODO/Possible New Pages=
| |
| − | Items to spin off as standalone videos / tutorials <br>
| |
| − | Editors - vim, emacs, pico, atom. Should be able to edit text files, save changes, make copies.<br>
| |
| − | IDEs - eclipse, MS visual studio. Should be able to create a project, add source files, compile and run, debug.<br>
| |
| − | Debugging - gdb. Should be able to compile with debug information, use gdb to find where seg fault occurs, set breakpoints and look at variable values, step line by line through code.<br>
| |
| − | Unix tools - grep, sed, awk, find, makefiles, unix regular expressions, reading manual and manual organization, pipes, I/O redirection.<br>
| |
| − |
| |
| − | =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.
| |
| − |
| |
| − | == Prerequisites ==
| |
| − | * ''TODO''
| |
| − |
| |
| − | ==Standard 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==
| |
| − | * ''TODO''
| |
| − |
| |
| − | ==Standard resources==
| |
| − | [[Programming Assessment|CS Programming Assessment Wiki Page]]
| |
| − |
| |
| | | | |
| | = CS Courses Standard Content Pages = | | = CS Courses Standard Content Pages = |
| Line 62: |
Line 34: |
| | * [[CS 420 Theory of Computing]] | | * [[CS 420 Theory of Computing]] |
| | * [[CS 421 Formal Methods]] | | * [[CS 421 Formal Methods]] |
| − | * [[CS 451 Architecture]] | + | * [[CS 451 Architecture]] |
| − | * [[CS452 Software Engineering]] | + | * [[CS 452 Software Engineering]] |
| | * [[CS 456 Systems Programming]] | | * [[CS 456 Systems Programming]] |
| | * [[CS 457 Data Base Processing]] | | * [[CS 457 Data Base Processing]] |
| − | * [[CS 458 Algorithms]] | + | * [[CS 458 Algorithms]] ''(needs information)'' |
| | * [[CS 469 Unix/Linux Administration and Networking]] | | * [[CS 469 Unix/Linux Administration and Networking]] |
| | * [[CS 470 Programming Languages]] | | * [[CS 470 Programming Languages]] |
| Line 73: |
Line 45: |
| | * [[CS 479 Web Programming II]] | | * [[CS 479 Web Programming II]] |
| | * [[CS 499 Senior Seminar]] | | * [[CS 499 Senior Seminar]] |
| − |
| |
| − | = 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.
| |
| − |
| |
| − | == Prerequisites ==
| |
| − | * basic programming concepts
| |
| − | * ability to use unix
| |
| − |
| |
| − | == Standard Content ==
| |
| − | ===Course Outline ===
| |
| − | * 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)
| |
| − |
| |
| − | ===Learning Outcomes===
| |
| − | * 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)
| |
| − |
| |
| − |
| |
| − | ===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 ===
| |
| − | * 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.
| |
| − |
| |
| − | == Prerequisites ==
| |
| − | * ''TODO''
| |
| − |
| |
| − | == Standard Content ==
| |
| − | ===Course Outline ===
| |
| − | * ''TODO''
| |
| − |
| |
| − | ===Learning Outcomes===
| |
| − | The following are the most important learning outcomes for each of the 8 topics listed in the course outline.
| |
| − | * ''TODO''
| |
| − |
| |
| − | ===Important Assignments and/or Exam Questions===
| |
| − | * ''TODO''
| |
| − |
| |
| − | === Standard resources ===
| |
| − | * ''TODO''
| |
| − |
| |
| − | = 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.
| |
| − |
| |
| − | == Prerequisites ==
| |
| − | * ''TODO''
| |
| − |
| |
| − | == Standard Content ==
| |
| − | ===Course Outline ===
| |
| − | * ''TODO''
| |
| − |
| |
| − | ===Learning Outcomes===
| |
| − | The following are the most important learning outcomes for each of the 8 topics listed in the course outline.
| |
| − | * ''TODO''
| |
| − |
| |
| − | ===Important Assignments and/or Exam Questions===
| |
| − | * ''TODO''
| |
| − |
| |
| − | === Standard resources ===
| |
| − | * ''TODO''
| |
| − |
| |
| − | = 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.
| |
| − |
| |
| − | == Prerequisites ==
| |
| − | * Willingness to work hard.
| |
| − |
| |
| − | == Standard Content ==
| |
| − | ===Course Outline ===
| |
| − | * 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)
| |
| − |
| |
| − | ===Learning Outcomes===
| |
| − | * Capable of constructing rigorous mathematical proofs using direct proof, proof by contradiction, induction, etc.
| |
| − |
| |
| − |
| |
| − | ===Important Assignments and/or 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 ===
| |
| − | * [https://www.amazon.com/Discrete-Mathematics-Its-Applications-Seventh/dp/0073383090/ref=sr_1_1?dchild=1&keywords=978-0073383095&qid=1621279949&sr=8-1 “Discrete mathematics and its applications”, 7th edition, by Kenneth Rosen. ISBN: 978-0073383095 (R.)]
| |
| − | * [https://www.people.vcu.edu/~rhammack/BookOfProof/ Book of Proofs (P.)]
| |
| − | * Experimental resource: [http://www.zybooks.com/ discrete math course of zyBooks]
| |
