Soma-notes - User contributions [en]

CR: COMP 2804 Learning Objectives

2011-04-11T17:51:24Z

Maheshwa: /* Assumed Background */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805 (Minimum grade of B-?)
* MATH 1007
* MATH 1104
* COMP 1406

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Design and analysis of several simple randomized algorithms will be discussed
during the course. Statistical ...

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta, Solving recurrence relations.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoff Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing, p-values, chi square, ANOVA (Analysis of Variance)
* Probability distributions: Poisson, normal, power laws (Zipf's law)

CR: COMP 2804 Learning Objectives

2011-04-11T17:50:26Z

Maheshwa: /* Assumed Background */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805
* MATH 1007
* MATH 1104
* COMP 1406

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Design and analysis of several simple randomized algorithms will be discussed
during the course. Statistical ...

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta, Solving recurrence relations.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoff Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing, p-values, chi square, ANOVA (Analysis of Variance)
* Probability distributions: Poisson, normal, power laws (Zipf's law)

CR: COMP 2804 Learning Objectives

2011-04-11T17:49:47Z

Maheshwa: /* Assumed Background */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805
* MATH 1007
* MATH 1104

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Design and analysis of several simple randomized algorithms will be discussed
during the course. Statistical ...

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta, Solving recurrence relations.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoff Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing, p-values, chi square, ANOVA (Analysis of Variance)
* Probability distributions: Poisson, normal, power laws (Zipf's law)

CR: COMP 2402 Learning Objectives

2011-04-11T17:49:06Z

Maheshwa: /* Assumed Background */

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1406.
*MATH 1007
*MATH 1104

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, the performance issues, both theoretical and practical will be discussed. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: MATH 1007 Learning Objectives

2011-04-11T17:44:40Z

Maheshwa: /* Elementary Calculus I */

==Elementary Calculus I==

*Limits - introduce O, o, Theta functions.
*Differentiation of the elementary functions.
*Rules of differentiation.
*Applications of differentiation: max-min problems, curve sketching, approximations.
*Definite and indefinite integrals, integration by substitution.

*Precludes additional credit for BIT 1000, BIT 1100, MATH 1002, MATH 1004, MATH 1009.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent.
Lectures three hours a week, tutorial one hour a week.

CR: COMP 1805 Learning Objectives

2011-03-23T18:42:38Z

Maheshwa: /* Topics */

=Calendar Description=
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

=Assumed Background=

I am assuming that the students will do this course in 2nd term of their first year.
Requirements include:
*At least one course in Grade 12 Mathematics (with U TAG)
*Completed MATH 1007 (Elementary Calculus) with a grade of ...
*Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of
*1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
*2. Should have Mathematical sophistication, for example should be able to solve/show that
** Sum of two odd numbers is even
** Not all real numbers are rationals
** The number of prime numbers is infinite
** The number of possible subsets of set of size n is 2^n
** Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
** Should know what is a function, what are properties of function.
** Given a system three linear equations, in three variables, should know how to solve it.
** Should know how to solve a quadratic equation
** Should know how to compute a formula for the sum of first n natural numbers.
....

=Learning Objectives=

Objectives for the whole course
* Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation, what is a 64-bit machine?
* Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, and finite-state machines.
* Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

=Topics=
This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course.
Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

*Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

*Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

*Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation.

* Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

*Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

*Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use. (possibly cover Halting Problem - As an example of Proof by Contradiction [3.1]).

* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

* Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language as a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

* Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

* Sets and Functions [2.1, 2.2, 2.3]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and/or Linear Algebra courses).

* Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

* More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).

CR: MATH 1007 Learning Objectives

2011-03-23T18:19:22Z

Maheshwa: /* Elementary Calculus I */

==Elementary Calculus I==

*Limits.
*Differentiation of the elementary functions.
*Rules of differentiation.
*Applications of differentiation: max-min problems, curve sketching, approximations.
*Definite and indefinite integrals, integration by substitution.

*Precludes additional credit for BIT 1000, BIT 1100, MATH 1002, MATH 1004, MATH 1009.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent.
Lectures three hours a week, tutorial one hour a week.

CR: MATH 1007 Learning Objectives

2011-03-23T18:18:11Z

Maheshwa: Created page with "==Elementary Calculus I=="

==Elementary Calculus I==

CR: Learning Objectives

2011-03-23T18:17:41Z

Maheshwa:

* [[CR: COMP 1405 Learning Objectives]]
* [[CR: COMP 1406 Learning Objectives]]
* [[CR: COMP 1805 Learning Objectives]]
* [[CR: COMP 2401 Learning Objectives]]
* [[CR: COMP 2402 Learning Objectives]]
* [[CR: COMP 2404 Learning Objectives]]
* [[CR: COMP 2405 Learning Objectives]]
* [[CR: COMP 2804 Learning Objectives]]
* [[CR: COMP 3004 Learning Objectives]]
* [[CR: COMP 3804 Learning Objectives]]
* [[CR: MATH 1104 Learning Objectives]]
* [[CR: MATH 1007 Learning Objectives]]

CR: MATH 1104 Learning Objectives

2011-03-23T18:15:15Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factorization and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants, LU decomposition,
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.

*Topics Omitted: Complex numbers, Eigenvalues,

CR: MATH 1104 Learning Objectives

2011-03-23T18:14:33Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants, LU decomposition,
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.

*Topics Omitted: Complex numbers, Eigenvalues,

CR: MATH 1104 Learning Objectives

2011-03-23T18:14:08Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants, LU decomposition,
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.
**?Group Theory: Definition, Z_p, ..?

*Topics Omitted: Complex numbers, Eigenvalues,

CR: MATH 1104 Learning Objectives

2011-03-23T18:13:47Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants, LU decomposition,
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.
**?Group Theory: Definition, Z_p, ..?

*Topics Omitted: Complex numbers, Eigenvalues, Diagonalization and applications.

CR: MATH 1104 Learning Objectives

2011-03-23T18:08:30Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants.
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.
**?Group Theory: Definition, Z_p, ..?

*Topics Omitted: Complex numbers, Eigenvalues, Diagonalization and applications.

CR: MATH 1104 Learning Objectives

2011-03-23T18:00:05Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
*Topics:
**Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
**Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants.
**Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.

*Topics Omitted: Complex numbers, Eigenvalues, Diagonalization and applications.

CR: MATH 1104 Learning Objectives

2011-03-23T17:58:38Z

Maheshwa: /* Calendar Description */

=Calendar Description=
MATH 1104 [0.5 credit]
Linear Algebra for Engineering or Science
Systems of linear equations. Matrix algebra. Determinants. Complex numbers. Eigenvalues. Diagonalization and applications.
Precludes additional credit for BIT 1001, BIT 1101, MATH 1102, MATH 1107, MATH 1109, MATH 1119.
Note: MATH 1119 is not an acceptable substitute for MATH 1104.
Prerequisite: Ontario Grade 12 Mathematics: Advanced Functions, or MATH 0005, or equivalent, or permission of the School.

New Version
MATH 1104 [0.5 credit]
Linear Algebra for Computer Science
Topics:
*Number Theory: Z, GCD, Primes and Relative Primes, MOD, Euclidean Algorithm, Prime Factoriazation and Fermat's Theorem.
*Matrices: Systems of linear equations, Gaussian Elimination, Matrix algebra and Determinants.
*Functions and Relations: 1-1, onto, bijection, inverse, composition, equivalence relations and partial orders.

*Topics Omitted: Complex numbers, Eigenvalues, Diagonalization and applications.

CR: MATH 1104 Learning Objectives

2011-03-23T17:52:31Z

Maheshwa: Created page with "=Calendar Description="

=Calendar Description=

CR: Learning Objectives

2011-03-23T17:51:58Z

Maheshwa:

CR: COMP 1805 Learning Objectives

2011-03-23T17:48:30Z

Maheshwa: /* Topics */

=Calendar Description=
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

=Assumed Background=

I am assuming that the students will do this course in 2nd term of their first year.
Requirements include:
*At least one course in Grade 12 Mathematics (with U TAG)
*Completed MATH 1007 (Elementary Calculus) with a grade of ...
*Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of
*1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
*2. Should have Mathematical sophistication, for example should be able to solve/show that
** Sum of two odd numbers is even
** Not all real numbers are rationals
** The number of prime numbers is infinite
** The number of possible subsets of set of size n is 2^n
** Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
** Should know what is a function, what are properties of function.
** Given a system three linear equations, in three variables, should know how to solve it.
** Should know how to solve a quadratic equation
** Should know how to compute a formula for the sum of first n natural numbers.
....

=Learning Objectives=

Objectives for the whole course
* Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation, what is a 64-bit machine?
* Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, and finite-state machines.
* Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

=Topics=
This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course.
Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

*Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

*Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

*Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation.

* Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

*Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

*Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use. (possibly cover Halting Problem - As an example of Proof by Contradiction [3.1]).

* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

* Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language as a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

* Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

* Sets [and Functions] [2.1, 2.2[, 2.3]]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. [May or may not review Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and Linear Algebra courses).]

* Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

* More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).

CR: COMP 1805 Learning Objectives

2011-03-23T17:47:32Z

Maheshwa: /* Topics */

=Calendar Description=
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

=Assumed Background=

I am assuming that the students will do this course in 2nd term of their first year.
Requirements include:
*At least one course in Grade 12 Mathematics (with U TAG)
*Completed MATH 1007 (Elementary Calculus) with a grade of ...
*Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of
*1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
*2. Should have Mathematical sophistication, for example should be able to solve/show that
** Sum of two odd numbers is even
** Not all real numbers are rationals
** The number of prime numbers is infinite
** The number of possible subsets of set of size n is 2^n
** Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
** Should know what is a function, what are properties of function.
** Given a system three linear equations, in three variables, should know how to solve it.
** Should know how to solve a quadratic equation
** Should know how to compute a formula for the sum of first n natural numbers.
....

=Learning Objectives=

Objectives for the whole course
* Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation, what is a 64-bit machine?
* Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, and finite-state machines.
* Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

=Topics=
This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course.
Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

*Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

*Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

*Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation.

* Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

*Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

*Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use.

* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

* Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language as a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

* Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

* Sets [and Functions] [2.1, 2.2[, 2.3]]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. [May or may not review Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and Linear Algebra courses).]

* Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

* More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).

* Halting Problem - As an example of Proof by Contradiction [3.1]

CR: COMP 1805 Learning Objectives

2011-03-23T17:44:22Z

Maheshwa: /* Learning Objectives */

=Calendar Description=
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

=Assumed Background=

I am assuming that the students will do this course in 2nd term of their first year.
Requirements include:
*At least one course in Grade 12 Mathematics (with U TAG)
*Completed MATH 1007 (Elementary Calculus) with a grade of ...
*Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of
*1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
*2. Should have Mathematical sophistication, for example should be able to solve/show that
** Sum of two odd numbers is even
** Not all real numbers are rationals
** The number of prime numbers is infinite
** The number of possible subsets of set of size n is 2^n
** Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
** Should know what is a function, what are properties of function.
** Given a system three linear equations, in three variables, should know how to solve it.
** Should know how to solve a quadratic equation
** Should know how to compute a formula for the sum of first n natural numbers.
....

=Learning Objectives=

Objectives for the whole course
* Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation, what is a 64-bit machine?
* Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, and finite-state machines.
* Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

=Topics=
This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course.
Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

*Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

*Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

*Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation ?

* Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

*Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

*Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use.

* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

* Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language is a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

* Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

* Sets [and Functions] [2.1, 2.2[, 2.3]]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. [May or may not review Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and Linear Algebra courses).]

* Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

* More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).

CR: COMP 2804 Learning Objectives

2011-03-22T17:46:07Z

Maheshwa: /* Topics */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Design and analysis of several simple randomized algorithms will be discussed
during the course. Statistical ...

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta, Solving recurrence relations.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing.

CR: COMP 3804 Learning Objectives

2011-03-22T17:43:42Z

Maheshwa: /* Topics */

=Calendar Description=
COMP 3804 Design and Analysis of Algorithms I

An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
* Disjoint Sets Data Structure?
* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum Spanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), review of simplex algorithm. [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
* Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.

CR: COMP 3804 Learning Objectives

2011-03-22T17:42:41Z

Maheshwa: /* Topics */

=Calendar Description=
COMP 3804 Design and Analysis of Algorithms I

An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
* Disjoint Sets Data Structure?
* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
* Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.

CR: COMP 3804 Learning Objectives

2011-03-22T17:42:04Z

Maheshwa: /* Calendar Description */

=Calendar Description=
COMP 3804 Design and Analysis of Algorithms I

An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
* Disjoint Sets Data Structure?
* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
* Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.

CR: COMP 2804 Learning Objectives

2011-03-22T17:39:33Z

Maheshwa: /* Learning Objectives */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Design and analysis of several simple randomized algorithms will be discussed
during the course. Statistical ...

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing.

CR: COMP 2804 Learning Objectives

2011-03-22T17:38:09Z

Maheshwa: /* Learning Objectives */

=Calendar Description=

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

=Assumed Background=

* COMP 1805

=Learning Objectives=

To learn basic tools and techniques from combinatorics and probability theory
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis,
probability and statistics. Several simple randoimized algorithms (design and analysis) will be discussed
during the course.

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing.

CR: COMP 2804 Learning Objectives

2011-03-22T17:32:41Z

Maheshwa: /* Calendar Description */

CR: COMP 2402 Learning Objectives

2011-03-22T17:28:44Z

Maheshwa: /* Learning Objectives */

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1406.

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, the performance issues, both theoretical and practical will be discussed. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:27:18Z

Maheshwa: /* Calender Description */

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1406.

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:27:02Z

Maheshwa: /* Assumed Background */

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1406.

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:26:32Z

Maheshwa: /* Calendar Description */

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1405
*COMP 1406.

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:26:22Z

Maheshwa: /* Prerequisite */

=Calendar Description=
=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1405
*COMP 1406.

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:26:11Z

Maheshwa: /* Calendar Description */

=Calendar Description=
=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Assumed Background=

*COMP 1805
*COMP 1405
*COMP 1406.

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Prerequisite=
COMP 1805 and COMP 1406

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-22T17:25:35Z

Maheshwa: /* Learning Objectives */

=Calendar Description=

=Assumed Background=

*COMP 1805
*COMP 1405
*COMP 1406.

=Calender Description=
2402 Abstract Data Types and Algorithms

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, sorting and searching.

=Prerequisite=
COMP 1805 and COMP 1406

=Learning Objectives=
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 1805 Learning Objectives

2011-03-22T17:21:48Z

Maheshwa: /* Calendar Description */

=Calendar Description=
Introduction to discrete mathematics and discrete structures. Topics include: propositional logic, predicate calculus, set theory, complexity of algorithms, mathematical reasoning and proof techniques, recurrences, induction, finite automata and graph theory. Material is illustrated through examples from computing.

=Assumed Background=

I am assuming that the students will do this course in 2nd term of their first year.
Requirements include:
*At least one course in Grade 12 Mathematics (with U TAG)
*Completed MATH 1007 (Elementary Calculus) with a grade of ...
*Either completed or concurrently registered in MATH 1104 (Linear Algebra)

Should have reasonable idea of
*1. Given a solution for a Grade 12 Math problem, should be able to verify it with minimal help.
*2. Should have Mathematical sophistication, for example should be able to solve/show that
** Sum of two odd numbers is even
** Not all real numbers are rationals
** The number of prime numbers is infinite
** The number of possible subsets of set of size n is 2^n
** Should know the meaning and significance of basic functions: log x, e^x, x^2, x, x^3
** Should know what is a function, what are properties of function.
** Given a system three linear equations, in three variables, should know how to solve it.
** Should know how to solve a quadratic equation
** Should know how to compute a formula for the sum of first n natural numbers.
....

=Learning Objectives=

Objectives for the whole course
* Mathematical Reasoning: Should be able to read, comprehend and construct mathematical arguments. Should develop sufficient background in mathematical logic, and should be able to apply to construct proofs. Learn some of the standard proof techniques (contradiction, induction, ..).
* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation ?, what is a 64-bit machine?
* Discrete Structures: Ability to work with discrete structures - abstract mathematical structures which are used to represent discrete objects and the relationships between objects. Examples of these structures include sets, strings, graphs, trees, finite-state machines.
* Algorithmic Thinking: Solving problems by a step-by-step process (algorithm), described in a pseudo-code. Students will get some idea on how to specify the algorithm, how to argue about its correctness, and how to argue about the computational resources (time and space) being used. (Simple algorithms like, Euclid GCD, Binary search, Merge-Sort, breadth-first search, MST, etc. may be discussed.)

=Topics=
This list is with respect to ROSEN's Discrete Math 6th edition and very closely follows the UBC Discrete Math Course.
Main omissions with current 1805 are - Big-O notation, Countability, and Relations. Big-O will be covered in COMP 2402/COMP 2804.

*Propositional Logic [1.1+11.3]: Introduce proposition, truth table, Logical operations (AND, NOT, OR, XOR..), Logical/Combinatorial Gates - simple circuits - how to design an half - full adder - how to design an adder for x+y, where x and y are 3 bits long [Introduce binary representation; complexity of a circuit = # of basic circuit components (wires+gates)]

*Logical Equivalences [1.1+1.2]: if-then-else, implication, tautology, contradiction, de Morgan's Law. Learn how to simplify, manipulate, and understand complex logical statements.

*Number Representation [3.6 + ?]: Representation of integers, hexadecimal expansion, base conversion, operation on binary numbers - addition, 2's complement, whats a 64-bit machine - what are limitations of this representation. Floating-point representation ?

* Predicates and Quantifiers [1.3+1.4]: whats a predicate? universal quantifiers, existential quantifier, negation of quantified statements, why are they important in CS (e.g Logic Programming), nested quantifiers and their ordering.

*Rules of Inference [1.5]: What is a valid argument in propositional logic, basic rules of inference (if-then-else), using rules to build arguments, resolution, quantification.

*Proof Techniques [1.6, 1.7, 3.4]: different methods, strategies. Check whether a propositional logic proof is valid or not, whether it is proving the statement. Practice on simple exercises - how to build a counterexample, how to prove a given statement - what techniques to use.

* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.

* Introduction to Finite State Machines and Graphs [Parts of 12.2+12.3, Relevant Parts of Chapter 9]: Whats a DFA, how to trace the operation of a DFA, concept of acceptance/rejection of a string, concept of a language, how to design a DFA accepting s simple language. Language is a set of strings. Also show that DFA is a graph - a directed graph - and discuss some properties of undirected and directed graphs - paths and connectivity.

* Induction and Recursion [Chapter 4]. Establish properties of self-referential structures using inductive proofs. What are steps involved in proof by induction - show right and wrong proofs - standard pitfalls - describe simple recursive algorithms (e.g. n!, linear search, binary search, merge sort, tree traversals, and discuss how to show that they are correct using Induction and how to argue about computational resources being used).

* Sets [and Functions] [2.1, 2.2[, 2.3]]: Power Set, Cartesian Products, Set Operations and de Morgans Laws. [May or may not review Functions : definition, 1-1 and onto, inverse (its expected that they will learn in depth about functions in Calculus and Linear Algebra courses).]

* Advanced DFA/NFA [12.1,12.2,12.3]: NFA, Designing NFA, Equivalence of DFA and NFA, existence of languages not recognized by a DFA - regular languages. Idea is to show the capabilities and limitations of these simple computation model - and show how discrete math (proof by contradiction, sets, power set, pigeon hole principle) are used to establish non-trivial results.

* More Graph Theory [Relevant Parts of Chapter 9] Stating some of the standard daily-life problems, in terms of Mathematical Abstraction as graphs, and showing some simple graph properties and algorithms which may address the problem. (e.g. MST, DFS, BFS).

CR: COMP 2804 Learning Objectives

2011-03-10T18:03:12Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

* COMP 1805

=Learning Objectives=

Objectives for the whole course

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
* Statistics: Confidence tests and Intervals, Hypothesis Testing.

CR: COMP 2804 Learning Objectives

2011-03-10T18:01:42Z

Maheshwa: /* Assumed Background */

=Calendar Description=

=Assumed Background=

* COMP 1805

=Learning Objectives=

Objectives for the whole course

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicsort, Binary Search Trees, Skip Lists.
* Statistics: ?
* Missing: Countability and Relations.

CR: COMP 2402 Learning Objectives

2011-03-10T17:59:37Z

Maheshwa: /* Assumed Background */

=Calendar Description=

=Assumed Background=

*COMP 1805
*COMP 1405
*COMP 1406.

=Learning Objectives=
[Based on Pat Morin's offering of COMP 2402 in Fall 2010]
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 2402 Learning Objectives

2011-03-10T17:59:13Z

Maheshwa: /* Assumed Background */

=Calendar Description=

=Assumed Background=

COMP 1805
COMP 1405 & COMP 1406.

=Learning Objectives=
[Based on Pat Morin's offering of COMP 2402 in Fall 2010]
This is an introductory course on data structures, using Java as an implementation language. The main topics covered in this course will be
* The Java Collections Framework
* Complexity analysis - Big Oh notation.
* Basic data types: sets, lists, stacks, queues, deques
* Array-based implementations of basic data types
* Linked-list based implementations of basic data types
* Ordered sets - balanced binary search trees, skiplists
* Basic Lower Bounds: Searching and Sorting
* Dictionaries - hash tables
* Priority queues - heaps

Along the way, we will consider performance issues, both theoretical and practical. After taking this course, students should have a good understanding of how to implement a variety of data structures, and be in a position to choose the right data type and implementation for problems they encounter.

=Topics=
* Java: The Java Collections Framework: Interfaces and Implementations
* Arrays: ArrayLists, ArrayStacks, ArrayQueues, ArrayDeques, DualArrayDeques, RootishArrayStacks
* Linked lists
* Hash tables
* Skip lists
* Complexity Analysis: Big O, Theta
* Binary search trees: Red-Black Trees
* Treaps and Scapegoat Trees
* Heaps, Randomized meldable heaps
* Mergesort and sorting lower bounds
* Applications: Plane sweep, Convex Hull, ...

CR: COMP 3804 Learning Objectives

2011-03-10T17:52:40Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication ..
* Disjoint Sets Data Structure?
* Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
* Whats Next: Brief idea on how to cope with NP-Complete problems - one lecture introduction to approximation algorithms, exhaustive search and search heuristics.

CR: COMP 3804 Learning Objectives

2011-03-10T16:42:42Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, Simple Divide and Conquer Algorithms (e.g. Multiplying two n-bit integers), merge-sort, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Some are already stated above, Median
* Disjoint Sets Data Structure
* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).

CR: COMP 2804 Learning Objectives

2011-03-10T16:41:05Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

Learning objectives completed before this course.

=Learning Objectives=

Objectives for the whole course

=Topics=
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
* Asymptotic Complexity: O, Theta.
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
* Randomized Algorithms: Median, Quicsort, Binary Search Trees, Skip Lists.
* Statistics: ?
* Missing: Countability and Relations.

CR: COMP 3804 Learning Objectives

2011-03-10T16:20:38Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, Simple Divide and Conquer Algorithms (e.g. Multiplying two n-bit integers), merge-sort, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Some are already stated above, Median
* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm). [This was never covered before]
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).

CR: COMP 3804 Learning Objectives

2011-03-10T16:19:38Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, Simple Divide and Conquer Algorithms (e.g. Multiplying two n-bit integers), merge-sort, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Some are already stated above, Median
* Graph Algorithms: Representation, DFS, BFS, Shortest Paths (including A* heuristic).
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm).
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems (1 lecture introduction to approximation algorithms, exhaustive search and search heuristics).

CR: COMP 3804 Learning Objectives

2011-03-10T16:15:55Z

Maheshwa: /* Topics */

=Calendar Description=

=Assumed Background=

COMP 2402 and COMP 2804.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency.
* How to think about abstract computation - develop algorithmic intution - how to attack a problem algorithmically.
* Algorithmic techniques - learn key techniques (greed, divid-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem.
* How to compare one algorithmic solution versus another for a problem
* How to express the algorithmic solution - pseodcode - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

=Topics=
COMP 3804 offerings from Fall and Winter 2010-2011 by Anil and Michiel
* Introduction: Whats an Algorithm, Simple Divide and Conquer Algorithms (e.g. Multiplying two n-bit integers), merge-sort, bib-O notation, recurrence relation, masters theorem.
* Divide and Conquer: Some are already stated above, Median
* Graph Algorithms: Representation, DFS, BFS, Shortest Paths.
* Greedy Algorithms: Minimum SPanning Trees, Huffman Encodings, ...
* Dynamic Programming: Edit Distance, Longest Common Sequence, ...
* Linear Programming: What it is, how to express seveal problems as LP problems (Flow, Shortest Paths, Matching), ideas of simplex algorithm (or the randomized algorithm).
* NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem, and brief idea on how to cope with NP-Complete problems.

CR: COMP 3804 Learning Objectives

2011-03-10T16:08:13Z

Maheshwa: /* Topics */

CR: COMP 3804 Learning Objectives

2011-03-10T16:06:34Z

Maheshwa: /* Learning Objectives */

CR: COMP 3804 Learning Objectives

2011-03-10T16:00:55Z

Maheshwa: /* Assumed Background */

CR: COMP 3804 Learning Objectives

2011-03-10T16:00:32Z

Maheshwa: /* Learning Objectives */

=Calendar Description=

=Assumed Background=

Learning objectives completed before this course.

=Learning Objectives=

Objectives for the whole course
* Designing algorithms, their correctness and efficiency

=Topics=

==Topic 1==

Learning objectives for topic 1

==Topic 2==

Learning objectives for topic 2