CR: COMP 1805 Learning Objectives - Revision history

Maheshwa: /* Topics */

2011-03-23T18:42:38Z

Topics

← Older revision		Revision as of 18:42, 23 March 2011
Line 54:		Line 54:
	* 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).		* 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).]		* 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.		* 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).		* 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).

Maheshwa: /* Topics */

2011-03-23T17:48:30Z

Topics

← Older revision		Revision as of 17:48, 23 March 2011
Line 46:		Line 46:
	*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.		*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.		*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.		* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.
Line 59:		Line 59:

	* 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).		* 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]

Maheshwa: /* Topics */

2011-03-23T17:47:32Z

Topics

← Older revision		Revision as of 17:47, 23 March 2011
Line 40:		Line 40:
	*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.		*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 ?		*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.		* 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.
Line 50:		Line 50:
	* Sets [2.1]: Very basics of sets - definition, membership, basic operations on sets.		* 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.		* 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).		* 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).
Line 59:		Line 59:

	* 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).		* 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]

Maheshwa: /* Learning Objectives */

2011-03-23T17:44:22Z

Learning Objectives

← Older revision		Revision as of 17:44, 23 March 2011
Line 28:		Line 28:
	Objectives for the whole course		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, ..).		* 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?		* 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.		* 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.)		* 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.)

Maheshwa: /* Calendar Description */

2011-03-22T17:21:48Z

Calendar Description

← Older revision		Revision as of 17:21, 22 March 2011
Line 1:		Line 1:
	=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=		=Assumed Background=

Maheshwa: /* Topics */

2011-03-10T15:30:37Z

Topics

← Older revision		Revision as of 15:30, 10 March 2011
Line 39:		Line 39:
	*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.		*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.		*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.		* 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.

Maheshwa: /* Topics */

2011-03-10T15:29:35Z

Topics

← Older revision		Revision as of 15:29, 10 March 2011
Line 57:		Line 57:
	* 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.		* 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.		* 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).

Maheshwa: /* Learning Objectives */

2011-03-09T19:56:48Z

Learning Objectives

← Older revision		Revision as of 19:56, 9 March 2011
Line 29:		Line 29:
	* Number Representation: Learn Bits, Bytes, Binary Representation, Floating-point representation ?, what is a 64-bit machine?		* 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.		* 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. ~~can~~ be discussed.)		* 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=		=Topics=

Maheshwa: /* Learning Objectives */

2011-03-09T19:55:52Z

Learning Objectives

← Older revision		Revision as of 19:55, 9 March 2011
Line 28:		Line 28:
	* 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, ..).		* 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?		* 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, ~~permutations, relations~~, graphs, trees, finite-state machines.		* 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. can be discussed.)		* 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. can be discussed.)

Maheshwa: /* Learning Objectives */

2011-03-09T19:55:02Z

Learning Objectives

← Older revision		Revision as of 19:55, 9 March 2011
Line 27:		Line 27:
	Objectives for the whole course		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, ..).		* 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?		* 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, permutations, relations, graphs, trees, finite-state machines.		* 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, permutations, relations, 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. can be discussed.)		* 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. can be discussed.)